21-arvores

Prévia do material em texto

Árvores 
Raquel O. Prates 
Gisele L. Pappa 
© R. O. Prates Algoritmos e Estrutura de Dados II 
Conceitos básicos 
 Organiza um conjunto de acordo com uma 
estrutura hierárquica. 
 Contém elementos que são chamados de 
nós 
 O “pai de todos” é a raiz – 1º. da hierarquia 
 O contéudo de um nó pode ser de qualquer 
tipo que se deseje representar 
© R. O. Prates Algoritmos e Estrutura de Dados II 
Definição (Aho, Hopcroft e Ullman - 1983) 
 
 Um único nó é uma árvore. Este nó é raiz da 
árvore. 
 Suponha que n é um nó e T1, T2, ..., Tk sejam 
árvores com raizes n1, n2, ... , nk, 
respectivamente. Podemos construir uma nova 
árvore tornando n a raiz e T1, T2, ...., Tk sejam 
subárvores da raiz. Nós n1, n2, ..., nk são 
chamados filhos do nó n. 
 
© R. O. Prates Algoritmos e Estrutura de Dados II 
Exemplos 
 Inteligência Artificial (IA): Árvores de Decisão 
© R. O. Prates Algoritmos e Estrutura de Dados II 
Exemplos 
 IA, Jogos: Minimax 
© R. O. Prates Algoritmos e Estrutura de Dados II 
Exemplos 
 Processamento Digital de Imagens (PDI), 
Visão Computacional: Árvore denominada 
Quadtree 
© R. O. Prates Algoritmos e Estrutura de Dados II 
Exemplos 
 Compressão de dados: Árvore de Huffman 
© R. O. Prates 
Exemplos de árvores 
 Árvore Patrícia utilizada na Recuperação de 
Informação 
Algoritmos e Estrutura de Dados II 
© R. O. Prates 
Exemplos de árvores 
 Árvore B+ 
 Usada para indexação em memória secundária 
Algoritmos e Estrutura de Dados II 
© R. O. Prates Algoritmos e Estrutura de Dados II 
Exemplo 
• Árvore Binária 
– Cada nó tem no 
máximo dois filhos 
 
• Obs: a árvore ao lado 
não impões nenhuma 
ordenação em seus 
nodos 
 
© R. O. Prates Algoritmos e Estrutura de Dados II 
Caminho 
 Um caminho de ni a nk, onde ni é 
antecedente a nk, é a sequência de nós para 
se chegar de ni a nk. 
 Se ni é antecedente a nk, nk é descendente 
de ni 
 O comprimento do caminho é o número de 
nós do caminho – 1. 
© R. O. Prates Algoritmos e Estrutura de Dados II 
Outros conceitos 
 Nó que não tem antecedente: raiz; 
 Nós que não tem descendentes são 
chamados de folhas. (Os outros são os nós 
internos) 
 A altura de um nó na árvore é o caminho de 
maior comprimento que se pode fazer deste 
nó a uma folha. 
 A altura da árvore é a altura de sua raiz. 
 A profundidade de um nó é o comprimento 
da raiz até o nó (só existe um caminho) 
© R. O. Prates 
 Estrutura de dados: 
 
typedef int TipoChave; 
 
typedef struct { typedef struct No { 
 TipoChave Chave; TipoItem item; 
 /* outros componentes */ Apontador Esq, Dir; 
} TipoItem; } No; 
 
typedef struct No * Apontador; typedef Apontador TipoArvore; 
 
Algoritmos e Estrutura de Dados II 
Árvore Binária 
© R. O. Prates 
Procedimento para Inserir na Árvore 
Algoritmos e Estrutura de Dados II 
 
 Atingir um apontador nulo em um processo de pesquisa 
significa uma pesquisa sem sucesso. 
 
 O apontador nulo atingido é o ponto de inserção. 
 
 Obs. O apontador deve ser passado por referência para 
