Unidade Árvores AVL e Árvores B

Prévia do material em texto

0 
 
 
 
 
 
 
 
 
Unidade I: 
 
Unidade: Árvores AVL 
e Árvores B 
 
 
 
1 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
Unidade: Árvores AVL e Árvores B 
1 – Balanceamento em Árvores de Busca Binária 
 
 Conforme visto anteriormente, a principal vantagem de uma Árvore de 
Busca Binária é a rapidez na busca de elementos pelo fato dos mesmos 
estarem organizados. A cada nível que descemos na busca, apenas uma sub-
árvore é escolhida para a continuação da busca. Desse modo, podemos dizer 
que a maior distância entre a raiz é um nó é sua altura. 
 Uma árvore binária completa é aquela onde todos os nós que não são 
folhas possuem grau 2 e todas as suas folhas estão no mesmo nível, também 
conhecida como árvore simétrica ou totalmente balanceada. Nesse caso, 
sabendo que a altura da árvore é h, a quantidade de nós n é sempre definida 
como: 
 N = 2h+1-1 
 Conseqüentemente, uma árvore binária com n nós tem uma altura 
mínima de log n na base 2, que indica aproximadamente o número máximo de 
comparações (nós acessados) a serem realizadas na busca de um nó. 
 h ~ log2 n 
 Sucessivas inserções e remoções de nós em uma árvore fazem com 
que existam diferenças sensíveis entre os níveis das suas folhas, o que 
acarreta grandes diferenças de desempenho no acesso a seus nós. 
Para melhorar o desempenho de ABB, surge o conceito de árvores 
balanceadas e balanceamento. Uma árvore binária é dita balanceada se, para 
cada nó, as alturas de suas sub-árvores diferem de, no máximo 1. Veja os 
exemplos na figura a seguir: 
 
 
 
2 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
 
1.1 - Balanceamento Estático 
 
 Consiste em construir uma nova versão da ABB, reorganizando-a. Essa 
reorganização possui duas etapas: 
1) Percurso em ordem sobre a árvore: esse percurso tem por objetivo gerar 
um vetor ordenado, com o conteúdo de todos os seus nós ativos. 
2) Criação de uma ABB a partir desse vetor: consiste em identificar o nó 
médio do vetor, que passa a ser considerado a raiz da ABB que está 
sendo criada. Cada uma das metades do vetor é tratada analogamente, 
de modo que cada nó intermediário será a raiz de uma subárvore. 
 
Veja um exemplo, inserindo os valores 85, 42, 70, 63, 90, 55 e 60 
A ABB ficaria: 
 
 
 
3 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
Aplicando o algoritmo de balanceamento estático, primeiro faremos um 
atravessamento em ordem (E-R-D) 
 
42, 55, 60, 63, 70, 85, 90 
 
Agora o elemento central será a nova raiz (63), dividindo em 2 metades, sendo 
que o elemento central de cada uma será inserido do seu lado, assim 
recursivamente. 
 
Note que nossa árvore que tinha altura 5, após balanceamento tem altura 2. 
 
 
1.2) Balanceamento Dinâmico (AVL) 
 
 Em 1962, dois matemáticos Russos G.M. Adelson-Velskki e E.M. Landis 
introduziram um conceito menos rigoroso de árvore balanceada, onde uma 
árvore é assim considerada quando, para cada nó, as alturas das subárvores à 
esquerda e à direita diferem no máximo de 1. A essa diferença chamamos de 
“fator de balanceamento”. Descreveram procedimentos para inserção e 
eliminação de nós nessas árvores: os algoritmos de balanceamento de árvore 
são chamados algoritmos AVL e as árvores são chamadas árvores AVL. 
A cada inserção ou remoção, a árvore é rebalanceada dinamicamente de modo 
a mantê-la balanceada. Para rebalancear uma árvore após uma inserção, são 
utilizadas rotações de subárvores. Existem 4 tipos de rotações: 
 
 
 
 
4 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
a) RSE (Rotação Simples para a 
Esquerda) 
Seqüência: 1-2-3 
 
 
 
b) RSD (Rotação Simples para a Direita) 
Seqüência: 3-2-1 
 
 
 
