Árvores Binárias Equilibradas
• Evitam o pior caso de O ( N )
• Algum overhead na construção
• Alternativa:
– Requilibrar uma árvore, depois de construída
– Usar aleatoriedade
– Usar técnicas especiais de construção (Red-Black, AVL, etc)
1
IAED, 2009/2010
Árvores Binárias Equilibradas
• Equilibra uma árvore
• Utiliza operação de partição para colocar a mediana na raíz
6
link balanceR(link h)
{
if (h->N < 2)
return h;
h = partR(h, h->N/2);
h->l = balanceR(h->l);
h->r = balanceR(h->r);
return h;
}
2
5
4
3
2
1
A
F
E
D
C
B
representado valor de N
IAED, 2009/2010
Árvores Binárias Equilibradas
• Equilibra uma árvore
• Utiliza operação de partição para colocar a mediana na raíz
link balanceR(link h)
{
if (h->N < 2)
return h;
h = partR(h, h->N/2);
h->l = balanceR(h->l);
h->r = balanceR(h->r);
return h;
}
3
6
3
2
1
B
D
F
C
E
2
1
A
IAED, 2009/2010
Árvores Binárias Equilibradas
• Equilibra uma árvore
• Utiliza operação de partição para colocar a mediana na raíz
link balanceR(link h)
{
if (h->N < 2)
return h;
h = partR(h, h->N/2);
h->l = balanceR(h->l);
h->r = balanceR(h->r);
return h;
}
4
6
3
1
A
D
F
B
1
C E
2
1
árvore equilibrada !
IAED, 2009/2010
Aleatoriedade na Inserção
• Se as chaves forem uniformemente distribuídas, um
novo nó fica na raíz com probabilidade 1/ (1 + N )
• Quando se insere um nó, coloca-se na raíz com
probabilidade 1/ (1 + N )
link insertR(link h, Item item)
{
Key v = key(item)
Key t = key(h->item);
if (h == z)
return NEW(item, z, z, 1);
if (rand()< RAND_MAX/(h-N+1))
return insertT(h, item);
if less(v, t)
h->l = insertR(h->l, item);
5
else
h->r = insertR(h->r, item);
(h->N)++;
return h;
}
void STinsert(Item item)
{
head = insertR(head, item);
}
IAED, 2009/2010
Árvores AVL (Adelson-Velskii e Landis)
• BST em que, para cada nó interno, a profundidade
(height) de ambos os filhos difere, no máximo, em 1
3
2
1
12
6
32
0
8
0
2
20
9
18
0
23
1
45
0
0
IAED, 2009/2010
Árvores AVL
• N (h) número mínimo de nós numa árvore AVL com
profundidade h ; fácil verificar que N (1) = 1 e N (2) = 2
• Por definição, N (h) ≥ N (h − 1)
• Considerando que a profundidade dos dois filhos de um
nó difere no máximo em 1, obtemos
N (h) ≥ N (h − 1) + N (h − 2) + 1 ⇒ N (h) ≥ 2 N (h − 2) + 1 ⇒ N (h) > 2 N (h − 2)
•
•
•
•
7
Por indução, obtemos N (h) > 2i N (h − 2i )
Para i = h / 2 − 1 obtemos N (h) > 2h /2
Aplicando logarítmo, obtemos h < 2 log( N (h))
A altura de uma árvore AVL é O(log N )
IAED, 2009/2010
Inserção em Árvores AVL
• Inserção de um elemento pode desequilibrar a árvore
3
2
1
12
8
32
0
8
0
2
20
9
18
0
23
1
45
0
0
IAED, 2009/2010
Inserção em Árvores AVL
• Inserção de um elemento pode desequilibrar a árvore
4
árvore
desequilibrada !
2
3
12
32
0
8
1
2
20
9
18
0
23
1
45
0
0
0
1
9
IAED, 2009/2010
Inserção em Árvores AVL
• Inserir novo elemento, numa folha, como numa BST
normal
• Percorrer o caminho desde a nova folha até à raíz
– Para cada nó encontrado, verificar se as alturas dos dois filhos
(esquerdo e direito) não diferem em mais do que 1
– Se diferirem, equilibrar a sub-árvore com raíz nesse nó,
efectuando uma rotação simples ou uma rotação dupla
• Após equilibrar a sub-árvore com raíz num determinado
nó x, não será necessário equilibrar as sub-árvores com
raíz nos antepassados de x
– Terminar após uma equilibragem, ou quando atingirmos a raíz
10
IAED, 2009/2010
Inserção em Árvores AVL
• Árvore desequilibrada após inserção
4
árvore
desequilibrada !
2
3
12
32
0
8
1
2
20
9
18
0
23
1
45
0
0
0
1
11
IAED, 2009/2010
Inserção em Árvores AVL
• Pode ser necessário equilibrar após a inserção
3
árvore
equilibrada !
2
1
32
8
1
2
0
12
12
0
1
20
1 0
23
45
0
0
9
18
IAED, 2009/2010
Equilibragem de Árvores AVL
• Rotação Simples I
A
B
B
A
C
C
rotação
esquerda
13
IAED, 2009/2010
Equilibragem de Árvores AVL
• Rotação Simples II
C
B
B
A
C
A
rotação
direita
14
IAED, 2009/2010
Equilibragem de Árvores AVL
• Rotação Dupla I
A
A
B
C
C
B
rotação
direita
15
IAED, 2009/2010
Equilibragem de Árvores AVL
• Rotação Dupla I (cont)
A
B
A
C
C
B
rotação
direita, esquerda
16
IAED, 2009/2010
Equilibragem de Árvores AVL
• Rotação Dupla II
C
C
B
A
A
B
rotação
esquerda
17
IAED, 2009/2010
Equilibragem de Árvores AVL
• Rotação Dupla II (cont)
B
C
A
A
C
B
rotação
esquerda, direita
18
IAED, 2009/2010
Remoção em Árvores AVL
• Remoção de um elemento pode desequilibrar a árvore
3
2
1
12
2
19
32
0
8
0
9
20
18
1
45
0
0
IAED, 2009/2010
Remoção em Árvores AVL
• Remoção de um elemento pode desequilibrar a árvore
árvore
desequilibrada !
1
3
2
12
2
20
32
0
8
0
9
20
0
18
0
IAED, 2009/2010
Remoção em Árvores AVL
• Remover um nó como numa BST normal
• Percorrer o caminho desde o nó removido até à raíz
– Para cada nó encontrado, verificar se as alturas dos dois filhos
(esquerdo e direito) não diferem em mais do que 1
– Se diferirem, equilibrar a sub-árvore com raíz nesse nó,
efectuando uma rotação simples ou uma rotação dupla
• Após equilibrar a sub-árvore com raíz num determinado
nó x, poderá ser necessário equilibrar as sub-árvores
com raízes nos antepassados de x
– Terminar apenas quando atingirmos a raíz
21
IAED, 2009/2010
Pesquisa em Árvores AVL
• Pesquisa é realizada como numa árvore BST normal
• Pesquisa não altera a árvore
22
IAED, 2009/2010
Desempenho de Árvores AVL
• Uma equilibragem (rotação dupla ou simples): O(1)
• Pesquisa: O (log N)
– Profundidade é O(log N ) , não é necessário equilibrar
• Inserção: O (log N)
– Procurar a posição para inserir é O (log N)
– Manter equilibrada é O (log N) : subir na árvore e equilibrar 1 vez
• Remoção: O (log N)
– Procurar o elemento a remover é O (log N)
– Manter equilibrada é O (log N) : subir na árvore e equilibrar no
máximo O (log N) vezes
23
IAED, 2009/2010
Árvores Red-Black (RBT) - Propriedades
1.
2.
3.
4.
5.
um nó ou tem côr vermelha ou preta
a raíz tem côr preta
as folhas têm côr preta
os filhos de nós de côr vermelha têm côr preta
todos os caminhos de um nó até qualquer folha contêm
sempre o mesmo número de nós de côr preta
20
12
32
NULL
8
18
NULL
NULL
45
NULL
NULL
NULL
9
24
NULL
NULL
IAED, 2009/2010
Árvores Red-Black
• RBT com N nós internos tem profundidade O(log N )
• h(v) = profundidade da árvore com raíz em v
• bh(v) = número de nós de côr preta no caminho de v para
qualquer folha (sem contar com v, se tiver côr preta);
• Uma árvore com raíz em v tem pelo menos 2bh(v) − 1 nós
internos
• Pelo menos metade dos nós em qualquer caminho da
raíz até às folhas é preto, logo bh(v) ≥ h(v) / 2
n≥2
25
h(v )
2
h (v )
− 1 ⇔ log(n + 1) ≥
⇔ h(v) ≤ 2 log(n + 1)
2
IAED, 2009/2010
Árvores Red-Black
• Equilibrada por construção: o caminho mais longo da
raíz até qualquer folha tem no pior caso comprimento
igual ao dobro do comprimento do caminho mais curto
da raíz até qualquer folha. Porquê ?
• Procura: igual ao procedimento para BST, mas mais
rápido porque a árvore está equilibrada
• Inserção, remoção: mais complexo
26
IAED, 2009/2010
Árvores Red-Black - Inserção
• Inserir um novo nó v, como no caso de uma BST, e
pintá-lo de côr vermelha.
• Após a inserção a RBT pode já não satisfazer as
propriedades. É necessário reparar a árvore,
considerando um conjunto de casos especiais.
27
IAED, 2009/2010
Árvores Red-Black - Inserção
•
v encontra-se na raíz: pintar v de côr preta
20
NULL
28
20
NULL
NULL
NULL
IAED, 2009/2010
Árvores Red-Black - Inserção
• O pai de v tem côr preta: todas a propriedades são
satisfeitas
20
12
32
NULL
8
18
NULL
NULL
45
NULL
NULL
NULL
9
NULL
29
NULL
IAED, 2009/2010
Árvores Red-Black - Inserção
• O pai p e o tio u têm côr vermelha e o avô g tem côr
preta. Mudar cores.
g
g
p
v
1
30
3
2
p
u
4
v
5
1
u
3
4
5
2
IAED, 2009/2010
Árvores Red-Black - Inserção
• O pai p tem côr vermelha, mas o tio u tem côr preta, e v
é o filho do lado esquerdo de p, e p é o filho do lado
esquerdo de g. Aplicar rotação à direita e mudar cores.
p
g
p
v
1
31
3
2
v
u
4
5
1
g
2
u
3
4
5
IAED, 2009/2010
Árvores Red-Black - Inserção
• O pai p tem côr vermelha, mas o tio u têm côr preta, e v
é o filho do lado direito de p, e p é o filho do lado
esquerdo de g. Aplicar rotação à esquerda e aplicar
caso anterior.
g
g
p
v
1
2
32
v
u
4
3
p
5
1
u
3
2
4
5
aplicar de seguida
caso anterior
IAED, 2009/2010
Árvores Red-Black - Remoção
• Trocar o maior elemento da sub-árvore do lado
esquerdo com o elemento a apagar (raíz)
• Apagar o elemento copiado, uma vez que tem no
máximo 1 filho
20
12
32
NULL
8
NULL
18
NULL
45
NULL
NULL
NULL
14
NULL
33
NULL
IAED, 2009/2010
Árvores Red-Black - Remoção
• Trocar o maior elemento da sub-árvore do lado
esquerdo com o elemento a apagar (raíz)
• Apagar o elemento copiado, uma vez que tem no
máximo 1 filho
18
12
32
NULL
8
NULL
20
NULL
45
NULL
NULL
NULL
14
NULL
34
NULL
IAED, 2009/2010
Árvores Red-Black - Remoção
• Trocar o maior elemento da sub-árvore do lado
esquerdo com o elemento a apagar (raíz)
• Apagar o elemento copiado, uma vez que tem no
máximo 1 filho
18
12
32
NULL
8
NULL
20
NULL
45
NULL
NULL
NULL
14
NULL
35
NULL
IAED, 2009/2010
Árvores Red-Black - Remoção
• Trocar o maior elemento da sub-árvore do lado
esquerdo com o elemento a apagar (raíz)
• Apagar o elemento copiado, uma vez que tem no
máximo 1 filho
18
12
32
NULL
8
NULL
14
NULL
NULL
45
NULL
NULL
NULL
necessário
reparar árvore !
36
IAED, 2009/2010
Árvores Red-Black - Remoção
• Trocar o maior elemento da sub-árvore do lado
esquerdo com o elemento a apagar (raíz)
• Apagar o elemento copiado, uma vez que tem no
máximo 1 filho
18
12
32
NULL
8
NULL
14
NULL
NULL
45
NULL
NULL
NULL
reparada !
37
IAED, 2009/2010
Árvores Red-Black - Remoção
• Trocar o maior elemento da sub-árvore do lado
esquerdo com o elemento a apagar (raíz)
• Apagar o elemento copiado, uma vez que tem no
máximo 1 filho
• Casos simples:
– Nó tem côr vermelha. Substituir pelo filho, que tem que têr côr
preta
– Nó tem côr preta e o seu filho vermelha. Pintar o filho de côr
preta
• Casos complexos:
– Tanto o nó como o filho têm côr preta
– Existem 6 casos diferentes.
38
IAED, 2009/2010
Árvores Red-Black - Remoção
s
p
v
sR
sL
p
v
p
sR
sL
39
sL
sR
v
sL
p
s
p
v
sR
v
s
sL
sL
s
sL
v
s
s
sR
sL
v
sR
sR
s
p
s
sR
p
s
p
s
sR
sR
v
IAED, 2009/2010