Estrutura de dados - Arvores AVL

Estrutura de dados - Arvores AVL

Sucessivas inserções e remoções de nós em uma árvore binária de pesquisa fazem com que existam diferenças entre os níveis das suas folhas, o que acarreta grandes diferenças de performance no acesso a seus nós.

No pior caso, se os dados já estão ordenados, a árvore será uma lista, perdendo toda a eficiência da busca. Nesses casos, diz-se que a árvore ficou degenerada.

Uma árvore é dita balanceada quando, para qualquer nó, as suas sub-árvores à esquerda e à direita possuem a mesma altura. Isso equivale a dizer que todos os ponteiros nulos estão no mesmo nível, ou seja, que a árvore está completa. Isso nem sempre é possível, por conta do número de nós da árvore.

Um critério mais simplificado seria considerar uma árvore balanceada se o número máximo de nós da sub-árvore esquerda diferencie no máximo 1 da sub-árvore direita.

Consiste em construir uma nova versão de uma árvore binária de pesquisa, reorganizando-a. Essa reorganização possui duas etapas:

1. Percurso in-ordem sobre a árvore, para gerar um vetor ordenado com o conteúdo de todos os seus nós.

2. Criação de uma ABP a partir desse vetor, da seguinte forma: a) Identifica-se o nó médio do vetor, que passa a ser considerado a raiz da ABP que está sendo criada. b) Cada uma das metades do vetor é tratada analogamente, de modo que cada nó intermediário será a raiz de uma sub-árvore.

Em 1962, dois matemáticos russos (Adelson-Velskii e Landis) definiram uma nova estrutura para balanceamento de árvores ABP e deram o nome de AVL.

Esta nova estrutura permite o balanceamento dinâmico da árvore e com boa performance.

Fator de Balanceamento (FB) de um nó

É a altura da subárvore direita do nó menos a altura da subárvore esquerda do nó. Inserção AVL:

O que pode acontecer quando um novo nó é inserido numa árvore balanceada? Na árvore abaixo:

- Nós 9 ou 1 podem ser inseridos sem balanceamento. Subárvore com raiz 10 passa a ter uma subárvore e subárvore com raiz 8 vai ficar melhor balanceada.

- Inserção dos nós 1, 3, 5 ou 7 requerem que a árvore seja rebalanceada.

Seja T uma árvore AVL na qual serão feitas inserções de novos nós. Para que a árvore se mantenha AVL (ABP e balanceada), é preciso efetuar operações de rebalanceamento quando necessário.

A idéia consiste em verificar, após cada inclusão, se algum nó ficou desbalanceado, isto é, se a diferença de altura entre as 2 sub-árvores ficou maior do que 1. Em caso afirmativo, aplicam-se as transformações apropriadas para rebalanceálo.

Torna-se então necessário que a estrutura dos nós da árvore contenha mais um campo (bal) além dos já existentes (ESQ, INFO e DIR). Este novo campo armazenará o Fator de Balanceamento (FB) de cada nó.

Veja abaixo como será a estrutura de dados para uma árvore AVL: typedef _ telem; typedef struct no { struct no *esq; telem info; int bal; struct no *dir; } tno; typedef tno *tavl;

Serão utilizadas 4 transformações, indicadas nas figuras dos casos abaixo. Observe que as subárvores T1, T2, T3 e T4 podem ser vazias ou não.

O ponteiro T aponta para o nó raiz p, que é o nó raiz da transformação. Observe que a ordem dos nós no percurso inordem é preservada em todas as rotações, e portanto é possível aplicar qualquer número de rotações sobre uma árvore para torná-la balanceada, sem alterar a ordem dos nós. Ou seja, as transformações preservam a árvore como sendo ABP.

Vamos analisar o que pode ocorrer durante o processo de inserção em uma árvore AVL - e aí vai ficar claro o contexto em que estas transformações são aplicadas.

Suponha que um nó q foi inserido em uma árvore AVL T. Se, após a inserção todos os nós de T permanecem

balanceados, a árvore continua AVL. Caso contrário, seja p o nó mais próximo às folhas de T que ficou desbalanceado (ou seja, o ancestral mais jovem que ficou desbalanceado). Observe que não há ambigüidade na escolha de p, pois qualquer sub-árvore de T que se tornou desbalanceada após a inclusão de q deve necessariamente conter p. Logo, p se encontra no caminho entre q e a raiz de T, e sua escolha é única.

Sejam hE(p) e hD(p) as alturas das sub-árvores esquerda e direita de p, respectivamente. Naturalmente,|hE(p)-

