Estruturas de Dados - Balanceamento Estático de Árvores Binárias

Prévia do material em texto

Balanceamento Estático de 
Árvores Binárias
Estruturas de Dados
Profa. Carla Koike
   
Balanceamento de Árvores
● Eficiência da árvore como estrutura de busca 
depende da disposição de seus elementos!
   
Pior caso: 6 testes!!!!
Pior caso: 3 testes
   
Árvore degenerada em lista!
   
Árvore binária balanceada
● Sub­árvore da esquerda tenha 
aproximadamente a mesma altura da sub­
árvore da direita
   
Árvore binária balanceada
Altura  Nós em um nível Nós em todos os níveis
  1 1   1
  2 2   3
  3 4   7
  4 8     15
 11  1024  2047
 14  8192  16383
  h 2^(h­1) 2^h ­ 1
Número máximo de testes a serem feitos 
para busca!!!
   
Algoritmos para Balanceamento de 
árvore
● Duas estratégias:
– balanceamento estático
● usando vetor
● DSW
– balanceamento dinâmico ou AVL
   
Balanceamento Estático
● O balanceamento estático consiste em destruir a estrutura 
da árvore e reconstruí­la balanceada
● Usando vetor:
– Os dados da árvore são armazenados em um vetor (ou 
lista), ordenados e constrói­se outra árvore, balanceada, a 
partir desse vetor
● DSW:
– Por meios de rotações, a árvore é transformada em 
uma árvore degenerada em lista (backbone) que é, por 
meio de rotações, transformada em uma outra árvore, 
dessa vez balanceada
   
Balanceamento Estático usando 
vetor: gerando o vetor
Vetor ordenado:
['B', 'D', 'K', 'M', 'P', 'R']
   
Balanceamento Estático usando 
vetor: gera árvore balanceada
Vetor ordenado:
['B', 'D', 'K', 'M', 'P', 'R']
Elemento do meio do vetor 
passa a ser a raiz!
   
Balanceamento Estático usando 
vetor: gera árvore balanceada
Vetor ordenado:
['B', 'D', 'K', 'M', 'P', 'R']
Sub­vetor a esquerda passa 
a ser a sub­árvore da esquerda
   
Balanceamento Estático usando 
vetor: gera árvore balanceada
Vetor ordenado:
['B', 'D', 'K', 'M', 'P', 'R']
Sub­vetor a direita passa 
a ser a sub­árvore da direita
   
Balanceamento Estático usando vetor
void GeraVetor(struct tree 
*root, char v[] ){
static int i=0;
 if (root != NULL){
   GeraVetor(root­>Esq,v);
   i++;
   v[i]= root­>info;
   GeraVetor(root­>Dir,v);
 }
}
void DestroiArvore(struct tree 
*root){
if(root !=NULL){
  DestroiArvore(root­>Esq);
  DestroiArvore(root­>Dir);
  free(root);
  }
}
void GeraArvore(int i, int j, 
char v[], struct tree *root)
{
int tmp;
 if( i > j)
    root = NULL;
 else{
    tmp = (i+j)/2;
    Insere(v[tmp],root);
    GeraArvore(i,tmp­1,root­
>Esq,v);
    GeraArvore(tmp+1,j,root­
>Dir,v);
 }
}
   
Balanceamento Estático DSW
● Inicialmente, a árvore é transformada em uma 
árvore degenerada em lista (backbone), por 
meio de rotações.
Rotação a Direita
Rotação a Esquerda
   
Rotação
● Rotações alteram a estrutura da árvore binária
– Especialmente, rotações podem ser utilizadas para alterar a 
altura de uma parte da árvore binária
● Rotações alteram a estrutura local de uma árvore binária
– qualquer rotação afeta somente o nó rotacionado e seus 
filhos imediatos: os pais do nó rotacionado e os filhos de 
seus filhos permanecem inalterados
● Rotações não alteram o ordenamento dentro da árvore 
binária
– O mesmo tipo de busca pode ser feito na árvore, antes e 
depois de uma rotação
   
Rotacionando Nó Filho a direita
Avô
Pai
Filho
NetoL NetoR
   
Rotacionando Nó Filho a direita
Avô
Pai
Filho
NetoL NetoR
Se avô não nulo
­ torna Avô o 
ascendente direto 
do filho
   
Rotacionando Nó Filho a direita
Avô
Pai
Filho
NetoL NetoR
Se avô não nulo
­ torna Avô o 
ascendente direto 
do filho
­ a sub­árvore do 
neto direita torna­
se  a sub­árvore 
esquerda do pai
   
Rotacionando Nó Filho a direita
Avô
Pai
Filho
NetoL NetoR
Se avô não nulo
­ torna Avô o 
ascendente direto 
do filho
­ a sub­árvore do 
neto direita torna­
se  a sub­árvore 
esquerda do pai
­ pai torna­se sub­
árvore direita do 
filho
   
Rotacionando Nó Filho a direita
Avô
Pai
Filho
NetoL NetoR
Avô
Pai
Filho
NetoL
NetoR
   
Criando backbone de árvore 
rotacionando a direita
B tem filho a esquerda? Não
K tem filho a esquerda? Sim, D
Rotaciona D a direita
   
Criando backbone de árvore 
rotacionando a direita
B tem filho a esquerda? Não
K tem filho a esquerda? Sim, D
Rotaciona D a direita
P tem filho a esquerda? Sim, M
Rotaciona M a direita
B
D
K
P
RM
   
Criando backbone de árvore 
rotacionando a direita
B
D
K
P
R
M
B tem filho a esquerda? Não
K tem filho a esquerda? Sim, D
Rotaciona D a direita
P tem filho a esquerda? Sim, M
Rotaciona M a direita
R tem filho a direita? Não
   
Balanceamento Estático DSW
● Inicialmente, a árvore é transformada em uma 
árvore degenerada em lista (backbone), por 
meio de rotações. 
– O(n), pior caso (Qual?)
● A árvore degenerada em lista é transformada 
em outra árvore, desta vez balanceada
   
Criando árvore balanceada do 
backbone
   
Criando árvore balanceada do 
backbone
   
Criando árvore balanceada do 
backbone
   
Criando árvore balanceada do 
backbone
● Se backbone a esquerda, 
são realizadas rotações a 
direita em nós alternados
● Se backbone a direita são 
realizadas rotações a 
esquerda em nós 
alternados
B
D
K
P
R
M
U
   
Criando árvore balanceada do backbone
● Árvore balanceada completa teria altura k  e   2k ­1 
nós em todos os níveis
● Para um backbone com exatos 2k ­1 nós, a cada laço, 
são executadas rotações em nós alternados.
● Se o backbone possui um valor m de nós tal que 2k ­1 
< m <  2k+1 ­1, então
– executa­se inicialmente x rotações, onde                       
x = m ­  (2k ­1)
– e então continua como se um backbone de  2k ­1 nós
   
Criando árvore balanceada do 
backbone
● Árvore com 9 nós: dois a mais que os 7 necessários para 
uma árvore balanceada de altura 3
● Realiza duas rotações inicialmente, e depois realiza 
rotações alternadas a partir da raiz