Questão 79201

• Banca: FCC
• Órgão: TRT - 18ª Região (GO)
• Ano: 2008
• Provas: FCC - 2008 - TRT - 18ª Região (GO) - Analista Judiciário - Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados

Árvore AVL balanceada em altura significa que, para cada nó da árvore, a diferença entre as alturas das suas sub- árvores (direita e esquerda) sempre será

• A. menor ou igual a 2.
• B. igual a 0 ou -1.
• C. maior que 1.
• D. igual a 1.
• E. igual a -1, 0 ou 1.

Gabarito: E

Comentários

• Árvore AVL (ou árvore balanceada pela altura), em Ciência da Computação, é uma árvore de busca binária auto-balanceada. Em tal árvore, as alturas das duas sub-árvores a partir de cada nó difere no máximo em uma unidade.O FATOR DE BALANCEAMENTO DE UM NÓ É DADO PELO SEU PESO EM RELAÇÃO A SUA SUB-ÁRVORE. UM NÓ COM FATOR BALANCEADO PODE CONTER 1, 0, OU -1 EM SEU FATOR. Um nó com fator de balanceamento diferente dos citados é considerado uma árvore não-AVL e requer um balanceamento por rotação ou dupla-rotação.Fonte: http://pt.wikipedia.org/wiki/%C3%81rvore_AVL

• Árvores AVL

  - São árvores binárias de busca autobalanceada.

  - 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.

  - Caso a árvore não esteja balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla.

  Alternativa: E