Rotação simples à direita (caso LL)
Aplicada quando o excesso de nós está no lado esquerdo do filho esquerdo.
30 20
/ → / \
20 10 30
/
10
Estruturas de dados
Busca em Árvore Binária
Crie sua própria árvore, pratique inserções e remoções e veja como funcionam os principais percursos e rotações.
Crie uma árvore binária de busca
Valores menores seguem para a esquerda e valores maiores para a direita. Insira ou remova um valor e acompanhe a nova estrutura.
A árvore de exemplo está pronta para edição.
Remoção com dois filhos: a busca começa no filho esquerdo do nó excluído e continua pelos filhos à direita até não existir outro. O último nó encontrado assume o lugar do excluído. No exemplo, a busca começa em 2; como ele não possui filho à direita, o próprio 2 substitui 3, aponta para 4, e a raiz 5 passa a apontar para 2. Se existisse um nó à direita de 2, a busca continuaria até o mais à direita.
Nós: 0
Altura: 0
Ordem simétrica: —
Rotações em árvores
Uma rotação reorganiza os nós sem alterar a ordem dos valores. Árvores balanceadas usam essas operações para reduzir a altura e manter buscas eficientes.
Rotação simples à esquerda (caso RR)
Aplicada quando o excesso de nós está no lado direito do filho direito.
10 20
\ → / \
20 10 30
\
30
Rotação dupla esquerda-direita (caso LR)
Primeiro gira o filho esquerdo à esquerda; depois gira a raiz à direita.
30 20
/ → / \
10 10 30
\
20
Rotação dupla direita-esquerda (caso RL)
Primeiro gira o filho direito à direita; depois gira a raiz à esquerda.
10 20
\ → / \
30 10 30
/
20
Importante: a árvore criada acima é uma árvore binária de busca comum e não faz rotações automaticamente. Veja o balanceamento em ação no Simulador de Árvore AVL.
Percursos na árvore
Pré-Ordem
Visita primeiro a raiz, depois a subárvore esquerda e, por fim, a direita.
Ordem Simétrica
Percorre a esquerda, visita a raiz e termina na subárvore direita.
Pós-Ordem
Visita as subárvores esquerda e direita antes de visitar a raiz.