9 AEDS1 AULA 9 - ÁRVORE

Prévia do material em texto

ÁRVORE
AEDS 1
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 conteúdo de um nó pode ser de qualquer 
tipo que se deseje representar
As árvores da computação têm 
a curiosa tendência de crescer 
para baixo…
CONCEITOS BÁSICOS
Um único nó é uma árvore. Este nó é raiz da árvore.
Suponha que n é um nó e T1, T2, ...,Tk sejam árvores com raízes 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.
EXEMPLO
EXEMPLO
Inteligência Artificial (IA): 
Árvores de Decisão
EXEMPLO
Processamento Digital 
de Imagens (PDI), Visão 
Computacional: Árvore 
denominada Quadtree.
Aplicação Isolamento de 
pontos.
ÁRVORE BINÁRIA
Uma árvore binária é um conjunto finito de elementos que está vazio ou é 
particionado em três subconjuntos disjuntos. 
O primeiro subconjunto contém um único elemento, chamado raiz da árvore. 
Os outros dois subconjuntos são em si mesmos árvores binárias, chamadas 
subárvores esquerda e direita da árvore original. 
Uma subárvore esquerda ou direita pode estar vazia. 
Cada elemento de uma árvore binária é chamado nó da árvore.
ÁRVORE BINÁRIA DE BUSCA
Uma árvore binária de pesquisa é uma 
árvore binária em que cada nó contém 
uma chave de pesquisa e apresenta a 
seguinte propriedade:
Cada nó da subárvore à esquerda tem 
valor da chave menor que a chave do 
nó;
Cada nó da subárvore à direita tem valor 
da chave maior que a chave do nó.
EXEMPLO
Árvore Binária
– Cada nó tem no máximo 
dois filhos.
• Obs: a árvore ao lado não 
impõe nenhuma ordenação 
em seus nodos.
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.
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)
RESUMO DE TERMOS
1. Grau de um nó: é o número de sub-árvores do nó.
2. Grau de uma árvore: é o máximo grau dos nós na árvore.
3. Folhas de uma árvore: são os nós de grau zero.
4. Filhos de um nó X: são as raízes das sub-árvores do nó X. Neste caso X é o 
Pai de seus filhos.
5. Nível de um nó: a raiz da árvore é dita estar no nível zero, se um nó está no 
nível k, seus filhos estão no nível k+1.
6. Altura ou profundidade de uma árvore: é o nível máximo dos nós na 
árvore.
7. Ancestrais de um nó: são todos os nós ao longo do caminho a partir da raiz 
até o nó.
8. Floresta: conjunto de árvores disjuntas.
ÁRVORE BINÁRIA - ESTRUTURA DE DADOS
PROCEDIMENTO DE INSERÇÃO NA ÁRVORE
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.
PROCEDIMENTO DE INSERÇÃO NA ÁRVORE
Algoritmo de inserção de uma chave, key , em uma árvore:
se a árvore é vazia: criar uma nova árvore com a nova chave;
se a chave de busca é menor que a do nó: insere na subárvore da esquerda;
se a chave de busca é maior que a do nó: insere na subárvore da direita.
INSERE ELEMENTO NA ÁRVORE BINÁRIA
RETIRADA DE ELEMENTO OBSERVAÇÕES
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.
REMOÇÃO EM ÁRVORE
REMOÇÃO 
DE NÓ COM 
UM FILHO.
REMOÇÃO 
DE NÓ COM 
DOIS FILHOS
RETIRADA DE UM ELEMENTO DA ÁRVORE
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. 
RETIRA ELEMENTO
OBS: O procedimento 
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.
AJUSTE DA ÁRVORE PARA REMOÇÃO
Quando o registro a ser 
retirado possui dois 
descendentes então retorna 
se para o nó antecessor 
para fazer o ajuste dos 
apontadores no nós filhos 
antes de remover o nó pai.
RETIRADA DE NÓS
CAMINHAMENTO EM ÁRVORE
A ordem dos filhos dos nós em uma árvore pode ser ou não significativa.
Em árvores binárias por exemplo a ordem é significativa.
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.
CAMINHAMENTO EM ÁRVORE
● 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ó.
CAMINHAMENTO EM ÁRVORE
● PRÉ-ORDEM: Caminha visitando primeiro o nó pai 
então segue para o nó filho da esquerda e só então 
visita o nó filho da direita.
● ORDEM CENTRAL: Caminha visitando primeiro os nós 
mais a esquerda, depois os nós pais e então os nós a 
direita
● PÓS-ORDEM: Caminha visitando primeiro os nós da 
esquerda, depois os nós da direita e então os nós 
pais.
CAMINHAMENTO PRÉ-ORDEM
SAÍDA: 1 2 4 7 A B 3 5 6 8 C 9
CAMINHAMENTO EM ÁRVORE PRÉ-ORDEM
CAMINHAMENTO CENTRAL
SAÍDA: A 7 B 4 2 1 5 3 C 8 6 9
CAMINHAMENTO PÓS-ORDEM
SAÍDA:A B 7 4 2 5 C 8 9 6 3 1