Estrutura de dados - Árvores Binárias - Aula 10

Prévia do material em texto

Prof. Adriano Teixeira de Souza 
 São estruturas de dados adequadas para a 
representação de hierarquias. 
 
 Uma árvore é composta por um conjunto de 
nós. 
 
 Existe um nó r, denominado raiz, que contém 
zero ou mais subárvores, cujas raízes são 
ligadas diretamente a r. 
 
 A raiz se liga a um ou mais elementos, e cada 
um destes forma uma nova subárvore. Esses 
elementos são seus galhos ou filhos. 
 Fundamentos básicos 
 
◦ GRAU – número de subárvores de um nó. 
 
◦ FOLHA – um nó que possui grau zero, ou seja, 
não possui subárvores. 
 
◦ FILHOS – são as raízes das subárvores de um 
nó. 
 
◦ Nó não terminal é um nó que não é uma folha 
e é diferente da raiz. 
 
 Fundamentos básicos 
 
◦ A altura de uma árvore é o comprimento do 
caminho mais longo da raiz até uma das 
folhas. 
 
◦ Uma árvore nula tem altura 0. 
 
◦ Todos os nós são acessíveis a partir da raiz. 
 
◦ Existe um único caminho entre a raiz e 
qualquer outro nó. 
 
 Formas de representação gráfica 
 Árvore Binária: Uma árvore binária é uma 
árvore que pode ser nula, ou então tem as 
seguintes características: 
 
◦ Existe um nó especial denominado raiz; 
 
◦ Nenhum nó tem grau superior a 2 (dois), isto 
é, nenhum nó tem mais de dois filhos; 
 
◦ Existe um “senso de posição”, ou seja, 
distingue-se entre uma subárvore esquerda e 
uma subárvore direita. 
 
 Atravessamento (ou caminhamento) de árvore 
é a passagem de forma sistemática por cada 
um de seus nós; 
 
 Diferentes formas de percorrer os nós de uma 
árvore: 
 
◦ Pré-ordem ou prefixa (busca em 
profundidade) 
◦ Em ordem ou infixa (ordem central) 
◦ Pós-ordem ou posfixa 
◦ Em nível 
 
 Pré-ordem (prefixa) 
◦ visitar a raiz; 
◦ caminhar na subárvore à esquerda, segundo 
este caminhamento; 
◦ caminhar na subárvore à direita, segundo este 
caminhamento. 
 
 Atravessamento em ordem (infixa) 
◦ caminhar na subárvore à esquerda, segundo 
este caminhamento; 
◦ visitar a raiz; 
◦ caminhar na subárvore à direita, segundo este 
caminhamento. 
 
 Atravessamento pós-ordem (posfixa) 
◦ a) caminhar na subárvore à esquerda, segundo 
este caminhamento; 
◦ b) caminhar na subárvore à direita, segundo 
este caminhamento; 
◦ c) visitar a raiz. 
 
 Atravessamento em nível 
◦ Percorre-se a árvore de cima para baixo e da 
direita para a esquerda. 
 
 
 Árvore Estritamente Binária: 
◦ É uma árvore binária na qual todo nó tem 0 ou 
2 subárvores, ou seja, nenhum nó tem “filho 
único”. 
 
 
 
 Árvore Binária Cheia 
◦ Todos os nós, exceto os do último nível, 
possuem exatamente duas subárvores. 
◦ Uma árvore binária cheia de altura h tem 2h – 
1 nós. 
 
 
 
 
 Árvore Degenerada 
◦ Cada nó possui exatamente um filho, e a 
árvore tem o mesmo número de níveis que de 
nós 
 
 
 
 Uma árvore é denominada árvore binária de 
busca se: 
◦ Todo elemento da subárvore esquerda é 
menor que o elemento raiz; 
 
◦ Nenhum elemento da subárvore direita é 
menor que o elemento raiz; 
 
◦ As subárvores direita e esquerda também são 
árvores de busca binária. 
 Busca 
 
◦ Se o valor for igual à raiz, o valor existe na 
árvore. 
 
◦ Se o valor for menor do que a raiz, então deve 
buscar-se na subárvore da esquerda, e assim 
recursivamente, em todos os nós da 
subárvore. 
 
◦ Se o valor for maior que a raiz, deve-se buscar 
na subárvore da direita, até alcançar-se o nó 
folha da árvore, encontrando ou não o valor 
requerido. 
 
 Inserção 
 
◦ Se a árvore estiver vazia, cria um novo no e 
insere as informações do novo nó. 
 
◦ Compara a chave a ser inserida com a chave 
do nó analisado: 
 
 Se menor, insere a chave na subárvore esquerda; 
 
 Se maior, insere a chave na subárvore direita. 
 
 Inserção 
 
 Exemplo: 
◦ Inserir os seguintes elementos: 7, 13, 20, 4, 1, 
18, 5, 11 . 
 
 
 
 
 
 Remoção 
 
 A remoção de um nó é um processo mais 
complexo. Para excluir um nó de uma árvore 
binária de busca, há de se considerar três 
casos distintos: 
 
◦ Remoção na folha 
 
◦ Remoção de um nó com um filho 
 
◦ Remoção de um nó com dois filhos 
 
 
 
 
 Remoção na folha 
 
◦ A exclusão na folha é a mais simples, basta 
removê-lo da árvore. 
 
 
 
 
 Remoção de um nó com um filho 
 
◦ Excluindo-o, o filho sobe para a posição do 
pai. 
 
 
 
 
 
 Remoção de um nó com dois filhos 
 
◦ Neste caso, pode-se operar de duas maneiras 
diferentes: 
 
 Substitui-se o valor do nó a ser retirado pelo 