hD(p)| > 1. Então, conclui-se que |hE(p)-hD(p)| = 2, pois T era uma árvore AVL e a inserção de um único nó não pode aumentar a altura de qualquer sub-árvore em mais do que 1. As 4 situações possíveis a serem analisadas são:

Caso 1: hE(p) > hD(p) Seja q o nó que foi inserido na sub-árvore esquerda de p. Além disso, sabe-se que p possui um filho esquerdo u diferente de q (caso contrário, p não teria ficado desbalanceado). Finalmente, por esse mesmo motivo, sabe-se que hE(u) é diferente de hD(u). Neste caso, são duas situações possíveis:

Caso 1.1: hE(u) > hD(u) Esta situação está ilustrada na fig 1(a), sendo q um nó pertencente a T1. Observe que h(T1) - h(T2) = 1 e h(T2)

= h(T3).

fig.1: rotação para a direita

void rot_dir (tavl *T) { tavl u; u = (*T)->esq; (*T)->esq = u->dir; u->dir = *T; (*T)->bal = 0; *T = u; }

Conseqüentemente, uma rotação direita da árvore com raiz p transforma a sub-árvore considerada na árvore da fig.1(b), o que restabelece o balanceamento da sub-árvore em p e, conseqüentemente, da sub-árvore T.

Caso 1.2: hD(u) > hE(u) Neste caso, u possui um filho direito v, e a situação é ilustrada na fig.2(a), sendo que o modulo de h(T2)- h(T3) é menor que 1 e o máximo de h(T2) e h(T3) = h(T1)=h(T4).

fig.2: rotação para a esquerda e em seguida para a direita void rot_esq_dir (tavl *T) { tavl u,v; u = (*T)->esq; v = u->dir; u->dir = v->esq; v->esq = u;

(*T)->bal = 1;
(*T)->bal = 0;
u->bal = 0;

*T = v; }

Aplica-se então a rotação esquerda_direita à raiz p. A nova configuração da árvore aparece em 2(b), e o balanceamento é restabelecido.

Caso 2: hD(p) > hE(p) Ou seja, q foi inserido na subárvore direita de p. Dessa vez, sabe-se que p possui um filho direito u diferente de q (caso contrário, p não teria ficado desbalanceado). Segue que hE(u) é diferente de hD(u), e as duas situações possíveis são:

Caso 2.1: hD(u) > hE(u) Este caso corresponde ao da fig.3(a), sendo q pertencente a T3. As relações de altura são h(T3) - h(T2) = 1 e h(T2) = h(T1).

fig.3: rotação para a esquerda void rot_esq (tavl *T) { tavl u; u = (*T)->dir; (*T)->dir = u->esq; u->esq = *T; (*T)->bal = 0; *T = u; }

Isso significa que a rotação esquerda torna a árvore novamente AVL (fig 3(b)).

Caso 2.2: hE(u) > hD(u) Então, u possui o filho esquerdo v (fig.4(a)). Observe que as alturas da sub-árvores T1, T2, T3 e T4 satisfazem as mesmas relações do caso 1.2. Dessa forma, a aplicação da rotação direita-esquerda torna a árvore novamente AVL (fig.4(b)), ao balancear a sub-árvore com raiz p.

fig.4: rotação para a direita e em seguida para a esquerda void rot_dir_esq (tavl *T) { tavl u,v; u = (*T)->dir; v = u->esq; u->esq = v->dir; v->dir = u;

(*T)->bal = -1;
(*T)->bal = 0;

(*T)->dir = v->esq; v->esq = *T; if (v->bal == 1) else if (v->bal == -1) u->bal = 1; else

u->bal = 0;

*T = v; }

É fácil concluir que o rebalanceamento de p implica também no rebalanceamento de seu nó pai, pois a transformação aplicada diminui em 1 a altura da sub-árvore com raiz em p. Isso assegura o rebalanceamento de todos os nós ancestrais de p, portanto uma única transformação resulta no rebalanceamento de T.

Implementação do procedimento de inserção

Seja T uma árvore AVL, e x a chave a ser incluída em algum novo nó q. O processo pode ser descrito do seguinte modo: Primeiro, busca a chave x. Se ela já está na árvore, nada precisa ser feito. Caso contrário, a busca determina a posição de inserção da nova chave, e a inserção é feita. A seguir, verifica se a inserção desbalanceou algum nó. Em caso negativo, a inserção termina. Caso contrário, é feito o rebalanceamento de T, através de uma das operações de rotação vistas, dependendo do caso.

