FC ConcursosFC Concursos

Questão FC374694

Observe a árvore binária de busca balanceada AVL a seguir: Considerando a inserção dos seguintes elementos (na ordem): 129, 134 e 136, analise as afirmativas a seguir. I. Provoca u

Algoritmos e Lógica de Programação

Instituto Consulplan · 2023

Observe a árvore binária de busca balanceada AVL a seguir:

 

 

Considerando a inserção dos seguintes elementos (na ordem): 129, 134 e 136, analise as afirmativas a seguir.

 

I. Provoca uma rotação dupla na árvore, direita/esquerda, o que adiciona um novo nó ao segundo nível da árvore.

 

II. Resulta em uma rotação simples e aumenta a altura da árvore.

 

III. Após a inserção, a complexidade computacional das operações se mantém em O(log n), no pior caso, onde n é o número de nós da árvore.

 

Está correto o que se afirma apenas em

  1. II.
  2. I e II.
  3. I e III.
  4. II e III.
Mostrar resposta e comentário

Gabarito

D

Comentário do professor

A sequência de inserções 129, 134 e 136 provoca, na subárvore afetada, um desbalanceamento do tipo que exige uma rotação simples (no caso, uma rotação à esquerda no nó desequilibrado). Após inserir 136 a diferença de alturas entre as subárvores do nó pai atinge 2, caracterizando um caso RR que é corrigido por uma única rotação simples, restaurando o fator de balanceamento.

Essa correção reestrutura localmente a árvore, e a operação de inserção, somada à rotação, faz com que a altura da árvore aumente em uma unidade no caminho até a raiz (quando aplicável), pois foi adicionado um novo nível na região afetada antes do balanceamento final.

Por fim, como a árvore permanece AVL (balanceamento mantido), as complexidades das operações de busca, inserção e remoção continuam em O(log n) no pior caso, onde \(n\) é o número de nós.

Conteúdo do catálogo FC Concursos · Atualizado em

Continue aprendendo