Flashcard FC377464
Como identificar se uma inserção em uma árvore AVL exige rotação simples ou dupla?
Algoritmos e Lógica de Programação
Instituto Consulplan · 2023
Como identificar se uma inserção em uma árvore AVL exige rotação simples ou dupla?
Mostrar resposta e comentário
Resposta
Resposta: Pelo padrão do caminho de inserção: inserção no filho externo → rotação simples; inserção no filho interno → rotação dupla.Explicação:
Critério: nó com fator de balanceamento ±2 e o filho mais pesado com mesmo sinal (ex.: esquerda-esquerda ou direita-direita) indica caso LL/RR → rotação simples.
Se o filho mais pesado tem fator oposto (inserção no ramo interno), é caso LR/RL → rotação dupla.
A rotação reequilibra localmente; a altura da região pode aumentar em 1 quando aplicável.
Como a árvore permanece AVL, as operações mantêm complexidade \(O(\log n)\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/374694
Conteúdo do catálogo FC Concursos · Atualizado em