Para verificar se algum nó de T ficou desbalanceado, vamos utilizar o campo bal existente na estrutura de cada nó. Esse campo armazena, para cada nó v, o valor hD(v) - hE(v). O nó está balanceado se -1 ? v->bal ? 1. O problema é como atualizar este campo de forma eficiente, tendo em vista a inclusão de q. Se q for inserido na subárvore esquerda de v, e esta inclusão ocasionar um aumento na altura desta subárvore, subtrai-se 1 de v->bal. Se esse valor ficar igual a -2, então v ficou desbalanceado. Analogamente, se q for inserido na subárvore direita de v e provocar um aumento na sua altura, adiciona-se 1 a v->bal, e o nó ficará desbalanceado se o valor resultante for 2.

Para completar o processo, precisamos identificar os casos em que a inclusão de q provoca um aumento na altura h(v) da subárvore Tv. Inicialmente, observamos que a inserção do nó q acarreta obrigatoriamente uma alteração na subárvore esquerda ou direita de seu nó pai w. O campo balanço permite avaliar se esta alteração pode ou não se propagar aos outros nós v que estão no caminho entre w e a raiz da árvore.

Suponha que o nó q foi inserido na subárvore esquerda de v. A análise se inicia com v = w e prossegue em seus nós ancestrais, de forma recursiva. O processo é encerrado quando se acha a raiz de uma sub-árvore Tv. que não foi modificada. Três situações distintas podem ocorrer:

Caso A: v->bal=1 antes da inclusão.

Neste caso, v?.bal passa a ser 0, e a altura da subárvore de raiz v não foi modificada. Conseqüentemente, os balanços dos nós no caminho entre v e a raiz não foram alterados.

Caso B: v->bal=0 antes da inclusão. Neste caso, v->bal passa a ser -1, e a altura da subárvore de raiz v foi modificada. Conseqüentemente, os nós no caminho de v até a raiz podem ter seus balanços modificados, e devem ser analisados. Se v é a raiz de T, a análise se encerra, pois nenhum nó ficou desbalanceado. Caso contrário, deve-se repetir o processo substituindo v pelo seu pai.

Caso C: v->bal=-1 antes da inclusão.

Neste caso, v->bal passa a ser -2, e o nó ficou desbalanceado. A rotação correta deve ser aplicada. Qualquer rotação implica em que a subárvore resultante tenha a mesma altura da subárvore antes da inclusão. As alturas dos ancestrais de v não precisam ser avaliadas.

Para uma inserção na subárvore direita de v, casos simétricos devem ser considerados.

A rotina de busca e inserção é dada a seguir. A chamada externa é ins_avl (&T.item), onde: - T é o endereço da raiz da árvore;

- item é a chave a ser inserida; verificação do FB.

Foram criadas duas rotinas auxiliares, caso1 e caso2, para facilitar a implementação.