valor sucessor (o nó mais à esquerda da 
subárvore direita); 
 
 Substitui-se o valor do nó a ser retirado pelo 
valor antecessor (o nó mais à direita da 
subárvore esquerda) 
 
 
 
 
 Remoção de um nó com dois filhos 
 
◦ Exemplo de remoção substituindo o nó pelo 
seu antecessor. 
 
 
 
 
 Remoção de um nó com dois filhos 
 
◦ Exemplo de remoção substituindo o nó pelo 
seu sucessor. 
 
 
 
 
 Árvore é representada pelo ponteiro para o nó raiz 
 
 
 
 
struct noArv { 
 int info; 
 struct noArv* esq; 
 struct noArv* dir; 
}; 
typedef struct noArv NoArv; 
 Árvore vazia representada por NULL: 
 
 
NoArv* abb_cria (void) 
{ 
 return NULL; 
} 
 Imprime os valores da árvore em ordem crescente, 
percorrendo os nós em ordem simétrica 
 
 
 
 
void abb_imprime (NoArv* a) 
{ 
 if (a != NULL) { 
 abb_imprime(a->esq); 
 printf("%d\n",a->info); 
 abb_imprime(a->dir); 
 } 
} 
 Explora a propriedade de ordenação da árvore 
 Possui desempenho computacional proporcional à 
altura 
 
 
 
 
NoArv* abb_busca (NoArv* r, int v) 
{ 
 if (r == NULL) 
 return NULL; 
 else if (r->info > v) 
 return abb_busca (r->esq, v); 
 else if (r->info < v) 
 return abb_busca (r->dir, v); 
 else return r; 
} 
 recebe um valor v a ser inserido 
 retorna o eventual novo nó raiz da (sub-)árvore 
 para adicionar v na posição correta, faça: 
◦ se a (sub-)árvore for vazia 
 crie uma árvore cuja raiz contém v 
◦ se a (sub-)árvore não for vazia 
 compare v com o valor na raiz 
 insira v na sae ou na sad, conforme o resultado da 
comparação 
 
 
 
 
NoArv* abb_insere (NoArv* a, int v) 
{ 
 if (a==NULL) { 
 a = (NoArv*)malloc(sizeof(NoArv)); 
 a->info = v; 
 a->esq = a->dir = NULL; 
 } 
 else if (v < a->info) 
 a->esq = abb_insere(a->esq,v); 
 else /* v >= a->info */ 
 a->dir = abb_insere(a->dir,v); 
 return a; 
} 
é necessário atualizar os ponteiros para 
as sub-árvores à esquerda ou à direita 
quando da chamada recursiva da função, 
pois a função de inserção pode alterar 
o valor do ponteiro para a raiz da (sub-)árvore. 
Cria 
insere 6 
insere 8 
insere 4 
insere 5 
insere 2 
insere 3 
insere 1 
insere 9 
insere 7 
 recebe um valor v a ser inserido 
 retorna a eventual nova raiz da árvore 
 para remover v, faça: 
◦ se a árvore for vazia 
 nada tem que ser feito 
◦ se a árvore não for vazia 
 compare o valor armazenado no nó raiz com v 
 se for maior que v, retire o elemento da sub-árvore à 
esquerda 
 se for menor do que v, retire o elemento da sub-
árvore à direita 
 se for igual a v, retire a raiz da árvore 
 para retirar a raiz da árvore, há 3 casos: 
◦caso 1: a raiz que é folha 
◦ caso 2: a raiz a ser retirada possui um único filho 
◦ caso 3: a raiz a ser retirada tem dois filhos 
 Caso 1: a raiz da sub-árvore é folha da árvore 
original 
◦ libere a memória alocada pela raiz 
◦ retorne a raiz atualizada, que passa a ser NULL 
 Caso 2: a raiz a ser retirada possui um único filho 
◦ libere a memória alocada pela raiz 
◦ a raiz da árvore passa a ser o único filho da raiz 
 Caso 3: a raiz a ser retirada tem dois filhos 
◦ encontre o nó N que precede a raiz na ordenação 
◦ (o elemento mais à direita da sub-árvore à esquerda) 
◦ troque o dado da raiz com o dado de N 
◦ retire N da sub-árvore à esquerda 
◦ (que agora contém o dado da raiz que se deseja retirar) 
 retirar o nó N mais à direita é trivial, pois N é um nó folha ou 
 N é um nó com um único filho (no caso, o filho da direita 
nunca existe) 
NoArv* abb_retira (NoArv* r, int v) 
{ 
 if (r == NULL) 
 return NULL; 
 else if (r->info > v) 
 r->esq = abb_retira(r->esq, v); 
 else if (r->info < v) 
 r->dir = abb_retira(r->dir, v); 
 else { /* achou o nó a remover */ 
 /* nó sem filhos */ 
 if (r->esq == NULL && r->dir == NULL) { 
 free (r); 
 r = NULL; 
 } 
 /* nó só tem filho à direita */ 
 else if (r->esq == NULL) { 
 NoArv* t = r; 
 r = r->dir; 
 free (t); 
 } 
 /* só tem filho à esquerda */ 
 else if (r->dir == NULL) { 
 NoArv* t = r; 
 r = r->esq; 
 free (t); 
 } 
 /* nó tem os dois filhos */ 
 else { 
 NoArv* f = r->esq; 
 while (f->dir != NULL) { 
 f = f->dir; 
 } 
 r->info = f->info; /* troca as informações */ 
 f->info = v; 
 r->esq = abb_retira(r->esq,v); 
 } 
 } 
 return r; 
}