poder ligar corretamente o novo nodo à árvore. 
 
 
© R. O. Prates 
Procedimento para Inserir na Árvore 
Algoritmos e Estrutura de Dados II 
 
 
void Insere(Registro x, Apontador *p) { 
 if (*p == NULL) { 
 *p = (Apontador) malloc (sizeof(No)); 
 (*p)->Reg = x; 
 (*p)->Esq = NULL; 
 (*p)->Dir = NULL; 
 } 
 else if (x.Chave < (*p)->Reg.Chave) 
 Insere(x, &(*p)->Esq); 
 else if (x.Chave > (*p)->Reg.Chave) 
 Insere(x, &(*p)->Dir); 
 else 
 printf("Erro : Registro ja existe na arvore\n"); 
} 
© R. O. Prates 
Procedimento para Retirar x 
da Árvore 
 Alguns comentários: 
1. A retirada de um registro não é tão simples quanto a inserção. 
2. Se o nó que contém o registro a ser retirado possui no 
 máximo um descendente ⇒ a operação é simples. 
3. No caso do nó conter dois descendentes o registro 
 a ser retirado deve ser primeiro: 
 – substituído pelo registro mais à direita na subárvore 
 esquerda; 
 – ou pelo registro mais à esquerda na subárvore direita. 
 
 
 
Algoritmos e Estrutura de Dados II 
© R. O. Prates 
Exemplo da Retirada de um Registro 
da Árvore 
 
 
 
 
 
 
 
 
 Assim: para retirar o registro com chave 5 da árvore basta 
trocá-lo pelo registro com chave 4 ou pelo registro com chave 
6, e então retirar o nó que recebeu o registro com chave 5. 
 
Algoritmos e Estrutura de Dados II 
© R. O. Prates 
Exemplo da Retirada de um 
Registro da Árvore 
 
void Antecessor(Apontador q, Apontador *r) 
{ 
 if ( (*r)->Dir != NULL) 
 { 
 Antecessor(q, &(*r)->Dir); 
 return; 
 } 
 q->Reg = (*r)->Reg; 
 q = *r; 
 *r = (*r)->Esq; 
 free(q); 
} 
 