void caso1(tavl *T) { /* item foi inserido à esquerda de T e causa desbalanceamento FB(T)=-2 */ tavl u; u = (*T)->esq;

rot_dir(&(*T)); /* Caso 1.1 sinais iguais e negativo */
rot_esq_dir(&(*T)); /* Caso 1.2 sinais diferentes */
rot_esq(&(*T)); /* Caso 2.1 sinais iguais e positivo */
rot_dir_esq(&(*T)); /* Caso 2.2 sinais diferentes */

void caso2(tavl *T) { /* item foi inserido à direita de T e causa desbalanceamento FB(T)=2 */ tavl u; u = (*T)->dir; if (u->bal == 1) else

int ins_avl(tavl *T, telem item) { int ok;

*T = (tno *) malloc(sizeof(tno));
if (*T == NULL) return 0;

if (*T == NULL) {

(*T)->info = item;
(*T)->bal = 0;

(*T)->esq = NULL; (*T)->dir = NULL; return 1; }

if ((*T)->info > item) {/* recursividade à esquerda */

ok = ins_avl (&((*T)->esq), item);

switch ((*T)->bal) { /* próxima raiz a se verificar o FB */
case 1 : (*T)->bal = 0; /* era mais alto à direita, fica com FB=0 */
ok = 0; /* interrompe propagação de balanceamento */
break;
case 0 : (*T)->bal = -1; /* ficou com a esquerda maior e propaga FB */
case -1: caso1(&(*T)); /* FB(p)=-2 */
ok = 0;/* nao propaga mais */
break;
}

if (ok) break; }

if ((*T)->info < item) { /* recursividade à direita */

else ok = ins_avl (&((*T)->dir), item); if (ok)

switch ((*T)->bal) { /* próxima raiz a se verificar o FB */
case -1: (*T)->bal = 0; /* era mais alto à esquerda, fica com FB=0 */
ok = 0; /* interrompe propagação de balanceamento */
break;
case 0 : (*T)->bal = 1; /* ficou com a direita maior e propaga FB */
case 1 : caso2(&(*T)); /* FB(p)=2 */
ok = 0;/* nao propaga mais */
break;
}
}
else
ok = 0;

break; return ok; }

Remoção em Árvore AVL

A retirada de um valor de uma Árvore Binária de Busca é mais complexa do que a inserção, porque, enquanto qualquer inserção sempre ocorre numa folha da árvore, uma retirada envolve pelo menos dois casos distintos: os nós com dois filhos e os demais nós. Nas árvores AVL essa dificuldade permanece.

Método manual de remoção de árvore AVL

Inicialmente, faz-se a retirada do nó, usando o algoritmo de busca e retirada de uma ABP. Se não desbalanceou, o processo está encerrado. Se desbalanceou a árvore, isto é, se um ou mais nós ficou com |FB(nó)| > 1, raciocina-se em termos de inserção, perguntando: se o desbalanceamento ocorresse devido a uma inserção, que nó teria sido inserido para causar tal desequilíbrio? Identificado o nó, simula-se sua inserção e faz-se a rotação necessária.

Exemplo 1: dada a árvore abaixo(a), retirando o 5 resulta uma árvore desbalanceada no nó 10(b). A partir daí, raciocina-se como se estivéssemos inserindo: que nó inserido teria causado esse desequilíbrio? o 30. Aplicando os conhecimentos de inserção em árvore AVL, constata-se que uma rotação simples à esquerda resolve o problema. O

resultado está na AVL (c).

Exemplo 2: Retirando a folha 12 de (a), na figura abaixo, desbalanceia a raiz (b); supondo-se a inserção recente de 8, corrige-se o desequilíbrio mediante uma rotação dupla à esquerda (c).

Caso especial: Seja a árvore AVL (a), no desenho abaixo. A retirada da folha 2 desbalanceia a raiz 6 (b). Todavia, essa configuração jamais poderia resultar de uma seqüência de inserções, pois, se ela fosse 8, 12 ou 12, 8, a primeira dessas inclusões provocaria rotação.

Solução: escolhe-se arbitrariamente um desses dois nós, despreza-se o outro (mantendo-o na árvore, obviamente), e simula-se a sua inserção. Escolhemos o 12, que exige uma operação mais simples: rotação simples à esquerda. O resultado é a árvore AVL (c).

Se escolhêssemos o 8, desprezando o 12, a rotação exigida seria dupla à direita, mas chegaríamos, também, a um resultado satisfatório (experimente).

Infelizmente, há situações mais complexas, onde o próprio processo de balanceamento devido a retirada de um nó de uma subárvore, por reduzir a altura desta, pode provocar um novo desequilíbrio na árvore a qual ela pertence.

Então, não resta outra saída senão reaplicar o método para a árvore que desbalanceou. E novo desequilíbrio pode ser provocado mais acima, na estrutura, exigindo novo balanceamento. E assim por diante, até que toda a árvore volte a ser uma AVL.

1. Implemente, em uma biblioteca chamada AVL, o tipo abstrato de dados Árvore AVL, com alocação encadeada dinâmica e tendo como base o tipo inteiro. A biblioteca deve conter, além da estrutura de dados do TAD, as seguintes operações:

a) Criar uma árvore AVL vazia b) Verificar se uma árvore está vazia ou não c) Inserir um novo elemento d) Remover um elemento, dado o seu valor e) Verificar se a uma árvore contém um dado valor, retornando o endereço do nó, caso encontrado, ou nil, caso contrário.

f) Exibir todos os valores de uma árvore g) Esvaziar uma árvore

2. Faça um programa que, utilizando a biblioteca AVL, faça o seguinte:

a) Crie uma árvore AVL T. b) Exiba o seguinte menu de opções:

1 – INSERIR 2 – REMOVER

3 – PESQUISAR 4 – EXIBIR A ÁRVORE 5 – ESVAZIAR A ÁRVORE c) Leia a opção do usuário. d) Execute a opção escolhida pelo usuário.

e) Após a execução de cada opção, o programa deve retornar ao menu para nova opção do usuário ou o encerramento do programa (através da tecla ESC).

Comentários