Árvores AVL — Estrutura de Dados I

A árvore AVL, uma árvore de busca que guarda a altura em cada nó e usa rotações para manter |fb| ≤ 1 em todos os nós, com altura sempre O(log n).

A árvore binária de busca degenera quando as chaves chegam ordenadas, e a página de árvores balanceadas apresentou as ferramentas para evitar isso: o fator de balanceamento, para detectar um nó desequilibrado, e as rotações, para consertá-lo sem perder a ordem das chaves. A árvore AVL junta essas duas ferramentas.

Ela foi a primeira árvore de busca balanceada a ser proposta, em 1962, pelos matemáticos soviéticos Georgy Adelson-Velsky e Evgenii Landis (o nome vem das iniciais deles). A ideia é simples: depois de cada inserção ou remoção, percorrer de volta o caminho até a raiz, recalculando as alturas, e aplicar uma ou duas rotações em cada nó que tiver ficado desequilibrado.

Definição

Definição 1(Árvore AVL)

Uma árvore AVL é uma árvore binária de busca em que todo nó satisfaz , ou seja, as alturas da SAE e da SAD de diferem de no máximo 1.

Lembrando a definição do fator de balanceamento: , com a árvore vazia de altura . Em uma AVL, todo nó tem fator , ou .

Duas árvores de busca com o fator de balanceamento anotado ao lado de cada nó. Em (a), as chaves 50, 30, 70, 20, 40, 60 e 10, com todos os fatores entre -1 e +1: é uma árvore AVL. Em (b), as chaves 5, 3, 8, 2, 7, 9, 1 e 10: o nó 3 tem a SAE com altura 1 e a SAD vazia, fator +2, e está em vermelho; a árvore não é AVL — (a) Uma árvore AVL. (b) Uma árvore de busca que não é AVL: basta um nó com |fb| = 2.

Repare em (b): a raiz tem fator 0 e a árvore parece "quase" balanceada, mas a condição vale para todo nó, e o nó 3 a viola. Repare também que uma AVL não precisa ser completa: em (a), o 70 tem um filho só e as folhas estão em níveis diferentes.

Pergunta

Em (b), qual é a menor alteração (inserção ou remoção de uma única chave) que transforma a árvore em uma AVL, sem nenhuma rotação?

Ver respostaEsconder resposta

Inserir uma chave entre 3 e 5 (o 4, por exemplo), que vira o filho direito de 3: o fator do 3 passa a ser , e o resto continua com (a raiz passa a ter ). Remover o 1 também resolve: o 3 fica com e a raiz com .

O nó guarda a altura

Calcular a altura percorrendo a subárvore custa , e a AVL precisa do fator de cada nó do caminho a cada operação. Por isso, cada nó guarda a sua altura, e o fator passa a custar . O TAD é o mesmo da página da ABB, com a mesma interface (Arvore.h), e só o nó ganha um campo:

typedef struct no {
    Chave chave;
    Valor valor;
    int altura;         /* altura do nó (folha = 0) */
    struct no *esq;
    struct no *dir;
} No;

Três funções auxiliares, todas static em Arvore.c, cuidam das alturas:

/* Altura guardada no nó; a árvore vazia tem altura -1 */
static int altura(const No *r) {
    return r == NULL ? -1 : r->altura;
}

/* Recalcula a altura de r a partir das alturas (já corretas) dos filhos */
static void atualizaAltura(No *r) {
    int he = altura(r->esq), hd = altura(r->dir);
    r->altura = (he > hd ? he : hd) + 1;
}

static int fatorBalanceamento(const No *r) {
    return altura(r->esq) - altura(r->dir);
}

A função altura existe para tratar o NULL: sem ela, cada acesso a r->esq->altura precisaria testar antes se o filho existe. E atualizaAltura não é recursiva: ela supõe que as alturas dos filhos já estão certas. Toda a correção da AVL depende de chamá-la de baixo para cima, depois que os filhos foram atualizados.

Como consequência, alturaArvore passa a custar : a altura da árvore é a altura guardada na raiz.

Rotações com alturas

