Árvores Balanceadas
Tempo de busca numa Árvore Binária de Busca
depende da profundidade da árvore
8
1
4
2
12
6
2
3
4
1
3
5
10
7
9
14
11
13
15
Com 4 nós precisa de 4 comparações
Com 15 nós precisa de 4 comparações
CAP-223
Árvores Balanceadas (cont.)
A geração de uma Árvore Binária de Busca não
garante que o resultado seja eficiente para a busca
1
2 5 10 7 1 6 8 4 3 9
2
9
1 9 7 2 8 10 4 3 6 5
1
5
7
10
2
4
8
10
4
3
7
6
3
6
8
9
5
CAP-223
Árvores Balanceadas (cont.)
6 7 8 3 4 9 2 5 10 1
6 10 3 5 9 1 4 2 8 7
6
6
3
3
2
1
10
7
4
8
5
2
9
10
9
5
1
8
4
7
CAP-223
Árvores Balanceadas (cont.)
O ideal é sempre ter uma Árvore Binária completa.
Mas nem sempre isso é possível.
Árvore não é balanceada
A melhor estrutura, para uma árvore parcialmente
preenchida, é aquela onde TODOS OS NÍVEIS
estão preenchidos exceto o último nível que pode
não ter algumas folhas
CAP-223
Árvores Balanceadas (cont.)
Conhecimento a priori dos dados é uma boa ajuda.
Não é sempre o caso.
Mas nas operações de inserção e remoção, a
eficiência na busca deve ser mantida. COMO?
Duas categorias de árvores:
Árvores Height-Balanced (1962)
 AVL (G. Adel’son-Vel’skii e E. Landis)
Árvores Multiway
 B-trees e sua generalização a-b trees
CAP-223
Árvores Balanceadas (cont.)
Altura de um nó
Comprimento do caminho mais
longo do nó até folha
CAP-223
Height-Balanced trees
Para cada nó, as alturas das suas sub-árvores
diferem no máximo em 1. Também são chamadas
de árvores AVL e esta diferença é o fator de
balanceamento.
5
6
10
2
1
4 7
3
6
12
1
8
5
2
11
9
8
4
3
7
9
10
CAP-223
Height-Balanced trees (cont.)
Convenções usadas para o Fator de Balanceamento
[/] ou [ -1], sub-árvore à esquerda tem altura maior
[\] ou [+1], sub-árvore à direita
tem altura maior
[-] ou [0], sub-árvores possuem a mesma altura
0
0
+1
0
+1
-1
0
0
0
0
0
CAP-223
Height-Balanced trees (cont.)
Exemplo de uma árvore que não está balanceada
pela altura.
O nó marcado viola a condição de balanceamento
6
4
8
5
9
10
CAP-223
Height-Balanced trees (cont.)
Operações aplicadas para reestruturar AVLs
depois de serem “bagunçadas” devido à
inserção e remoção
Rotação (rotation)
Rotação Dupla (double rotation)
Árvore dividida em sub-árvores e reconstrui
numa maneira diferente
CAP-223
Height-Balanced trees (cont.)
Três propriedades de balanceamento:
[-]horizontal
[/]inclinação à esquerda (left-leaning)
[\]inclinação à direita (right-leaning)
CAP-223
Height-Balanced trees (cont.)
a
x
b
1
2
y
z
b
a
x
y
z
CAP-223
Height-Balanced trees (cont.)
a
c
b
1
2
W
x
Z
b
Y
a
c
x
W
Y
Z
CAP-223
Height-Balanced trees (cont.)
Processo de Inserção
novo elemento inserido na árvore
condição de balanceamento do novo nó a partir do novo nó
•caminhe até a raiz passando a informação que
a altura da sub-árvore do nó inserido aumentou
em 1
em cada nó no caminho uma operação
baseada em algumas regras é realizada
CAP-223
Height-Balanced trees (cont.)
As regras dependem de:
condição de balanceamento do nó
(encontrado no caminho) antes da
inclusão do novo elemento
direção do acesso a esse nó
(esquerda ou direita)
CAP-223
Height-Balanced trees (cont.)
Regra I1
SE ( nó atual tem a condição de balanceamento
horizontal[-] )
{
mude para [\] se acessou pelo lado direito
mude para [/] se acessou pelo lado esquerdo
SE ( nó é raiz ) FIM
SENÃO continue subir
}
CAP-223
Height-Balanced trees (cont.)
Regra I2
SE ( nó atual tem a condição de balanceamento
[/] ou [\] )
{
SE ( acesso via sub-árvore que era
mais baixa antes da inserção do nó)
{
mude para [-]
FIM
}
}
CAP-223
Height-Balanced trees (cont.)
1
Insere 0
1
2
Antes da inserção do novo nó 0
a sub-árvore à esquerda era mais
baixa que o da direita (Não havia
sub-árvore à esquerda)
2
0
1
0
2
CAP-223
Height-Balanced trees (cont.)
Regra I3
SE ( nó atual tem a condição de balanceamento
[/] ou [\] )
{
SE ( acesso via sub-árvore que era
mais alta antes da inserção do nó)
{
// condição de balanceamento violada
restaura o balanceamento
}
}
CAP-223
Height-Balanced trees
(cont.)
2
2
Insere 4
1
1
5
5
3
3
4
2
Antes da inserção do novo nó 4
a sub-árvore à esquerda era mais 1
alta que o da direita (Não havia
sub-árvore à direita)
5 BALANCEAR
3
4
CAP-223
Height-Balanced trees (cont.)
Como restaurar a condição de balanceamento?
SE os últimos dois passos vieram da mesma
direção (os dois de esquerda ou os dois de
direita) ENTÃO aplica rotação
SE os últimos dois passos vieram de direções
opostas (um de esquerda e outro de direita OU
um de direita e outro de esquerda) ENTÃO
aplica rotação dupla
CAP-223
Height-Balanced trees (cont.)
1
1
1
2
5
2
rotação
2
1
2
5
5
2
2
2
3
rotação
dupla
4
1
5
3
1
5
1
3
4
3
5
4
CAP-223
Height-Balanced trees (cont.)
Processo de Remoção
um elemento é removido da árvore
a partir do nó removido
•caminhe até a raiz passando a informação que
a altura da sub-árvore do nó removido diminuiu
em 1
em cada nó no caminho uma operação
baseada em algumas regras é realizada
CAP-223
Height-Balanced trees (cont.)
As regras dependem de:
condição de balanceamento do nó
(encontrado no caminho) antes da
remoção do elemento
direção do acesso a esse nó
(esquerda ou direita)
CAP-223
Height-Balanced trees (cont.)
Regra D1
SE ( nó atual tem a condição de balanceamento
horizontal[-] )
{
mude para [\] se acessou pelo lado direito
mude para [/] se acessou pelo lado esquerdo
}
CAP-223
Height-Balanced trees (cont.)
Regra D2
SE ( nó atual tem a condição de balanceamento
[/] ou [\] )
{
SE ( acesso via sub-árvore que era
mais alta antes da remoção do nó)
{
mude para [-]
continue a caminhar para cima com a
mensagem que a sub-árvore do nó
encurtou
}
}
CAP-223
Height-Balanced trees (cont.)
Regra D3
SE ( nó atual tem a condição de balanceamento
[/] ou [\] )
{
SE ( acesso via sub-árvore que era
mais baixa antes da remoção do nó)
{
// condição de balanceamento violada
restaura o balanceamento (3 casos)
}
}
CAP-223
Height-Balanced trees (cont.)
Caso 1
b
a
rotação
a
b
Z
X
X
Z
Y
Y
CAP-223
Height-Balanced trees (cont.)
Caso 2
b
a
rotação
a
b
Z
Y
X
X
Y
Z
CAP-223
Height-Balanced trees (cont.)
Caso 3
c
b
rotação dupla
a
a
Z
b
W
W
X
c
X
Y
Z
Y
CAP-223
Multiway Trees
•Número variável de filhas
•Devido ao interesse em manter as
árvores balanceadas, tem que adicionar
algumas restrições
Restrições
Folhas na mesma profundidade
Limitação no número de filhas
limite inferior a
limite superior b
exemplo (2,3) trees
nós com 2 ou 3 filhas
CAP-223
Multiway Trees
Definição de árvore-(a,b):
•Elementos xi com ordenação  definida
•a e b são inteiros tal que 2  a e (2a-1)  b
•c(N) é número de filhas do nó N
•todas as folhas no mesmo nível
•2  c(raiz)  b
•a  c(N)  b, para  N que não seja raiz
Árvores-(a,b) com b = 2a - 1

