Árvores AVL

Definição

Árvores binárias de busca em que cada nó x obedece a seguinte propriedade:
- O módulo da diferença entre as alturas das sub-árvores direita e esquerda de x é menor ou igual à 1. Ou seja,

| HD(x)-HE(x)| < = 1

Algoritmo de inserção

Para cada nó x manteremos um campo chamado balanço, que corresponderá à diferença entre as alturas das sub-árvores direita e esquerda de x. Ou seja,

Balanço(x) = HD(x)-HE(x)

Cada nó da AVL possuirá a seguinte strutura:

struct SNo
{   ... chave ...
   SNo * FilhoEsquerdo,
   SNo * FilhoDireito;
   int Balanço;
}

InserçãoAVL(...)
Inserir nó v usando algoritmo de inserção da ABB
Seja v um ponteiro para o nó Inserido.
v->Balanco = 0 
v = Pai(v)
Enquanto v != NULL [O(logn)]
    Se Inseriu à Esquerda de v
        Se v->Balanco = = 1 
            v->Balanco = 0
           Break // Terminou Insercao.
        Se v->Balanco = = 0 
            v->Balanco = -1
            // Mudou Altura mas não desregulou.
            // Precisa continuar verificando ancestrais.'
        Se v->Balanco = = -1 entao
           Balancear(v) 
           Break
    Senao // Inseriu à Direita de v
      // Simétrico ao ''Se''
    v = Pai(v); // v deve "ir subindo"		 Balancear(SNo * p)
// Verificar o tipo da rotação [O(log1)]
Se Inseriu à Esquerda de p
   u = p->FilhoEsquerdo
   Se inseriu à Esquerda de u
        RD(p,u) // Rotação à Direita
   Senão // Rotação Dupla à Direita
        RDD(p,u,u->FilhoDireito) 
Senão // Inseriu à Direita de p
   // Caso Simétrico (RE, RDE).

// Executar rotação e Ajustar balanço [O(log1)]
RD(SNo * p, SNo * u)
   T2 = u->FilhoDir
   u->FilhoDir = p
   p->FilhoEsq = T2
   u->Balanco = 0 // Verificar se é
   p->Balanco = 0 // isto mesmo.
   Trocar Filho de Pai de p para u, 
   se necessário (Se p tiver pai).

    Algorítmo Recursivo: Clique aqui para obter um "rascunho" de uma implementação de um algorítmo recursivo para inserção em AVL.
 
 

Algoritmo de Remoção