As rotações são as da página anterior, agora chamando os dois nós envolvidos de (o nó desequilibrado, que desce) e (o filho que sobe). A única novidade é que, depois de mudar os ponteiros, as alturas de e de precisam ser recalculadas: as subárvores não mudam por dentro, então as alturas delas continuam certas.

/* Rotação à direita em A: o filho esquerdo B sobe */
static No *rotacaoDireita(No *A) {
    No *B = A->esq;
    A->esq = B->dir;
    B->dir = A;
    atualizaAltura(A);      /* primeiro A, que agora está embaixo */
    atualizaAltura(B);
    return B;
}

/* Rotação à esquerda em A: o filho direito B sobe */
static No *rotacaoEsquerda(No *A) {
    No *B = A->dir;
    A->dir = B->esq;
    B->esq = A;
    atualizaAltura(A);
    atualizaAltura(B);
    return B;
}

A ordem das atualizações importa

Depois da rotação, é filho de . A altura de depende da altura de , então precisa ser atualizado antes. Na ordem inversa, usa a altura antiga de , e o erro se propaga silenciosamente para cima: é o erro do Programa 1.

Os quatro casos

Quando um nó fica com , a correção depende de onde está a parte alta demais. Se , a SAE de é a mais alta, e olhamos o filho esquerdo para saber de qual lado dele está o excesso:

se o excesso está à esquerda de , o caminho de até a parte funda vai para a esquerda e de novo para a esquerda: é o caso LL (left-left);
se está à direita de , o caminho vai para a esquerda e depois para a direita: é o caso LR (left-right).

Os casos RR e RL são os espelhos, com .

Casos pelo caminho, rotações pela direção

Nesta página, as siglas LL, RR, LR e RL nomeiam os casos, e descrevem o caminho de até a subárvore alta demais. As rotações são nomeadas pela direção em que os nós giram: rotacaoDireita e rotacaoEsquerda. Atenção ao comparar com outros materiais: alguns livros e slides usam "rotação RR" ou "rotação LL" para as próprias rotações, e não há um padrão único. Por exemplo, o caso LL é corrigido por uma rotação à direita, que em alguns textos é chamada de "rotação RR" (porque gira para a direita) e, em outros, de "rotação LL" (porque corrige o caso LL). Na dúvida, olhe a figura: quem sobe e para que lado.

Casos LL e RR: uma rotação

No caso LL, o excesso está em e , abaixo de , o filho esquerdo de . Pela proposição sobre profundidades, uma rotação à direita em faz essa parte subir um nível, e , que era a mais baixa, desce um nível.

Caso LL. Antes: A, com fator +2, tem o filho esquerdo B, com fator +1, e a subárvore T4 à direita; B tem o filho esquerdo C e a subárvore T3 à direita; C tem as subárvores T1 e T2. Depois da rotação à direita em A: B é a raiz, com C à esquerda e A à direita, e A tem T3 e T4 como filhos; B e A ficam com fator 0. Em ordem, antes e depois: T1, C, T2, B, T3, A, T4 — Caso LL: uma rotação à direita em A. A ordem simétrica não muda.

O caso RR é o espelho: o excesso está à direita do filho direito, e a correção é uma rotação à esquerda em .

Caso RR, o espelho do caso LL. Antes: A, com fator -2, tem a subárvore T1 à esquerda e o filho direito B, com fator -1; B tem a subárvore T2 à esquerda e o filho direito C, com T3 e T4. Depois da rotação à esquerda em A: B é a raiz, com A à esquerda (filhos T1 e T2) e C à direita (filhos T3 e T4), e fatores 0. Em ordem: T1, A, T2, B, T3, C, T4 — Caso RR: uma rotação à esquerda em A.

Casos LR e RL: duas rotações

No caso LR, o excesso está na subárvore com raiz , o filho direito de . Uma rotação à direita em não resolve: fica no meio, e a mesma proposição diz que a subárvore do meio não muda de profundidade. A solução é, primeiro, uma rotação à esquerda em , que transforma o caso LR em um caso LL; depois, a rotação à direita em .

