- Capítulo 7 -

2. Parte: : Árvores de Busca Semibalanceadas -

 

Prof. Dr. Aldo von Wangenheim
Índice:

7.3.1. Algoritmos para Manipulação da Árvore AVL

Estrutura de um nodo na árvore AVL: 
Estrutura nodoAVL {
        info            : tipo_info;
        esq             : *nodoAVL;
        dir             : *nodoAVL;
        alt             : inteiro;
};
O campo alt deve ser atualizado recursivamente quando um nodo for inserido ou deletado.

Para o retorno da altura de uma subárvore necessitamos de uma função especial, já que um nodo pode não ter um ou ambos os filhos (lembre-se que a pesquisa para garantir a condição-AVL é realizada perguntando-se a altura das duas subárvores): 

inteiro altura( subárvore : *nodoAVL )
        início
                se (subárvore for NULO)
                        retorne -1; /* A altura de uma subárvore 
                                       inexistente é definida como -1 */
                senão
                        retorne subárvore->alt;
                fim se
        fim
Além deste, teremos também algoritmos para rotação das subárvores:

7.3.1.1. Algoritmos para efetuar a Rotação Simples

Rotação simples à esquerda:
Esta função será chamada somente se k2 possuir um filho à esquerda.

nodoAVL *simp_roda_esq(k2 *nodoAVL) 

        variáveis locais
                k1 : *nodoAVL;
        início
                k1 <- k2->esq;
                k2->esq <- k1->dir;
                k1->dir <- k2;
                /* atualize alturas */
                k2->alt <- max(altura(k2->esq), altura(k2->dir)) + 1;
                k1->alt <- max(altura(k1->esq), k2->alt) + 1;
                
                retorne k1; /* nova raiz da subárvore */
        fim
A rotação à direita é simétrica e pode ser facilmente implementada. 

7.3.1.2. Dupla Rotação à Esquerda

Esta função será chamada somente se k3 possuir um filho à esquerda e se o filho à esquerda de k3 possuir um filho à direita. Ela realiza a rotação e atualiza as alturas das subárvores rotacionadas.

nodoAVL *dup_roda_esq(k3 : *nodoAVL) 

        início
                /* Rotacione entre k1 e k2 */
                k3->esq <- simp_roda_dir( k3-> esq );
        
                /* Rotaciona entre k3 e k2 */
                retorne ( simp_roda_esq( k3 );
        fim
Da mesma forma que com a rotação simples, a rotação dupla à direita é a operação simétrica da rotação à esquerda e é facilemente implementada. 

7.3.1.3. Inserção em Árvore AVL

nodoAVL *inserçãoAVL(info : tipo_info, arv : *nodoAVL, pai : *nodoAVL)
variáveis
        arv_rodada : *nodoAVL;
início
        se (arv é NULO) então /* Folha: aloca novo nodo */
                arv <- aloca novo nodo;
                se (arv é NULO) então retorne ERRO;
                arv->info <- info;                                      arv->alt <- 0;
                arv->esq <- NULO;                                   arv->dir <- NULO;
        senão
                se (info < arv->info) então
                        arv->esq <- inserçãoAVL(info, arv->esq, arv);
                        se ((altura(arv->esq) - altura(arv->dir) > 1)
                                se (info < arv->esq->info) então
                                        arv_rodada <- simp_roda_esq(arv);
                                senão
                                        arv_rodada <- dup_roda_esq(arv);
                                se (pai->esq = arv) então
                                        pai->esq <- arv_rodada;
                                senão
                                        pai->dir <- arv_rodada;
                                fim se
                        senão
                                 arv->alt <- max( altura(arv->esq), altura(arv->dir)) + 1;
                        fim se
                senão
                        se (info > arv->info) então
                                /* caso simétrico para árvore direita */
                        senão
                                retorne ERRO: ,,chave já está na árvore"
                        fim se
                fim se
        fim se
        retorne arv;
fim

7.3.1.4. Exclusão

A exclusão pode ser implementada utilizando-se o algoritmo de exclusão para a árvore de busca binária dado anteriormente, com apenas algumas modificações:

7.3.1.5. Comentários finais:

A primeira chamada da inserção pode ser feita passando-se um ponteiro nulo como pai da árvore ou então através de uma rotina que tem por objetivo somente chamar a inserçãoAVL da forma adequada: 
nodoAVL *insere( info : tipo_info, arv : *nodoAVL )
        início
                retorne inserçãoAVL( info, arv, NULO );
        fim

7.4. Árvore B

7.4.2. Inserção em uma Árvore-B

O algoritmo de inserção em uma Árvore-B é bastante simples: 0. A inserção é sempre feita nas folhas.

1. Desça a árvore em busca da chave.

2. Verifique se o nó está cheio: se contém 2t-1 chaves.

3. Se o nó estiver cheio:

Exemplo simples: Inserção de ,,U"

7.4.2.1. Seqüência de inserções (exemplo):

Considere a árvore abaixo com t=3:

7.4.3. Remoção em Árvore-B

A remoção é a operação mais complexa em uma árvore-B:

Passos iniciais:

Regras de Remoção (remover a chave K da subárbvore X):

1. Se K está em X e X é folha: Remova

2. Se K está em X e X é um nodo interno:

3. Se K não está em X e X é um nó interno:

7.4.3.1. Exemplo de Exclusão

Considere a árvore abaixo:

* Caso 1: Remoção do F

* Caso 2a: Remoção do M

* Caso 2c: Remover o G

* Caso 3b: Remover D

* Caso 3B: Árvore diminui de altura

* Caso 3a: Remover B

*

7.5. Exercícios

7.5.1 Exercício sobre Árvores de Busca 7.5.2 Trabalho: Árvore de Busca AVL ou B