Algoritmos e Estrutura de Dados II 
© R. O. Prates 
Exemplo da Retirada de um Registro 
da Árvore 
 void Retira(Registro x, Apontador *p) 
{ Apontador Aux; 
 
 if (*p == NULL) { 
 printf("Erro : Registro nao esta na arvore\n"); 
 } 
 else if (x.Chave < (*p)->Reg.Chave) { 
 Retira(x, &(*p)->Esq); 
 } 
 else if (x.Chave > (*p)->Reg.Chave){ 
 Retira(x, &(*p)->Dir); 
 } 
 
Algoritmos e Estrutura de Dados II 
© R. O. Prates 
Exemplo da Retirada de um Registro 
da Árvore 
 else if ((*p)->Dir == NULL) { 
 Aux = *p; 
 *p = (*p)->Esq; 
 free(Aux); 
 } 
 else if ((*p)->Esq == NULL) { 
 Aux = *p; 
 *p = (*p)->Dir; 
 free(Aux); 
 } 
 else 
 Antecessor(*p, &(*p)->Esq); 
 Algoritmos e Estrutura de Dados II 
© R. O. Prates 
Exemplo da Retirada de um Registro 
da Árvore 
 
 
 
 
Obs.: proc. recursivo Antecessor só é ativado quando 
 o nó que contém registro a ser retirado possui 2 
 descendentes. 
 Solução usada por Wirth, 1976, p.211. 
 
Algoritmos e Estrutura de Dados II 
© R. O. Prates 
Outro Exemplo de Retirada de Nó 
 
 
 
 
Algoritmos e Estrutura de Dados II 
© R. O. Prates 
Outro Exemplo de Retirada de Nó 
 
 
 
 
Algoritmos e Estrutura de Dados II 
© R. O. Prates Algoritmos e Estrutura de Dados II 
Caminhamento 
 A ordem dos filhos dos nós em uma árvore pode ser 
ou não significativa. 
 Exemplos, no heap, a ordem dos filhos não tem significado 
 Outros casos, pode se ter um significado (árvores binárias) 
 
 Considera-se que se a e b são nós irmãos, e a está 
à esquerda de b, então todos seus descendentes 
estão à esquerda de b. 
 
© R. O. Prates Algoritmos e Estrutura de Dados II 
Caminhamento 
 Diversas formas de percorrer ou caminhar em uma 
árvore listando seus nós, as principais: 
 Pré-ordem (Pré-fixada) 
 Central (Infixada) 
 Pós-ordem (Pós-fixada) 
 
 Para todas elas: 
 Se T é uma árvore nula, então a lista é nula. 
 Se T é uma árvore de um único nó então a lista contém 
apenas este nó. 
© R. O. Prates Algoritmos e Estrutura de Dados II 
Pré-Ordem 
 Pré-ordem: lista o nó raiz, seguido de suas 
subárvores (da esquerda para a direita), cada uma 
em pré-ordem. 
 
Procedimento PREORDEM (n: TipoNo); 
Início 
 Lista(n); 
 Para cada filho f de n, da esquerda para direita faça 
 PREORDEM(f); 
Fim 
 
© R. O. Prates Algoritmos e Estrutura de Dados II 
Central 
 Central: lista os nós da 1ª. subárvore à esquerda 
usando o caminhamento central, lista o nó raiz n, 
lista as demais subárvores (a partir da 2ª.) em 
caminhamento central (da esquerda para a direita) 
 
Procedimento CENTRAL (n: TipoNo); 
InícioSe Folha(n) então /* Folha retorna se n é uma folha da árvore 
ou não) 
 Lista(n); 
 Senão 
 CENTRAL (FilhoMaisEsquerda(n)); 
 Lista (n); 
 Para cada filho f de n, exceto o mais à esquerda, da 
esquerda para a direita faça 
 CENTRAL (f); 
Fim; 
 
© R. O. Prates Algoritmos e Estrutura de Dados II 
Pós-Ordem 
 Pós-ordem: Lista os nós das subárvores (da 
esquerda para a direita) cada uma em pós-ordem, 
lista o nó raiz. 
 
Procedimento POSORDEM 
 Início 
 Para cada filho f de n, da esquerda para direita faça 
 POSORDEM(f); 
 Lista(n); 
Fim; 
 
© R. O. Prates 
Análise 
 
 O número de comparações em uma pesquisa com sucesso: 
 melhor caso : C(n) = O(1) 
 pior caso: C(n) = O(n) 
 caso médio : C(n) = O(log n) 
 
 
 
 O tempo de execução dos algoritmos para árvores binárias 
de pesquisa dependem muito do formato das árvores. 
 
Algoritmos e Estrutura de Dados II 
© R. O. Prates 
Análise 
 
1. Para obter o pior caso basta que as chaves sejam 
inseridas em ordem crescente ou decrescente. 
Neste caso a árvore resultante é uma lista linear, 
cujo número médio de comparações é (n + 1)/2. 
2. Para uma árvore de pesquisa aleatoria o número 
esperado de comparações para recuperar um 
registro qualquer é cerca de 1,39 log n, apenas 39% 
pior que a árvore completamente balanceada. 
Algoritmos e Estrutura de Dados II 
© R. O. Prates Algoritmos e Estrutura de Dados II 
Exercício 
 Crie em C a estrutura de uma árvore binária 
cuja informação seja um inteiro. 
 Escreva funções que recebam um ponteiro 
para a raiz da árvore e façam: 
 o caminhamento pré-ordem 
 o caminhamento pós-ordem 
 o caminhamento central 
© R. O. Prates 
Árvores em Computação 
 Diversos tipos de árvore 
 AEDS2 foca em: 
 Árvores digitais 
 Árvore binárias de busca 
 Com balanceamento 
 Sem balanceamento 
 
Algoritmos e Estrutura de Dados II