Caso LR em três etapas. Antes: A, com fator +2, tem o filho esquerdo B, com fator -1, e T4 à direita; B tem T1 à esquerda e o filho direito C, que tem T2 e T3. Depois da primeira rotação, à esquerda em B: C é o filho esquerdo de A, e B é o filho esquerdo de C, com T1 e T2; T3 fica à direita de C. Depois da segunda rotação, à direita em A: C é a raiz, com B à esquerda (T1 e T2) e A à direita (T3 e T4), e fator 0 — Caso LR: à esquerda em B, depois à direita em A. No fim, C, que estava no meio, vira a raiz.

Caso RL, o espelho do caso LR. Antes: A, com fator -2, tem T1 à esquerda e o filho direito B, com fator +1; o filho esquerdo de B é C. Primeiro, uma rotação à direita em B põe C como filho direito de A; depois, uma rotação à esquerda em A põe C na raiz, com A à esquerda e B à direita — Caso RL: à direita em B, depois à esquerda em A.

Muitos textos chamam o par de rotações de rotação dupla (à direita ou à esquerda, conforme a segunda). No código, não há uma função separada para ela: são duas chamadas às mesmas funções.

Resumo

Caso			Correção
LL			à direita em
RR			à esquerda em
LR			à esquerda em , depois à direita em
RL			à direita em , depois à esquerda em

Aqui é o filho de do lado mais alto. O caso (com e na tabela) nunca acontece na inserção, mas acontece na remoção, e vamos voltar a ele mais adiante.

O menor exemplo de cada caso tem só três nós: as quatro ordens de inserção abaixo terminam todas na mesma árvore, com 2 na raiz.

Quatro painéis. (a) Inserir 3, 2, 1 forma uma linha para a esquerda, com fator +2 em 3: caso LL, corrigido com uma rotação à direita em 3. (b) Inserir 1, 2, 3 forma uma linha para a direita, com fator -2 em 1: caso RR, corrigido com uma rotação à esquerda em 1. (c) Inserir 3, 1, 2: 1 é filho esquerdo de 3 e 2 é filho direito de 1, caso LR, corrigido com uma rotação à esquerda em 1 e depois à direita em 3. (d) Inserir 1, 3, 2: caso RL, corrigido com uma rotação à direita em 3 e depois à esquerda em 1. Nos quatro, o resultado é 2 na raiz, com 1 à esquerda e 3 à direita — As quatro ordens de inserção que desequilibram uma árvore de três nós, uma para cada caso.

Questão

Em uma AVL vazia, inserimos 30, depois 10, depois 20. Qual caso acontece, e qual é a raiz no final?

A função balanceia

A tabela vira uma única função, chamada para cada nó do caminho, de baixo para cima. Ela atualiza a altura do nó e, se ele estiver desequilibrado, aplica as rotações e devolve a nova raiz da subárvore.

/* Atualiza a altura de r e, se |fb| > 1, aplica a rotação certa.
   Devolve a raiz da subárvore depois do rebalanceamento. */
static No *balanceia(No *r) {
    atualizaAltura(r);
    int fb = fatorBalanceamento(r);
    if (fb > 1) {                                   /* SAE alta demais */
        if (fatorBalanceamento(r->esq) < 0)         /* caso LR */
            r->esq = rotacaoEsquerda(r->esq);
        return rotacaoDireita(r);                   /* casos LL e LR */
    }
    if (fb < -1) {                                  /* SAD alta demais */
        if (fatorBalanceamento(r->dir) > 0)         /* caso RL */
            r->dir = rotacaoDireita(r->dir);
        return rotacaoEsquerda(r);                  /* casos RR e RL */
    }
    return r;
}

Três detalhes:

os testes são fb > 1 e fb < -1, e não fb == 2: se as alturas estão corretas, o fator nunca passa de 2, mas o teste com > é mais robusto e igualmente claro;
o filho é testado com < 0 e > 0, e não com == -1 e == 1. A diferença está no caso , que só aparece na remoção e precisa ser tratado como LL (ou RR). É o erro do Programa 2;
a primeira rotação do caso duplo muda a raiz da subárvore de r->esq (ou r->dir), e o retorno precisa ser guardado ali, como na página anterior. Esquecer isso é o erro do Programa 4.

Inserção

A inserção é a da ABB, com uma linha a mais: na volta da recursão, cada nó do caminho passa por balanceia.

