Estruturas de Dados - Busca - Parte 4 (Dibio)

Prévia do material em texto

dibio@unb.br
Assuntos 
● Árvores Binárias de Pesquisa/Busca
– Com Balanceamento
– Exemplos (TADs)
● Aplicações com Árvores Binárias de Pesquisa
● Exemplo de “Backtracking”
● Árvores de Jogos
● Estratégia MiniMax
dibio@unb.br
Árvore Balanceada
dibio@unb.br
Árvore AVL (Adelson, Velskii, 
Landis)
dibio@unb.br
Árvore AVL (Adelson, Velskii, 
Landis)
dibio@unb.br
Exemplo (números do lado do nó 
indicam altura)
88
44
17 78
32 50
48 62
2
4
1
1
2
3
1
1
dibio@unb.br
Exemplo (inserindo em uma 
árvore binária vazia a sequência: 
30, 20, 40, 10, 25,35, 50)
dibio@unb.br
Exemplo (inserindo em uma 
árvore binária vazia a sequência: 
10, 20, 30, 40, 50)
dibio@unb.br
Árvore AVL
dibio@unb.br
Árvore AVL
dibio@unb.br
TAD (Árvore AVL)
dibio@unb.br
Balanceamento
dibio@unb.br
Balanceamento
dibio@unb.br
Funções do TAD (FB e Altura)
dibio@unb.br
Inserção Balanceada
dibio@unb.br
Rotação Simples
dibio@unb.br
Exemplo: Rotação simples à 
esquerda
dibio@unb.br
TAD (Rotação simples à esquerda)
dibio@unb.br
Exemplo: Rotação simples à 
direita
dibio@unb.br
TAD (Rotação simples à direita)
dibio@unb.br
Exemplo: AVL 3, 2, 1, 4, 5, 6,7 ?
dibio@unb.br
Exemplo: AVL 3, 2, 1, 4, 5, 6,7 ?
dibio@unb.br
Exemplo: AVL 3, 2, 1, 4, 5, 6,7 ?
dibio@unb.br
Exemplo: AVL 3, 2, 1, 4, 5, 6,7 ?
dibio@unb.br
Exemplo: AVL 3, 2, 1, 4, 5, 6,7 ?
dibio@unb.br
cont...
dibio@unb.br
cont...
dibio@unb.br
cont...
dibio@unb.br
Rotação Dupla
dibio@unb.br
Rotação Dupla à esquerda
dibio@unb.br
Exemplo: Rotação Dupla à 
esquerda
dibio@unb.br
TAD (Rotação dupla à esquerda)
dibio@unb.br
Rotação Dupla à direita
dibio@unb.br
Exemplo: Rotação Dupla à direita
dibio@unb.br
TAD (Rotação Dupla à direita)
dibio@unb.br
TAD (Rotação)
dibio@unb.br
Exemplo: Rotação Dupla
dibio@unb.br
Exemplo: Rotação Dupla
dibio@unb.br
Exemplo: Rotação Dupla
dibio@unb.br
Exemplo: Rotação Dupla
dibio@unb.br
Exemplo: Rotação Dupla
dibio@unb.br
Exemplo: Rotação Dupla
dibio@unb.br
Exemplo: Rotação Dupla
dibio@unb.br
TAD (Inserção)
dibio@unb.br
Remoção
dibio@unb.br
Remoção: Exemplo
dibio@unb.br
Remoção: Exemplo
dibio@unb.br
Remoção: Exemplo
dibio@unb.br
Remoção: Exemplo
dibio@unb.br
Remoção: Exemplo
dibio@unb.br
Remoção: Exemplo
dibio@unb.br
TAD (Remoção)
dibio@unb.br
Considerações Remoção
dibio@unb.br
TAD (Verifica se árvore é AVL)
dibio@unb.br
Aplicações de Árvores Binárias: 
Exemplos
● Redes de Comunicação de Dados 
– Envio de pacotes ordenados e/ou redundantes
● Compressão e Descompressão de arquivos
– Algoritmo de Huffman
dibio@unb.br
Exemplo: Redes de Comunicação
● Os protocolos dividem as mensagens em pacotes, 
enumeram os mesmos e enviam
● Não há garantia que todos os pacotes chegam
● Novos envios são feitos e podem ocorrer 
duplicatas
dibio@unb.br
Exemplo: Redes de Comunicação
● Como reconstruir portanto a mensagem original 
enviada?
– Descartar os pacotes repetidos
– Ordenar os pacotes
● => Árvore Binária
dibio@unb.br
Exemplo: Redes de Comunicação
dibio@unb.br
Exemplo: Algoritmo
● O primeiro pacote é colocado na raiz da árvore;
– Cada pacote seguinte é comparado com a raiz;
● Se for igual: descarta-se a réplica;
● Se for menor: percorre-se o lado esquerdo;
● Se for maior: percorre-se o lado direito;
– Sub-árvore vazia implica inserção de novo pacote;
– Sub-árvore não vazia implica comparação dos pacotes 
com a mesma;
● Resolve-se ordenação e redundância através das 
propriedades da Árvore e dos Algoritmos de 
percurso.
dibio@unb.br
Exemplo: Huffman para 
Compressão de arquivos
● Ou seja, uma mensagem teria que ter (3 bits para 
cada das letras)x(22+9+10+12+16+8)=231 bits
● Código fixo
dibio@unb.br
Exemplo: Huffman para 
Compressão de arquivos
● Uma árvore binária completa, chamada de árvore 
de Huffman é construída recursivamente a partir 
da junção dos dois símbolos de menor 
probabilidade, que são então somados em 
símbolos auxiliares e estes símbolos auxiliares 
recolocados no conjunto de símbolos. O processo 
termina quando todos os símbolos foram unidos 
em símbolos auxiliares, formando uma árvore 
binária. A árvore é então percorrida, atribuindo-se 
valores binários de 1 ou 0 para cada aresta, e os 
códigos são gerados a partir desse percurso.
dibio@unb.br
Exemplo: Huffman para 
Compressão de arquivos
● Ou seja, a mensagem terá 22x(2bits) + 9x(3bits) 
+10x(3bits) + 12x(3bits) + 16x(2bits) + 8x(3bits)= 
193 bits (comparado com 231?)
dibio@unb.br
Árvores de Jogos e Acompanhamento 
Reverso (“Backtracking”)
● “Backtracking”: técnica algorítmica para pesquisar 
em um grande espaço de busca;
● Em cada ponto da busca há um número de 
escolhas;
● A cada escolha um ponto terminal pode ser 
atingido;
● O “backtracking” consiste em retornar à escolha 
mais recente anterior e avaliar um novo 
caminho/escolha possível.
dibio@unb.br
Ex: Encontrar um caminho em um 
labirinto
● Iniciando em (0,0) há um caminho ligando (0,0) 
até (m-1, n-1) ?
dibio@unb.br
Ex: labirinto
● Se o caminho existir marcar cada nó até o fim.
dibio@unb.br
Há um caminho? (casos base)
● Se (x,y) estiver fora dos limites do labirinto, a 
resposta é NÃO;
● Se (x,y) for um elemento marcado (e.g. parede), 
NÃO;
● Se (x,y) já tiver sido visitado, NÃO;
● Se (x,y) for (m-1, n-1), SIM;
● Como saber se uma célula foi visitada? (marcá-la 
diferentemente de SIM, NÃO)
dibio@unb.br
Passo recursivo (“backtracking”)
● Há um caminho de (0,0) até (m-1, n-1)? 
● Se nenhum desses casos base forem satisfeitos:
– Célula (x,y) já marcada com SIM
– Para cada vizinho de (x,y) 
● Há um caminho do vizinho de (x,y) até (m-1, n-1), 
RESPOSTA SIM
– Caso contrário marcar célula (x,y) como visitada, mas 
diferente de SIM; RESPOSTA NÃO
RECURSÃO
dibio@unb.br
Árvores de Jogos
● Uma estrutura de dados do tipo árvore pode ser 
usada em processos de tomada de decisão, onde a 
partir de uma escolha (opção) diferentes 
possibilidades (caminhos) são seguidos.
dibio@unb.br
Exemplo: Jogo da Velha
● Dois Jogadores (0 e 
X)
● Nove posições 
(3x3)
● Uma jogada por vez
● Vence quem 
preencher uma 
linha, uma coluna, 
ou uma diagonal 
completa
dibio@unb.br
Caso Jogador X comece as 
possibilidades seriam 
dibio@unb.br
Necessariamente deve-se projetar 
uma função que avalia a jogada a 
ser feita
● Uma função avaliarJogada simples poderia ser 
uma que retorne um valor numérico computando: 
o número de linhas, colunas e diagonais que 
permaneceriam abertas ao jogador (X), menos o 
número de posições (linhas, colunas e diagonais) 
abertas ao seu oponente (0)
dibio@unb.br
dibio@unb.br
dibio@unb.br
Estrutura possível (partes)
● A estrutura do nó para o jogo poderia ser algo 
como:
struct noh {
char tabuleiro [3][3];
int jogada;
struct noh *filho;
struct noh *prox;
} ;
typedef struct noh *NOH;
dibio@unb.br
TAD deve incluir pelo menos 
(partes)
● Função para criar estrutura
● Função para liberar memória da estrutura
dibio@unb.br
Funções a construir
– gerarListaNohs /* aceita uma posição do tabuleiro tab e 
retorna um ponteiro para uma lista de nós contendo as 
posições do tabuleiro que podem ser obtidas de tab*/
– avaliarPosicao /*avalia a posição de tabuleiro dessa folha 
para o jogador em questão no momento */dibio@unb.br
Uma função para construir a 
árvore poderia ser (partes)
NOH ConstroiArvore(tab, nivelJog)
char tab[][3];
int nivelJog;
{ int i,j;
NOH *pArvore = (NOH *) malloc(sizeof(NOH));
for (i=0; i<3; ++i)
for (j=0; j<3; ++j)
pArvore-> tabuleiro[i][j] = tab[i][j];
pArvore->jogada=1;
pArvore->filho=NULL;
pArvore->prox=NULL;
expandirNoh (pArvore, 0, nivelJog);
return (pArvore);
}
dibio@unb.br
Estratégia MiniMax
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
Caminho MiniMax (partes)
caminhoMiniMax(pnd, jogador,pMelhor, pValor)
NOH pnd, *pMelhor;
int *pValor;
char jogador;
{ NOH p, pMelhor2;
 int val; 
 if (pnd->filho == NULL) {
 pValor = avaliarPosicao(pnd->tabuleiro, jogador); /* a 
fazer */
 *pMelhor = pnd; }
 else{
 p = pnd->filho;
 caminhoMiniMax(p, jogador, pMelhor, pValor);
 *pMelhor = p;
dibio@unb.br
Cont. Caminho MiniMax (partes)
if (pnd.jogada == -1)
*pValor = -*pValor;
p = p->prox;
while (p != NULL) {
caminhoMiniMax(p, jogador, &pMelhor2, &val);
if (pnd->jogada == -1) val = -val;
if (val > *pValor) {
*pValor = val; *pMelhor = p; }
p = p->prox; }
if (pnd->jogada == -1)
*pValor = -*pValor;
}
}
dibio@unb.br
Referências
● Celes, W.; Cerqueira, R. & Rangel, J.L. 
 Introducão a Estruturas de Dados, Editora 
 Campus (Elsevier), RJ, 2004.
● Cormen, T.; Leiserson, C. & Rivest, R. 
 Algoritmos: teoria e prática, Campus Editora, RJ, 
 2002.
● Tenenbaum, A.; Langsam, Y. & Augenstein, M. 
 Estruturas de Dados usando C, Makron Books, 
 RJ, 1995.
● Ziviani, N. Projetos de Algoritmos com 
Implementações em Pascal e C, Cengage 
Learning, SP, 2004.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70
	Slide 71
	Slide 72
	Slide 73
	Slide 74
	Slide 75
	Slide 76
	Slide 77
	Slide 78
	Slide 79
	Slide 80
	Slide 81
	Slide 82
	Slide 83