View
112
Download
5
Category
Preview:
Citation preview
Árvores
Prof. Dr. rer. nat. Daniel Duarte Abdala
DAS 5102 – Fundamentos da Estrutura da Informação
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
• Objetivo: Ir de Floripa para Blumenau!3
FloripaSão José
Tubarão
Biguaçu
Joinville
Palhoça
Garopaba
Blumenau
Árvore de Busca
4
Floripa
Biguaçu São José Garopaba
PalhoçaBiguaçu TubarãoBlumenau Garopaba
Árvores - Grafos
A
B C
FED G
A
B C
FE
D
G
A
B C
FE
D
G
• É uma árvore– Conectado– acíclico– Não orientado
• Não é uma árvore– Conectado– Cíclico– Não orientado
• É uma arborecência– disconectado– acíclico– Não orientado
5
• É 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 C
ED
A
B C ED
Nível 2
Nível 1
Nó raiz
Nomenclatura
A
C
FED G
Nível 0
altura daárvoreB
Nós internos
Folhas
B
E
Nó pai
Nó filho
6
Árvores Binárias
A
C
FED G
B
Subárvore esquerda Subárvore direita
7
• 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
Á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
• Uma árvore binária completa de nível d contém exatamente 2l nós em cada lível l entre 0 e d (profundidade d com exatamente 2d nós no nível d
8
Árvores Binárias - Definições
• Número total de nós
9
d
j
jnnt
0
210 22222 12 1 dnt
Por indução
• Também é possível calcular o nível d de uma árvore binária completa se o número tn for conhecido.
1)1(log2 ntd xx 2lognote que em geral,
log2x x
3 15
10 1.024
≈20 1.000.000
Árvore Binárias Quase Completas
A
B C
F
D E
G
A
B
H
D E
I
D
G
J
F
K
A
B
H
D E
I
D
GF
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
A
B
H
D E
I
D
GF
1
2 3
4 5 6 7
8 9
11
• 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 itensA B D D E F G H I
Exemplo: encontrar repetições
12
• 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
Encontrar Repetições – Árvore Binária
13
• Inserção:– pegue o primeiro elemento da lista e o faça a raiz
da árvore binária;– Para cada elemento seguinte:
4
3
1 2
6
95
1. Comparar com o nó raiza. Se igual, acusar repetiçãob. Se menor, examinar a subárvore
esquerdac. Se maior, examinar a subárvore da
direitad. Se vazio, inserir o elemento sendo
examinado4 3 6 5 4 9 9 1 2
Percurso de Árvores Binárias
14
• 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
Algorítmos Recursivos
15
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
Exemplo – ordemAnterior
16
A
B
D E
C
GF
5. H (4.a)
6. I (4.b)
7. E (3.b)
8. C (2.b)a. ant(F)
b. ant(G)
9. F (8.a)
10.G (8.b)
IH
1. ant([A,B,C,D,E,F,G,H,I])(init)
2. Aa. ant([B,D,E,H,I])
b. ant([C,F,G])
3. B (2.a)a. ant([D,H,I])
b. ant([E])
4. D (3.a)a. ant([H])
b. ant([I])
1. ord([A,B,C,D,E,F,G,H,I])(init.)
2. ord([B,D,E,H,I])
3. ord([D,H,I])
4. ord([H])
5. H
6. D
7. ord(I)
8. I
9. B
10.ord([E])
Exemplo – emOrdem
17
A
B
D E
C
GF
IH
11.ord([C,F,G])
12.ord([F])
13.F
14.C
15.ord([G])
16.G
Revisitando... Encontrar Repetições
18
9 8 9 7 6 5 4 3 4 3 4 5 4 7 7 9 8 9
9
8
7
6
5
4
3
3
4
5
6
7
8
9A ordem dos elementos na lista pode levar a criação de uma árvore não balanceada
Laboratório Desta Semana
19
• 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)
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
Recommended