1
Desça como na ABB#
Compare a chave com a do nó atual e desça para a esquerda ou para a direita, até encontrar um NULL (ou a própria chave, que só tem o valor atualizado).
2
Crie a folha#
No lugar do NULL, crie o novo nó, com altura 0. Ele é uma folha e está balanceado.
3
Volte rebalanceando#
Na volta da recursão, cada nó do caminho, do pai da nova folha até a raiz, passa por balanceia: a sua altura é recalculada a partir dos filhos, que já estão corretos, e, se , as rotações do caso correspondente são aplicadas.
4
Atualize os ponteiros#
Cada chamada devolve a raiz (possivelmente nova) da sua subárvore, e o pai a guarda em r->esq ou r->dir. Na raiz, insereArvore guarda o retorno em arvore->raiz.

static No *insereNo(No *r, Chave chave, Valor valor, bool *novo) {
    if (r == NULL) {
        *novo = true;
        return criaNo(chave, valor);
    }
    if (chave < r->chave)
        r->esq = insereNo(r->esq, chave, valor, novo);
    else if (chave > r->chave)
        r->dir = insereNo(r->dir, chave, valor, novo);
    else
        r->valor = valor;               /* chave já existe: atualiza */
    return balanceia(r);                /* na volta da recursão */
}

O padrão r->esq = insereNo(r->esq, ...) é exatamente o da ABB, e é o que torna as rotações simples de encaixar: quem chama já guarda a raiz devolvida, seja ela a mesma de antes ou uma nova, vinda de uma rotação.

A figura mostra a inserção das chaves de 1 a 8, em ordem crescente, o pior caso da ABB comum. Os títulos em destaque indicam as rotações feitas.

Oito painéis com a árvore depois de cada inserção, com o nó recém-inserido em verde. Inserir 1 e 2 não exige rotação. Inserir 3 causa uma rotação à esquerda em 1, e 2 vira a raiz. Inserir 4 não exige rotação. Inserir 5 causa uma rotação à esquerda em 3. Inserir 6 causa uma rotação à esquerda em 2, e 4 vira a raiz. Inserir 7 causa uma rotação à esquerda em 5. Inserir 8 não exige rotação; a árvore final tem 4 na raiz, com 2 (filhos 1 e 3) à esquerda e 6 (filhos 5 e 7, e 7 com o filho direito 8) à direita, e altura 3 — Inserção de 1 a 8 em uma AVL. Na ABB comum, a altura seria 7; aqui, é 3.

Repare que todas as rotações da figura são simples (casos RR): com chaves crescentes, o excesso está sempre à direita do filho direito. E repare no painel do 6: a rotação acontece na raiz, o 2, e não no pai do novo nó, porque é o 2 o nó mais baixo desequilibrado.

Um rebalanceamento basta

Em cada um dos painéis, houve no máximo uma correção, mesmo quando havia mais de um nó desequilibrado no caminho. Isso não é coincidência.

Proposição 1

Na inserção em uma AVL, depois que o nó desequilibrado mais baixo do caminho é corrigido (com uma ou duas rotações), a subárvore corrigida volta a ter a altura que tinha antes da inserção. Logo, nenhum ancestral precisa de rotação, e cada inserção faz no máximo uma correção.

Demonstraçãotente antes de abrir

Seja o nó desequilibrado mais baixo, com (o caso é simétrico), e o seu filho esquerdo. Primeiro, : a altura de cresceu com a inserção (senão não teria se desequilibrado), e está balanceado. Se as duas subárvores de tivessem a mesma altura depois da inserção, uma delas já teria altura antes, e a altura de já seria : ela não teria crescido.

Seja a altura de , a SAD de . Como , a altura de é depois da inserção, e era antes. Então, antes da inserção, a subárvore com raiz tinha altura .

Caso LL (). A SAE de (a subárvore com raiz na figura) tem altura , e a SAD de , , tem altura . Depois da rotação à direita em , o nó tem como filhos e , os dois com altura : a altura de é e o seu fator é 0. O nó tem como filhos a subárvore de (altura ) e (altura ): a altura de é , e o seu fator é 0.

