- 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.
-
* Executa uma rotação entre
um nodo k2 e seu filho da esquerda.
-
* Atualiza as alturas.
-
* Retorna a nova raiz.
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:
-
* Depois de excluir um nodo, tenho de balancear
o nodo que agora ocupa o seu lugar.
-
* Tenho de retornar recursivamente atualizando
a altura das subárvores.
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
-
São árvores de
pesquisa balanceadas especialmente projetadas para a pesquisa de informação
em discos magnéticos e outros meios de armazenamento secundário.
-
Minimizam o número de operações
de movimentação de dados (escrita/leitura) numa pesquisa
ou alteração.
-
O grau de um nó pode ser alto.
-
Podem ser consideradas como uma generalização
natural das árvores de pesquisa binárias.
-
Exemplo:
-
Definição
Uma árvore-B de grau mínimo
t >= 2 é uma árvore com as seguintes propriedades: 1. Cada
nó possui os seguintes campos:
<NChaves,Folha,P1,<K1,PR1>,P2,<K2,PR2>,...,<Kq-1,PRq-1>,Pq>
onde:
K: chaves
Folha: flag indicando se o nó
é folha ou não
q < 2t
Pi: ponteiro para o nó filho
i
PRi: ponteiro para o elemento de dados
na memória ou para um registro em disco onde se encontra a chave
Ki
2. Em cada nó as chaves estão
em ordem crescente.
3. Cada chave Ki separa as subárvores
Pi e Pi+1. As chaves da subárvores Pi são menores do que
Ki e as chaves da subárvore Pi+1 são maiores do que Ki.
4. Existem limites inferior e superior
ao número de chaves em cada nó:
(a) Cada nó, exceto a raiz, contém
no mínimo t-1 chaves (t filhos)
(b) Cada nó pode ter no máximo
2t-1 chaves (2t filhos).
5. Todos os nós-folha estão
no mesmo nível.
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:
3.a. Dividir o nó ao meio.
3.b. Colocar a chave do meio no nó
pai.
3.c. Se este também encher, repetir
o processo recursivamente.
Exemplo simples: Inserção
de ,,U"
7.4.2.1. Seqüência
de inserções (exemplo):
Considere a árvore abaixo com t=3:
-
Inserir Q:
- o nó 5 é dividido em dois
(5 e 7)
- a chave T é movida para o nó
pai
- Q é inserido no nó de
endereço 5
-
Inserir L:
- a raiz está cheia
- a raiz é dividida em dois
nós (1 e 7.
- a árvore cresce em altura
com o deslocamento de P para o
novo nó 9
- Q é inserido no nó
de endereço 3
-
Inserir F:
- o nó 2 está cheio e
é dividido em dois nós (2 e 10)
- a chave C é movida para o
nó pai
- F é inserido no nó
de endereço 10.
7.4.3. Remoção
em Árvore-B
A remoção é a operação
mais complexa em uma árvore-B:
Passos iniciais:
1. Desça a árvore em busca
da chave.
2. Verifique se haverá underflow
(t-1). Se ocorrer, lembre-se que será necessário fundir o
nó com algum irmão, seguindo regras bem definidas.
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:
(a) Se a subárvore Y predecessora
de X possui pelo menos t chaves:
- determine a chave predecessora K' em
Y
- substitua K por K'
- recursivamente exclua K' da subárvore
Y
(b) Se a subárvore Z sucessora
de X possui pelo menos t chaves:
- determine a chave sucessora K' em Z
- substitua K por K'
- recursivamente exclua K' da subárvore
Z
(c) Se as subárvores Y e Z possuem
apenas t-1 chaves:
- funda K e todo o nodo Z em Y
- retire K e o apontador para Z de X
- libere o nó Z
- recursivamente exclua K da subárvore
Y.
3. Se K não está em X e X
é um nó interno:
- determine a raiz Pi[X] da subárvore
que deve conter K
- SE Pi[X] tem apenas t-1 chaves:
(a) Se um dos vizinhos de Pi[X] tem pelo
menos t chaves:
- mova uma chave de X descendo para Pi[X]
- mova uma chave do vizinho de Pi[X] subindo
para X
- mova o apontador apropriado do vizinho
para Pi[X]
- recursivamente exclua K de Pi[X]
(b) Se Pi[X] e seus vizinhos têm
apenas t-1 chaves:
- funda Pi[X]com um dos seus vizinhos
e com a chave Ki de X
- remova o parKi e Pi de X
- libere o nó apontado por Pri
- recursivamente exclua K do nodo em que
foi feita a junção
- SEN[Atilde]O :
Exclua recursivamente K de Pi[X]
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
1. Mostre sob a forma de desenho, tanto
para uma árvore AVL como para uma árvore-B com t=3, os resultados
de:
a) criar uma árvore vazia e inserir
os seguintes elementos nesta ordem: F,S,Q,K,C,L,H,T,V,P,A,B,X,D.
b) excluir desta árvore os elementos
K,C e L.
2. Descubra uma estratégia para
imprimir o conteúdo das árvores acima em ordem alfabética.
Teste os algoritmos preordem, emordem e pósordem nos seus desenhos
e veja se você pode usar um deles. Quais as modificações
necessárias para percorrer uma árvore B?
7.5.2
Trabalho: Árvore de Busca AVL ou B
Implemente uma das duas árvores
de busca semibalanceadas dadas (AVL ou B) em C++. O programa
deverá ser capaz de ler um arquivo ASCII com os seguintes dados
de Locais e seus CEPs, nesta forma: <CEP>|<Logradouro>. O caracter
separador de campos será o caracter ,,|". O arquivo conterá
um local por linha.
Serão fornecidos 3 arquivos com
tamanhos diferentes (Santa Catarina, Distrito Federal e Sao Paulo). Tente
primeiro usar o programa com o menor.
-
As equipes que implementarem árvore
B deverão combinar entre si o grau da árvore, para que cada
equipe implemente uma árvore com grau diferente. O programa deverá,
durante a inclusão e a exclusão escrever em um arquivo os
seguintes dados, em ascii, neste formato: <número
de elementos na árvore> <tempo necessário para efetuar
uma operação de inclusão ou de exclusão>.
IMPORTANTE: O tempo necessário
para ler um dado do arquivo não deverá ser considerado.
-
Ao final o programa deverá chamar o
programa unix gnuplot com o arquivo de tempos como parâmetro para
que um gráfico dos tempos seja mostrado na tela.
-
O programa deverá também listar
todos os nomes em ordem na tela.