Árvores AVL e vermelho-pretas

Rodar sem trocar ordem

Rotação troca pai e filho e move a subárvore do meio. Em-ordem conserva-se. Custa $O(1)$.

Atualiza a antiga raiz antes da nova e religa ao pai.

AVL pelo fator

Com vazio de altura -1, cada nó tem $b=h_e-h_d$ em -1,0,1.

Fator	Filho pesado	Repara com
2	Esquerda-esquerda	Direita no nó
2	Esquerda-direita	Esquerda no filho e direita no nó
-2	Direita-direita	Esquerda no nó
-2	Direita-esquerda	Direita no filho e esquerda no nó

Exterior pede rotação simples; interior pede rotação dupla. Na inserção, repara o primeiro nó desequilibrado a subir. Na remoção, verifica todos os antepassados: quando o filho tem fator 0, a rotação simples correspondente também repõe o equilíbrio, mas a altura da subárvore não diminui.

O número mínimo de nós de uma AVL de altura h segue $N(h)=1+N(h-1)+N(h-2)$, com $N(-1)=0$ e $N(0)=1$. Daqui resulta altura $O(\log n)$.

Vermelho-pretas em quatro casos

Raiz e NIL pretos, sem vermelhos seguidos, mesma altura preta em todos os caminhos. Altura até $2\log_2(n+1)$.

Inserir vermelho como numa BST e depois:

Pai e tio	Configuração	Ação
Pai preto	Qualquer	Nada
Ambos vermelhos	Qualquer	Recolore e sobe
Pai vermelho, tio preto	Exterior	Roda no avô e troca cores
Pai vermelho, tio preto	Interior	Roda no pai e cai no caso anterior

Pinta a raiz de preto no fim. Remoção de preto pode exigir reparação longa; estas notas não substituem a receita completa.

Provas e código.