c) RDE (Rotação Dupla para a 
Esquerda) 
Seqüência: 1-3-2 
 
 
 
d) RDD (Rotação Dupla para a Direita) 
Seqüência: 3-1-2 
 
 
 
 
 
Exemplo 1 
 
O nodo com chave 6.5 desequilibrou a árvore. Com a rotação da subárvore em 
torno do nodo 7, rebalanceamos. Usamos uma rotação simples para a direita. 
 
 
 
 
 
 
 
 
Exemplo 2 
 
 
5 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
Criação de uma árvore AVL com os nos de 1 a 7 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Notadamente verificamos que os nós são capazes de subir de nível em 
uma rotação, portanto, a estrutura de um nó precisa guardar a referência para 
o pai e não somente dos filhos. A classe que abstrai o nó de uma árvore AVL 
pode ser: 
 
 
 
6 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
public class NoAVL { 
 private Object dado; //Dado do nó 
 private NoAVL pai; //Pai do nó 
 private NoAVL esq; //Filho Esquerdo 
 private NoAVL dir; //Filho Direito 
 
 ... 
} 
 
A remoção em árvores AVL segue o mesmo princípio da árvore de 
busca binária, com a diferença que a cada remoção é necessário verificar o 
fator de balanceamento e, se necessário, aplicar uma das rotações. 
 
 
1.3 - Árvores B 
 
 Vimos até agora que a estrutura de árvore de busca binária (ABB) é 
interessante quando desejamos manipular informações. Outra vantagem é que 
com o balanceamento dinâmico das árvores AVL a busca se torna mais 
eficiente, porém ambos trabalham na memória real, que pode ser volátil e ter o 
seu espaço físico limitado, não podendo ser utilizada para grandes quantidades 
de informações e para o armazenamento permanente dessas informações. 
 Ao implementarmos uma ABB ou AVL em memória secundária (disco), 
observamos que os algoritmos de busca já apresentados não são eficientes, 
pois o tempo de acesso a um nó em discos é maior do que se ele estivesse na 
memória. 
 Ao fazermos um acesso a essa estrutura obtemos um nó, ou seja, uma 
chave. Se agruparmos várias chaves dentro de cada nó, obteremos com o 
mesmo acesso várias chaves. Com isso, reduziremos o número de acessos à 
estrutura, e conseqüentemente ao disco, diminuindo assim o tempo de 
pesquisa. Além disso, esse agrupamento faz com que a altura da árvore seja 
reduzida. 
 A implementação com agrupamento de chaves é chamada de “árvore de 
busca M-vias” ou “multivias”. Essa estrutura é uma árvore de grau M. 
 
 
7 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
 A reunião de vários nós de uma árvore binária num único nó com várias 
chaves é chamada de página. 
 Além de considerar o tempo de acesso a cada nó, devemos verificar o 
balanceamento dessa árvore. As árvores M-vias que estão permanentemente 
balanceadas são chamadas árvores B. 
 Diferente das árvores binárias, cada nó em uma árvore B pode ter 
muitos filhos, isto é, o grau de um nó pode ser muito grande. Cada nó de uma 
árvore B é chamado de página. 
Bayer and McGreight, 1972, publicaram o artigo: "Organization and 
Maintenance of Large Ordered Indexes". Em 1979, o uso de árvores-B já era 
praticamente o padrão adotado em sistemas de arquivos de propósito geral 
para a manutenção de índices para bases de dados. 
A maioria dos bancos de dados atuais utiliza Árvores B ou Tabelas Hash 
que veremos na próxima Unidade na criação dos índices dos seus arquivos de 
dados. 
 
 
Agrupamento de chaves da árvorebinária em páginas 
A divisão de uma árvore binária em páginas é ilustrada na figura acima. 
Nessa árvore de 9 páginas, quaisquer dos 63 registros podem ser acessados 
em no máximo 2 acessos. 
Definição: Uma árvore B possui as seguintes propriedades: 
1. Todo o nó X possui os seguintes campos: 
a. n, o número de chaves armazenadas em X; 
b. as n chaves k1, k2...kn são armazenadas em ordem crescente; 
 
 
 