B-trees
CAP-223
Multiway Trees (cont.)
Os nós que não são folhas são considerados
nós internos.
Nó interno com k filhas possui k-1 elementos
ou chaves tal que x1 < x2 < ... < xk-1
Árvores que correspondem às k filhas são
T1, T2, ..., Tk
y  xi para todos os elementos y na T1 ... Ti
xi  z para todos os elementos z na Ti+1 ... Tk
CAP-223
Multiway Trees (cont.)
Os algoritmos operam nos nós internos e
ignoram as folhas. As folhas são entidades
fictícias.
Na verdade as folhas são arquivos físicos
com todos os registros cujo as chaves estão
localizadas nos nós internos
CAP-223
Multiway Trees (cont.)
19
11 15
2 5 7
1214 1618
273645
20 222526 3033
3739 485766
Exemplo de Árvore (3,5)  B-Tree
CAP-223
Multiway Trees (cont.)
Nó 19 aponta para 2 nós [nó 11-15 e nó 27-36-45]
Nó 11-15 aponta para 3
Nó 27-36-45 aponta para 4
CAP-223
Multiway Trees (cont.)
Operação de Inserção
Separação dos nós
Operação de Remoção
Junção dos nós
CAP-223
Multiway Trees (cont.)
A operação de inserção começa a partir de uma
procura, até a FOLHA, sem sucesso do nó a ser
inserido  O NÓ NÃO ESTÁ NA ÁRVORE
A chave a ser inserida começa no pai da FOLHA.
Processo de inserção depende se o Nó possui
MENOS que (b-1) elementos. Neste caso, o elemento
x é inserido.
Caso contrário há a necessidade de uma cisão
(split)
CAP-223
QuadTrees
Usadas muito para armazenamento de imagens
1
0
2
3
CAP-223