Estruturas de Dados - Balanceamento Dinâmico, Árvores Genéricas

Prévia do material em texto

Balanceamento Dinâmico, 
Árvores Genéricas
Estruturas de Dados
Profa. Carla Koike
   
Balanceamento Dinâmico
● O balanceamento dinâmico tenta assegurar 
que a árvore permanecerá balanceada cada 
vez que um nó é inserido ou deletado.
● Um dos métodos de balanceamento dinâmico é 
chamado AVL (Adelson­Velskii e Landis)
● A árvore necessita ter os nós alterados para 
incluir o fator de balancemento
   
Balanceamento Dinâmico AVL
● Árvores AVL possuem nós cuja diferença de 
altura entre sub­árvore direita e sub­árvore 
esquerda é de no máximo um nível
● Exemplos de árvores AVL
   
Fator de Balanceamento
● Fator de balanceamento é um número que 
expressa a diferença de altura entre as sub­
árvores de esquerda e direita de um nó
● Em uma árvore AVL, todos os nós devem 
possuir fator de balanceamento igual a 
‣ ­1 (ou ­), caso a sub­árvore da esquerda seja maior
‣ 0, se ambas as sub­árvores tem o mesmo tamanho
‣ +1 (ou +), caso a sub­árvore da direita seja maior
   
Árvores AVL com fator de 
balanceamento
● Árvores alteradas para mostrar somente o fator 
de balanceamento. Cada nó possui os campos 
de informação, apontadores esquerda e direita, 
e um campo para armazenar o fator de 
balanceamento
   
Operações em Árvores AVL
● Inserção:
1. Busca da posição para inserir o novo item
2. Insere o novo item como uma nova folha
3. Atualiza os fatores de balanço que se alteram após 
a inserção
4. Rebalanceia a árvore, se necessário 
   
Inserção e Atualização do Fator de 
Balanceamento
   
Inserção e Atualização do Fator de 
Balanceamento
● Inserção é sempre em nó folha
● Os nós anteriores no caminho da inserção tem 
seu fator de balanceamento atualizado, bottom­
up
● O rebalanceamento somente é necessário para 
o primeiro nó no caminho cujo fator de 
balanceamento for maior que +1 ou menor que 
­1
   
Inserção e Atualização do Fator de 
Balanceamento
   
Inserção e Atualização do Fator de 
Balanceamento
Após  rebalancear,a 
altura da árvore final 
é  igual  a  altura  da 
árvore  inicial.  Isso 
indica que o fator de 
balanceamento  não 
muda  acima  desse 
nó.
   
Rebalanceando a árvore AVL
● Inserindo um nó na sub­árvore esquerda do 
filho a esquerda (ilustração)
– uma rotação a direita
● Inserindo um nó na sub­árvore direita do filho a 
direita
– uma rotação a esquerda
   
Rebalanceando a árvore AVL
● Inserindo um nó na sub­árvore direita do filho a 
esquerda (ilustração)
– uma rotação a esquerda e uma rotação a direita
● Inserindo um nó na sub­árvore esquerda do 
filho a direita
– Uma rotação a direita e uma rotação a esquerda
   
Removendo um nó
1. Busca da posição para remover
2. Remove o item (por fusão ou por cópia)
3. Atualiza os fatores de balanço que se 
alteram após a remoção
4. Rebalanceia a árvore, se necessário
A grande diferença em relação à inserção é 
que talvez seja necessário rebalancear em 
mais de um nível da árvore
   
Atualizando os fatores de 
balanceamento após remoção
● Quando removendo um nó, atualizar o fator de 
balanceamento dos nós do caminho, bottom­up
● Caso o fator de balancemento se torne ­2 ou 
+2, a sub­árvore é balanceada por rotação.
● É necessário continuar atualizando os fatores 
acima dessa sub­árvore e balanceando sempre 
que necessário.
   
Implementando uma árvore genérica a 
partir de uma árvore binária
● Uma árvore genérica pode possuir um número 
arbitrário de filhos por nó: como implementar, 
se não sabemos quantos ponteiros são 
necessários?
● Usamos a mesma estrutura da árvore binária, 
mas como diferentes significados...
   
Árvore Genérica
Ponteiro para nó filho
Nível inferior na árvore
Ponteiro para nó irmão
Mesmo nível na árvore
   
Aplicação – Árvores Genéricas
● Game Trees são árvores que representam as 
possibilidades de jogadas para um jogador a 
partir de um estado do jogo. 
● Os filhos de um nó representam todas as 
possibilidades a partir daquela situação do jogo
● Função Avalia retorna um valor representando 
quão bom um estado do jogo (posição do 
tabuleiro).
   
Implementação
typedef struct No {
     int info;
     struct No *pai;
     struct No *filho;  /* 1o filho */
     struct No *prox;   /* proximo irmao */
} No;
   
Árvore do Jogo da Velha
● A Altura da árvore indica o número de jogadas 
adiante que se deseja prever
● A decisão deve maximizar avalia para o jogador 
e minimizar avalia para o adversário.
   
Árvore do Jogo de Xadrez
● Árvore completa de altura 3 exigiria 10120 nós
● Reduzindo para 5 ou 10 movimentos, em 
profundidade 3 ou 5, o problema fica tratável.
   
Exercícios
● Faça um programa que jogue jogo da velha 
com o usuário.
● Use uma árvore de jogos para decidir o 
próximo movimento do programa
● Cada nó da árvore possui o seguinte tipo:
struct jogada{
char board[3][3];
int turn;
struct jogada*son;
struct jogada *next;
};
   
Continuação
● Cada posição do tabuleiro pode ter os 
seguintes caracteres:
– X, para o usuário
– O, para o programa
– espaço para casa vazia
● turn indica quem é a vez: +1 para o 
computador, ­1 para o usuário (adversário)
● son e next apontam para os outros nós
   
Continuação
● A função de avaliação retorna o valor do 
número de linhas colunas e diagonais abertas 
para o programa menos o número de linhas, 
colunas e diagonais abertas ao adversário
● Cada folha da árvore é atribuído o valor de 
avaliação.
● Um pai da árvore recebe:
– o máximo dos seus filhos se turn for +1
– o mínimo dos seus filhos se turn for ­1