8 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
c. folha, que indica se X é uma folha ou um nó interno. 
2. Se X é um nó interno então ele possui n+1 ponteiros f1, f2...fn+1 para 
seus filhos (podendo alguns serem nulos) 
3. Se ki é alguma chave na sub-árvore apontada por fi, então 
 
4. Todas as folhas da árvore estão na mesma altura (que é a altura da 
árvore). 
5. Existe um número máximo e mínimo de filhos em um nó. Este número 
pode ser descrito em termos de um inteiro fixo t maior ou igual a 2 
chamado grau mínimo. 
a. Todo o nó diferente da raiz deve possuir pelo menos t-1 chaves. Todo o 
nó interno diferente da raiz deve possuir pelo menos t filhos. Se a árvore não é 
vazia, então a raiz possui pelo menos uma chave. 
b. Todo o nó pode conter no máximo 2t-1 chaves. Logo um nó interno pode 
ter no máximo 2t filhos. Dizemos que um nó é cheio se ele contém 2t-1 chaves. 
 
 Dizemos que uma árvore B é de ordem n quando n representa o número 
máximo de filhos de um nó, exceto a raiz. Por exemplo, uma árvore B de ordem 
4 pode conter no máximo oito e no mínimo quatro filhos em cada nó. Porém a 
palavra "ordem" é usada de formas diferentes pelos autores, podendo indicar o 
número máximo de chaves em cada nó, ou até mesmo a ocupação mínima em 
cada nó. 
A estrutura de um nó da árvore B (página) é: 
 
Qtde de 
chaves 
Link 
inicial 
Par 
(chave, 
link) 
Par 
(chave, 
link) 
Par 
(chave, 
link) 
Par 
(chave, 
link) 
Par 
(chave, 
link) 
i L0 X1L1 X2L2 X3L3 ... XiLi 
 
 
 
9 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
 
 
Onde: 
- Xk é a k-ésima chave, sendo 1<=k<=i; 
- Lk é o k-ésimo link, sendo 0<=k<=i; 
- XnLn constituem uma entrada que pode conter um campo de 
informações ou um link para um nó com essas informações 
- L0 aponta para o nó cujas chaves são menores que X1; 
- Ln aponta para o nó cujas chaves são maiores que Xn e menores que 
Xn+1, 0<n<i; 
- Li aponta para o nó cujas chaves são maiores que Xi; 
- I é o número de entradas ativas (ocupadas) de um nó em dado 
momento, ou seja, d<=i<=2d 
- Um nó A é pai de um nó B quando A possui um link Ln para B. 
- Um nó B é irmão de um nó C quando os dois possuem o mesmo nó pai; 
- Um nó B é irmão adjacente de um nó C quando existirem dois links 
adjacentes do nó pai (Ln, Ln+1) apontando para eles e a chave pai é 
aquela que se encontra entre esses dois links. 
 
 A ordem “d” determina as quantidades máxima e mínima de chaves 
dentro de cada nó da árvore B. O número máximo de chaves é estabelecido de 
acordo com o espaço físico disponível para cada nó. O número mínimo de 
chaves é estabelecido para determinar o percentual mínimo de ocupação 
dentro de um nó. 
Bayer e McCreight propuseram que as árvores sejam construídas de 
baixo para cima. As chaves raiz da árvore emergem naturalmente. Uma idéia 
elegante e poderosa. Cada página é formada por uma seqüência de chaves e 
conjunto de ponteiros. 
 
 
 
10 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
1.3.1 - Inserção em uma árvore B 
 
Para inserir um novo elemento em uma árvore B, basta localizar o nó 
folha X onde o novo elemento deva ser inserido. Se o nó X estiver cheio, será 
necessário realizar uma subdivisão de nós que consiste em passar o elemento 
mediano de X para seu pai e subdividir X em dois novos nós com t-1 elementos 
e depois inserir a nova chave. 
Veja o exemplo a seguir, inserindo os elementos de 1 a 8 em uma árvore 
B de ordem 2 (t=2). 
 
 
Veja outro exemplo a seguir: 
 
 
 
 
 