Caso LR (). A SAD de , com raiz , tem altura , e tem altura . Como está no caminho da inserção e está balanceado, as suas subárvores e têm alturas e , em alguma ordem (ou é o próprio nó novo, com e as duas vazias). Depois das duas rotações, tem como filhos e , e tem como filhos e : as alturas são no máximo , com pelo menos uma igual a em cada lado, então e têm altura e fatores em . A nova raiz tem altura e fator 0.

Nos dois casos, a subárvore volta a ter altura , a mesma de antes da inserção. Os ancestrais de veem, então, as mesmas alturas de antes da inserção, quando estavam balanceados, e continuam balanceados.

O código não precisa saber disso: ele continua chamando balanceia em todos os nós do caminho, e, acima da correção, essas chamadas só recalculam a altura (que não muda) e não encontram nenhum . Na remoção, a história é outra.

Remoção

A remoção também é a da ABB (pelo antecessor, copiando o par chave-valor), com balanceia na volta da recursão.

1
Encontre o nó#
Desça como em uma busca. Se chegar a um NULL, a chave não está na árvore e nada muda.
2
Remova como na ABB#
Com nenhum ou um filho, o nó é liberado e o filho (ou NULL) toma o seu lugar; esse filho já é uma AVL, e é devolvido como está. Com dois filhos, o antecessor (o máximo da SAE) tem a chave e o valor copiados para o nó, e é removido da SAE, recursivamente.
3
Volte rebalanceando#
Na volta da recursão, cada nó do caminho passa por balanceia, como na inserção. Agora, a correção de um nó pode diminuir a altura da subárvore, e o desequilíbrio pode reaparecer em um ancestral: a volta precisa ir até a raiz, e pode haver rotações em vários níveis.

static No *removeNo(No *r, Chave chave, bool *removeu) {
    if (r == NULL)
        return NULL;
    if (chave < r->chave) {
        r->esq = removeNo(r->esq, chave, removeu);
    } else if (chave > r->chave) {
        r->dir = removeNo(r->dir, chave, removeu);
    } else if (r->esq == NULL || r->dir == NULL) {
        /* nenhum ou um filho: o filho (ou NULL) sobe, já balanceado */
        No *filho = r->esq != NULL ? r->esq : r->dir;
        free(r);
        *removeu = true;
        return filho;
    } else {
        /* dois filhos: o antecessor (máximo da SAE) toma o lugar */
        No *ant = r->esq;
        while (ant->dir != NULL)
            ant = ant->dir;
        r->chave = ant->chave;
        r->valor = ant->valor;
        r->esq = removeNo(r->esq, ant->chave, removeu);
    }
    return balanceia(r);                /* na volta da recursão */
}

No caso de dois filhos, a chamada recursiva remove o antecessor da SAE e, na volta, rebalanceia todo o caminho entre r e o antecessor. Depois, o próprio r passa por balanceia, e a recursão continua subindo.

Na remoção aparece o caso que a inserção não tem: o filho do lado alto com fator 0. Na figura, remover o 1 deixa o 2 com , e o seu filho direito, o 4, tem as duas subárvores com a mesma altura.

Três árvores com os fatores anotados. (a) Uma AVL com raiz 2, filho esquerdo 1 e filho direito 4, que tem os filhos 3 e 5. (b) Depois de remover o 1: o 2 tem fator -2 e o 4 tem fator 0, os dois em vermelho. (c) Depois de uma rotação à esquerda em 2: 4 é a raiz, com 2 à esquerda (que tem o filho direito 3) e 5 à direita; os fatores são +1 em 4 e -1 em 2 — Remoção com fb(B) = 0: uma rotação simples resolve, como no caso RR.

Com , uma rotação simples resolve: sobe, a sua SAD sobe junto um nível, e a sua SAE vai para o meio (à direita de ), na mesma profundidade. Como as duas tinham a mesma altura, os fatores finais ficam em , como em (c). Já a rotação dupla não é garantida: dependendo das alturas dentro da subárvore do meio, ela pode deixar com . É por isso que a tabela tem e , e o código testa < 0 e > 0.

Pergunta

Na figura, a altura da árvore antes da remoção era 2 e, depois da rotação, continua 2. Na demonstração da inserção, a correção devolvia a subárvore à altura de antes. Na remoção, o que acontece com a altura da subárvore corrigida nos casos com ? Por que isso obriga a continuar verificando os ancestrais?

