balanceamento DSW

Prévia do material em texto

ECOI08 – Balanceamento e 
DSW
Prof. Rafael Santos
Email: rsantos@unifei.edu.br
Balanceando uma árvore binária
◼ Uma das grandes vantagens das árvores
◼ possuir um processo de busca rápido
◼ depende muito de como é a árvore.
◼ Para garantir que todos os nós da árvore
possuem um “processo de busca rápido”
precisamos que a árvore esteja balanceada.
◼ Uma árvore binária é balanceada em altura
ou simplesmente balanceada se:
◼ a diferença na altura de ambas as subárvores de
qualquer nó na árvore é zero ou um.
Balanceando uma árvore binária
Altura Nós em um nível Nós em todos os níveis
1 20 = 1 1 = 21 – 1
2 21 = 2 3 = 22 – 1
3 22 = 4 7 = 23 – 1
4 23 = 8 15 = 24 – 1
: : :
11 210 = 1024 2047 = 211 – 1
: : :
14 213 = 8192 16383 = 214 – 1
: : :
h 2h-1 n = 2h – 1
: : :
Balanceando uma árvore binária
◼ Baseado na técnica de pesquisa
binária
1. Armazene os dados em um vetor
2. Ordene o vetor
3. Designe para a raiz o elemento do meio
do vetor
4. Agora o vetor tem duas submatrizes,
refaça o passo 3 e 4 para cada submatriz
até que todos os elementos tenham sido
utilizados
Balanceando uma árvore binária
void balancear (TipoNo dados[], int primeiro, int ultimo, 
TipoApontador &p){
if(primeiro <= ultimo) {
int meio = (primeiro + ultimo)/2;
insere(dados[meio],p);
balancear(dados, primeiro, meio-1, p);
balancear(dados, meio+1, ultimo, p);
}
}
Baseado na técnica de pesquisa binária 
Balanceando uma árvore binária
◼ Baseado na técnica de pesquisa binária
 Este algoritmo tem um sério inconveniente:
 todos os dados precisam ser armazenados em
um vetor antes de construir a árvore.
 O algoritmo não é muito interessante em
árvores dinâmicas pois teríamos que destruir
e reconstruir a árvore a cada nova inserção.
◼ Neste caso não seria necessário o uso de
métodos de ordenação, basta utilizar o percurso
em in-ordem.
Balanceando uma árvore binária
◼ O Algoritmo DSW
 Foi idealizado por Colin Day e melhorado por 
Quentin F. Stout e Bette L Warren.
◼ O algoritmo DSW (2 passos)
1. Transfigura uma árvore binária arbitrária em uma
árvore parecida com lista ligada (espinha dorsal).
2. Então, essa árvore alongada é transformada em
uma série de passes em uma árvore perfeitamente
balanceada, girando repetidamente cada segundo
nó da espinha dorsal ao redor de seu ascendente.
Balanceando uma árvore binária
◼ O Algoritmo DSW
 O essencial para as transformações de 
árvores nesse algoritmo é a rotação.
◼ Há dois tipos de rotação simétricas
 A esquerda
 A direita.
Balanceando uma árvore binária
◼ O Algoritmo DSW
◼ A rotação à direita do nó Ch com relação ao seu ascendente
Par é realizada de acordo com o seguinte algoritmo:
RotateRight (Gr, Par, Ch)
if Par não é a raiz da árvore //isto e, se Gr não e nulo
o avô Gr do filho Ch se torna o ascendente de Ch´s substituindo Par;
a subárvore direita de Ch se torna a árvore esquerda do ascendente Par de Ch;
o nó Ch obtém Par como seu filho direito; 
Gr
Par
Ch R
P Q
Gr
Par
Ch
R
P
Q
Balanceando uma árvore binária
◼ Primeira Fase (espinha dorsal)
createBackbone(root, n)
tmp = root;
while (tmp != 0)
if tmp tem um filho esquerdo
gire esse filho ao redor de tmp;
ajuste tmp para o filho que se tornou o ascendente;
else
ajuste tmp para o filho direito;