Limite Mínimo  t-1  2-1  1 
Limite Máximo  2t-1  2.2-1  3 
 
 
11 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
Passos para a inserção da chave 80 em uma árvore B com t = 2 
 Se o pai de X também estiver cheio, repete-se recursivamente a 
subdivisão acima para o pai de X. No pior caso terá que aumentar a altura da 
árvore B para poder inserir o novo elemento. 
 Note que diferentemente das árvores binárias, as árvores B crescem 
para cima. A figura a seguir ilustra a inclusão de novos elementos em uma 
árvore B com t=3. 
 
 
Agora vamos criar uma árvore B de ordem 3 passo a passo, com os 
elementos F,S,Q,K,C,L,H,T,V,W,M,R,N,P,A,B,X,Y,D,Z,E 
 
 
 
12 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
 
 
 
 
 
 
 
 
 
 
13 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
1.3.2 - Remoção em uma árvore B 
 
A remoção de um elemento de uma árvore B pode ser dividida em dois 
casos: 
1. O elemento que será removido está em uma folha 
2. O elemento que será removido está em um nó interno. 
 Se o elemento estiver sendo removido de um nó não folha, seu 
sucessor, que deve estar em uma folha, será movido para a posição eliminada 
e o processo de eliminação procede como se o elemento sucessor fosse 
removido do nó folha. 
 Quando um elemento for removido de uma folha X e o número de 
elementos no nó folha diminui para menos que t - 1, deve-se reorganizar a 
árvore B. A solução mais simples é analisarmos os irmãos da direita ou 
esquerda de X. Se um dos irmãos (da direita ou esquerda) de X possui mais de 
t - 1 elementos, a chave k do pai que separa os irmãos pode ser incluída no nó 
X e a última ou primeira chave do irmão (última se o irmão for da esquerda e 
primeira se o irmão for da direita) pode ser inserida no pai no lugar de k. 
 
 
 
Passos para a remoção da chave 80 em uma árvore B com t = 2 
 Se os dois irmãos de X contiverem exatamente t - 1 elementos 
(ocupação mínima), nenhum elemento poderá ser emprestado. Neste caso, o 
nó X e um de seus irmãos são concatenados em um único nó que também 
contém a chave separadora do pai. 
 
 
14 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
 
 
 
Passos para a remoção da chave 70 em uma árvore B com t = 2 
 Se o pai também contiver apenas t - 1 elementos, deve-se considerar os 
irmãos do pai como no caso anterior e proceder recursivamente. No pior caso, 
quando todos os ancestrais de um nó e seus irmãos contiverem exatamente t - 
1 elementos, uma chave será tomada da raiz e no caso da raiz possuir apenas 
um elemento a árvore B sofrerá uma redução de altura. 
 A figura a seguir ilustra a remoção de elementos em uma árvore B com 
t=3. 
 
 
 
15 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
 
 
 
 
16 
 
U
n
id
a
d
e
: 
Á
rv
o
re
s
 A
V
L
 e
 Á
rv
o
re
s
 B
 
 
Referências 
 
MAIN, M. Data Structures & Other Objects Using C++. 3. ed. Boston: 
Pearson Education., 2005. 
DROZDEK, A. Estrutura de Dados e Algoritmos em C++. Sao Paulo: 
Pioneira Thomson Learning, 2005. 
PENTON, R. DataStructures For Game Programmers. Ohio, Usa: Focal 
Press, 2003. 
http://www.lcad.icmc.usp.br/~nonato/ED/B_arvore/btree.htm 
SZWARCFITER, Jayme Luiz, Estruturas de Dados e Seus Algoritmos, LTC, Rio 
de Janeiro, 1994 
 
17 
 
Responsável pelo Conteúdo: 
Prof. Ms. Amilton Sousa Martha 
 
Revisão Textual: 
Prof. Ms. Rosemary Toffolli 
 
 
 
 
 
 
 
 
 
www.cruzeirodosul.edu.br 
Campus Liberdade 
Rua Galvão Bueno, 868 
01506-000 
São Paulo SP Brasil 
Tel: (55 11) 3385-3000