Ver dicaEsconder dica

Refaça as contas da demonstração para o caso LL, mas agora com o desequilíbrio causado por uma remoção em : antes da remoção, tinha altura .

Ver respostaEsconder resposta

Com (ou , no caso duplo), a subárvore corrigida termina com altura , como na inserção. Mas, na remoção, a altura antes da operação era ( com e com ): a subárvore ficou mais baixa. O ancestral de vê um dos seus lados diminuir e pode ficar com . Por isso a remoção pode precisar de uma correção em cada nível, até correções. Só com a altura volta ao valor de antes () e o desequilíbrio para ali.

O TAD completo

O programa abaixo usa o TAD AVL completo, com a mesma interface Arvore.h da ABB. Ele insere as chaves de 1 a 8 (a mesma sequência da figura), imprimindo a árvore deitada depois de cada inserção (a raiz fica à esquerda e a SAD em cima), e depois remove o 1 e o 3. Tente prever a árvore depois de cada remoção antes de executar.

TAD Arvore (AVL)C

Pergunta

Remover o 3 dispara uma rotação. Em qual nó, e por quê?

Ver respostaEsconder resposta

Depois de remover o 1, a SAE da raiz 4 é o 2 com o filho direito 3. O 3 é uma folha, e é removido sem rotação no seu pai: o 2 fica com fator 0 e altura 0. A raiz 4 passa a ter a SAE com altura 0 e a SAD (6, 5, 7, 8) com altura 2: . O filho direito, 6, tem fator , então é o caso RR: uma rotação à esquerda em 4, e 6 vira a raiz. A altura da árvore cai de 3 para 2.

A altura de uma AVL

A AVL tem em todo nó, mas isso não a obriga a ser completa. Quão alta ela pode ficar? Na página de árvores binárias, deixamos para esta página a demonstração de que árvores balanceadas têm altura . A estratégia é olhar o problema ao contrário: qual é o menor número de nós de uma AVL de altura ?

Uma AVL de altura com o mínimo de nós tem uma subárvore de altura (senão a altura não seria ) e a outra com a menor altura permitida, , e as duas, por sua vez, também com o mínimo de nós. Essas árvores são chamadas de árvores de Fibonacci, e o motivo do nome aparece já nos números.

As AVL com o menor número de nós para cada altura de 0 a 4: com altura 0, 1 nó; com altura 1, 2 nós; com altura 2, 4 nós; com altura 3, 7 nós; com altura 4, 12 nós. Cada uma é formada por uma raiz com a árvore mínima de altura h-1 de um lado e a de altura h-2 do outro — Árvores de Fibonacci: as AVL mais esparsas de cada altura. 1, 2, 4, 7, 12 são os números de Fibonacci menos 1.

Usamos a sequência de Fibonacci com e : 1, 1, 2, 3, 5, 8, 13, 21, ...

Lema 1

Toda árvore AVL de altura tem pelo menos nós.

Demonstraçãotente antes de abrir

Por indução forte em . Com , a árvore tem 1 nó, e . Com , a árvore tem pelo menos 2 nós (a raiz e um filho), e .

Seja . Uma das subárvores da raiz tem altura . Como na raiz, a outra tem altura ou . As duas são AVL (a condição vale para todo nó). Pela hipótese de indução, a primeira tem pelo menos nós, e a segunda, pelo menos (se a altura dela for , tem pelo menos ). Somando a raiz,

As árvores de Fibonacci da figura atingem esse mínimo, então o lema não pode ser melhorado. Falta saber quão depressa os números de Fibonacci crescem. Seja , a razão áurea, que satisfaz .

Lema 2

Para todo , .

Demonstraçãotente antes de abrir

Por indução forte em . Para , ; para , . Para , pela hipótese de indução,

Teorema 1(Altura da AVL)

Uma árvore AVL com nós tem altura

Em particular, , e a família das árvores AVL é balanceada.

Demonstraçãotente antes de abrir

Pelos dois lemas, , isto é, . Aplicando (que é crescente), . Para a segunda desigualdade, basta trocar a base: , e .

Ou seja, a AVL mais alta possível é no máximo cerca de 44% mais alta que a árvore mais baixa possível, . Com um milhão de chaves, isso dá no máximo 27 níveis abaixo da raiz, contra 19 da árvore completa e 999.999 da ABB degenerada.

