Questão 5509675

• Banca: VUNESP
• Órgão: Semae de Piracicaba - SP
• Ano: 2021
• Provas: VUNESP - 2021 - Semae de Piracicaba - SP - Programador Junior
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Árvores; Estrutura de Dados

Considere uma estrutura de dados T como sendo uma árvore binária do tipo AVL. Como característica, essa estrutura de dados é uma árvore binária

• A. balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) diferem de até uma unidade.
• B. balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) são sempre idênticas.
• C. não balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) diferem de até uma unidade.
• D. não balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) são sempre idênticas.
• E. não balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) diferem exatamente de uma unidade.

Gabarito: A

Comentários

• Uma árvore binária T é denominada AVL quando, para qualquer nó de T, as alturas de suas duas subárvores, esquerda e direita, diferem em módulo de até uma unidade.

  Pela definição fica estabelecido que todos os nós de uma árvore AVL devem respeitar a seguinte propriedade:

  |h(u) - h(u)| ≤ 1, onde h(u) é a altura da subárvore direita do nó u e h(u) é a altura da subárvore esquerda do nó u.

  O valor h(u) - h(u) é denominado fator de balanço do nó. Quando um nó possui fator de balanço com valor -1, 0 ou 1 então o mesmo é um nó regulado. Todos os nós de uma árvore AVL são regulados, caso contrário a árvore não é AVL.

• GABARITO A

  Balanceamento Dinâmico (AVL): São árvores binárias de busca auto balanceada;

  • Mais eficientes para buscas;
  • A cada nó que é inserido, alterado ou excluído, é necessário realizar todo o trabalho de balanceamento de novo para que permaneça com as características da árvore AVL;
  • Possuem complexidade O(log n);
  • Inserções e exclusões podem requerer um rebalanceamento, por meio de rotações;
  • Toda árvore completa é AVL;
  • Para cada nó da árvore, a diferença entre as alturas das suas subárvores (direita e esquerda) sempre será igual a -1, 0 ou 1.