DAS 5102 – Fundamentos da Estrutura da Informação
Árvores
Prof. Dr. rer. nat. Daniel Duarte Abdala
1
Motivação
• Estrutura de dados muito utilizada
– Permite a representação de dados de maneira
hierárquica;
– Fornece maneiras eficientes de busca;
• Quais são seus usos comuns?
– Manipular dados hierárquicos
– Manipular listar ordenadas de dados
– Em algoritmos de roteamento de pacotes
2
Motivação - exemplo
Joinville
Biguaçu
Blumenau
São José
Floripa
Palhoça
Garopaba
Tubarão
• Objetivo: Ir de Floripa para Blumenau!
3
Árvore de Busca
Floripa
Biguaçu
Biguaçu
São José Garopaba
Blumenau Palhoça
Tubarão Garopaba
4
Árvores - Grafos
• É uma árvore nada mais é que um tipo particular de grafo. Para que um
grafo seja uma árvore o mesmo deve ser:
– Conectado,
– acíclico,
– Não orientado
A
B
A
C
A
A
B
D
C
E
F
A
G
D
• É uma árvore
– Conectado
– acíclico
– Não orientado
B
E
E
D
C
F
G
B
C
D EE
D
C
B
F
G
• Não é uma árvore
• É uma arborecência
– Conectado
– Cíclico
– Não orientado
– disconectado
– acíclico
– Não orientado
5
Nomenclatura
Nó raiz
Nós internos
Nível 0
A
Folhas
B
D
Nível 1
C
E
F
G
altura da
árvore
Nível 2
Nó pai
Nó filho
B
E
6
Árvores Binárias
• Todo nó possui exatamente dois nós filhos
– Exceto os nos folha, que devem possuir exatamente 0 filhos
• É muito útil para modelar situações em que precisam ser
tomadas decisões bidirecionais em cada ponto de um processo
A
Subárvore esquerda
Subárvore direita
B
D
C
E
F
G
7
Árvores Binárias - Definições
• Árvore Binária Completa de nível d
– Todas as folhas estejam no nível d
• Se contiver m nós no nível l, ela conterá no
máximo 2m nós no nível l+1
Nível (d) n. max. nós Potência
• Uma árvore binária completa de
0 nível1d
2
2
2
contém exatamente 2l nós em 1cada lível
l
2
4
2
entre 0 e d (profundidade d com
exatamente
3
8
2
2d nós no nível d
4
16
2
0
1
2
3
4
5
32
25
8
Árvores Binárias - Definições
• Número total de nós
d
tn  2  2  2    2   2
0
1
2
n
j
Por indução
j 0
tn  2
d 1
1
• Também é possível calcular o nível d de uma
árvore binária completa se o número tn for
conhecido.
note que em geral, log2 x  x
d  log2 (tn  1) 1
log2x
x
3
15
10
1.024
≈20
1.000.000
9
Árvore Binárias Quase Completas
A
C
B
D
F
A
B
E
G
A
E
D
H
I
B
D
G
F
J
K
E
D
H
D
F
G
I
1. Todas as folhas da árvore devem estar localizadas no
nível d ou no nível d-1;
2. Para cada nó nd na árvore com um descendente
direto no nível d, todos os descendentes esquerdos
de nd que forem folhas estiverem também no nível d.
10
Numeração de nós de árvores binárias
1
A
2
3
B
D
5
4
E
D
8
H
A
B
D
6
F
7
G
9
I
D
E
F
G
H
• Os nós de uma árvore binária quase
completa podem ser numerados
• 1 para a raiz
• Filho esquerdo = dobro do n. do pai
• Filho direito = dobro + 1 do n. do pai
• A numeração ajuda na
implementação como será visto na
aula prática
(implementação por vetores)
• Facilita na localização de itens
I
11
Exemplo: encontrar repetições
• Encontrar todas as repetições numa lista de
números
– Comparar cada número com todos os que o
prescedem
– Por meio de uma árvore binária
4
3
6
5
4
9
9
1
2
12
Encontrar Repetições – Árvore Binária
• Inserção:
– pegue o primeiro elemento da lista e o faça a raiz da
árvore binária;
– Para cada elemento seguinte:
1.
Comparar com o nó raiz
a. Se igual, acusar repetição
b. Se menor, examinar a subárvore
esquerda
c. Se maior, examinar a subárvore da direita
d. Se vazio, inserir o elemento sendo
examinado
4
3
6
5
4
9
9
1
2
4
3
1
6
2
5
9
13
Percurso de Árvores Binárias
• Não existe uma ordem “natural” para se
percorrer uma árvore binária
• Existem três formas básicas:
– Ordem Anterior (percurso em profundidade)
– Ordem (ou em ordem simétrica)
– Ordem Posterior
14
Algorítmos Recursivos
ordemAnterior(no)
IMPRIMA no.valor
SE no.esq ≠ null ENTAO
ordemAnterior(no esq)
SE no.dir ≠ null ENTAO
ordemAnterior(no.dir)
emOrdem(no)
SE no.esq ≠ null ENTAO
emOrdem(no.esq)
IMPRIMA no.valor
SE no.dir ≠ null ENTAO
emOrdem(no.dir)
ordemPosterior(no)
SE no.esq ≠ null ENTAO
emOrdem(no.esq)
SE no.dir ≠ null ENTAO
emOrdem(no.dir)
IMPRIMA no.valor
15
Exemplo – ordemAnterior
A
B
D
H
C
E
I
F
G
1. ant([A,B,C,D,E,F,G,H,I])(init)
5.
H
(4.a)
6. A
2.
I
(4.b)
7. a.
E ant([B,D,E,H,I])
(3.b)
8. b.
C ant([C,F,G])
(2.b)
3. a.
B ant(F)
(2.a)
a.
b. ant([D,H,I])
ant(G)
b. ant([E])
9. F
4.
D
10.G
a. ant([H])
b. ant([I])
(8.a)
(3.a)
(8.b)
16
Exemplo – emOrdem
A
B
D
H
C
E
I
F
G
11.ord([C,F,G])
1. ord([A,B,C,D,E,F,G,H,I])(init.)
12.ord([F])
2. ord([B,D,E,H,I])
13.F
3. ord([D,H,I])
14.C
4. ord([H])
15.ord([G])
5. H
16.G
6. D
7. ord(I)
8. I
9. B
10.ord([E])
17
Revisitando... Encontrar Repetições
9
8
9
7
6
5
4
3
9
8
7
4
3
4
5
4
7
7
9
8
9
3
4
5
6
6
7
5
8
4
3
A ordem dos elementos na lista pode
levar a criação de uma árvore não
balanceada
9
18
Laboratório Desta Semana
• Implementar uma árvore Binária
– Usando arrays como estrutura de armazenamento
– Usando ponteiros
– Resolver o problema da identificação de números
repetidos usando árvores binárias
– Implementar os métodos de percurso
• Modificar a árvore binária para que seus nós
possam armazenar diferentes tipos de dados
(números e operadores)
19
Bibliografia da Aula
• A. A. Tenenbaum, Y. Langsam, M. J. Augenstein.
Estruturas de Dados Usando C. Makron Books Ed.
1995. pp. 303—406. (cap. 5)
• R. Sedegewick. Algorithms in C. Princeton University.
Addison-Wesley Publishing Company. 1990. pp 35—
50. (cap. 4)
20