Na prática, a AVL costuma ficar bem perto do mínimo. O programa abaixo insere chaves em ordem crescente, o pior caso da ABB, e compara a altura obtida com a mínima e com o limite do teorema.

altura.cC

Pergunta

Com chaves crescentes, a altura da AVL coincidiu com a mínima em todas as linhas. Que tipo de sequência de inserções você usaria para tentar aproximar a altura do limite do teorema?

Ver respostaEsconder resposta

Uma que construa árvores de Fibonacci: cada subárvore precisa ter o mínimo de nós para a sua altura, com uma das subárvores de cada nó um nível mais baixa que a outra. Uma forma é inserir as chaves na ordem de um percurso em largura de uma árvore de Fibonacci já montada (raiz primeiro, depois nível a nível): como cada nó entra depois do pai, nenhuma inserção desequilibra a árvore, e nenhuma rotação muda a forma. Na média, com chaves em ordem aleatória, a altura de uma AVL fica muito próxima de .

Custos

Operação	ABB	AVL
busca	no pior caso
inserção	no pior caso	, com no máximo uma correção (uma ou duas rotações)
remoção	no pior caso	, com até correções
altura da árvore	(percorre a árvore)	(guardada na raiz)
memória extra	nenhuma	um `int` por nó

A busca da AVL é exatamente a da ABB, sem nenhuma mudança: o trabalho todo fica na inserção e na remoção, e a busca colhe o resultado. É por isso que a AVL é uma boa escolha quando há muito mais buscas que alterações. Quando as alterações são frequentes, a rubro-negra, que tolera mais desequilíbrio e faz menos rotações, costuma ser preferida.

Exercícios

Encontre e corrija o erro

Os quatro programas abaixo implementam uma AVL simplificada (só com chaves) e terminam com um relatório: a ordem simétrica, a altura recalculada da árvore (sem usar o campo altura) e se todos os nós têm . Cada um tem um erro diferente.

Programa 1

avl_ordem.cC

Resposta

As rotações atualizam a altura de B antes da de A. Depois da rotação, A é filho de B, então B é recalculado com a altura antiga de A, a de antes da rotação, quando B ainda estava embaixo dele. As alturas guardadas ficam erradas (a raiz diz 9, mas a altura real é 5), e balanceia passa a decidir com fatores errados: a árvore deixa de ser AVL, sem nenhuma mensagem de erro. O nó que desce precisa ser atualizado primeiro:

atualizaAltura(A);
atualizaAltura(B);

Programa 2

avl_igual.cC

Resposta

A função balanceia só trata os casos em que o filho tem fator exatamente ou . Depois de remover o 1, a raiz 2 fica com e o seu filho direito, o 4, com (é a situação da figura da remoção). Nenhum dos quatro if se aplica, e a árvore fica desequilibrada. O caso precisa ser tratado como RR (ou LL), com uma rotação simples:

if (fb > 1) {
    if (fatorBalanceamento(r->esq) < 0)
        r->esq = rotacaoEsquerda(r->esq);
    return rotacaoDireita(r);
}
if (fb < -1) {
    if (fatorBalanceamento(r->dir) > 0)
        r->dir = rotacaoDireita(r->dir);
    return rotacaoEsquerda(r);
}

Programa 3

avl_altura.cC

Resposta

A inserção só chama balanceia quando o nó está desequilibrado. Mas é balanceia que atualiza a altura: nos outros nós, a altura nunca muda e fica 0 para sempre. Com todas as alturas em 0, os fatores são sempre 0 ou , nenhuma rotação acontece, e as chaves crescentes formam uma lista (altura 6 com 7 chaves). Todo nó do caminho precisa ter a altura atualizada na volta da recursão, desequilibrado ou não:

return balanceia(r);

Programa 4

avl_lr.cC

Resposta

O AddressSanitizer acusa um vazamento: um nó alocado em criaNo foi perdido. (Dependendo do ambiente, a saída do relatório pode nem aparecer, porque o programa termina com erro antes de esvaziar o buffer de printf. Se aparecer, ela mostra só 10 30: o 20 sumiu.) A sequência 30, 10, 20 é o caso LR, e balanceia faz a primeira rotação, à esquerda em 10, mas descarta o retorno: r->esq continua apontando para o 10, que agora é filho do 20 e não tem mais filhos. A rotação à direita em 30 sobe o 10, e o 20 fica fora da árvore. O retorno da primeira rotação precisa ser guardado no filho:

r->esq = rotacaoEsquerda(r->esq);

e, no caso RL, r->dir = rotacaoDireita(r->dir);.

Implemente

Os quatro casos. O TAD AVL está pronto, exceto pela função balanceia. Implemente-a usando as funções de ArvoreInterno.h (altura, atualizaAltura, fatorBalanceamento, rotacaoDireita e rotacaoEsquerda). Os testes fazem inserções e remoções e, depois de cada bateria, conferem a ordem das chaves, as alturas guardadas, a condição em todos os nós e os valores. Há testes com os quatro casos, com o caso da remoção e com até 100 mil chaves.

Como organizar balanceia?

A função recebe um nó cujos filhos já estão balanceados e com as alturas corretas. Quais são as decisões, e em que ordem?

Ver dica 1Esconder dica 1

Primeiro, a altura do próprio nó: sem ela, o fator dos ancestrais sai errado. Depois, o fator do nó decide o lado (mais alto à esquerda ou à direita), e o fator do filho desse lado decide se a rotação é simples ou dupla.

Ver dica 2Esconder dica 2

Use a tabela de casos desta página e repare nas linhas com e . E lembre que cada rotação devolve a nova raiz da subárvore.

Os quatro casos de rebalanceamentoC

k-ésima menor chave. Se cada nó guardar também o tamanho da sua subárvore (o número de nós dela), é possível encontrar a -ésima menor chave e o rank de uma chave (quantas chaves da árvore são menores que ela) em , sem percorrer a árvore. Implemente, em ordem.c:

atualiza, que recalcula a altura e o tamanho de um nó a partir dos filhos (ela substitui atualizaAltura em todo o TAD, inclusive nas rotações);
kesimaArvore, que devolve a -ésima menor chave, com de 1 até tamanhoArvore;
rankArvore, que devolve quantas chaves são menores que a chave dada (que pode não estar na árvore).

Os testes conferem os tamanhos guardados depois de rotações, inserções e remoções. O último faz 80 mil rodadas de operações em uma árvore com 50 mil chaves, e uma solução que percorre a árvore em ordem para contar não termina a tempo.

Como descer usando os tamanhos?

Na raiz, quantas chaves são menores que a chave da raiz? Como isso ajuda a decidir para que lado ir?

Ver dica 1Esconder dica 1

Seja o tamanho da SAE da raiz. As menores chaves estão na SAE, a raiz é a -ésima, e o resto está na SAD. Se , desça para a SAE com o mesmo ; se , é a raiz; senão, desça para a SAD procurando a -ésima.

Ver dica 2Esconder dica 2

Para o rank, desça como em uma busca. Cada vez que for para a direita de um nó, todas as chaves da SAE dele e ele próprio são menores que a chave procurada.

Ver dica 3Esconder dica 3

Quando um nó muda de filhos (nas rotações), o tamanho dele muda. Por que é importante que atualiza calcule o tamanho a partir dos filhos, e não somando ou subtraindo 1?

k-ésima menor chaveC

Referências

G. M. Adelson-Velsky e E. M. Landis. An algorithm for the organization of information. Doklady Akademii Nauk SSSR, 146, 1962.
A. Backes. Estrutura de Dados Descomplicada em Linguagem C. Elsevier, 2016.
W. Celes, R. Cerqueira e J. L. Rangel. Introdução a Estruturas de Dados: com técnicas de programação em C. 2ª ed. Grupo GEN, 2016.
T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein. Algoritmos: Teoria e Prática. 3ª ed. Elsevier, 2012. Problemas do capítulo 13 (árvores AVL).
R. Sedgewick e K. Wayne. Algorithms. 4ª ed. Addison-Wesley, 2011. Seção 3.3.
VisuAlgo. Binary Search Tree e AVL Tree.
D. Galles. Visualização interativa de árvores AVL. University of San Francisco.