TAD de árvores Arquivo

Estruturas de Dados
Árvores – Parte II:
EDs & Algoritmos
Prof. Ricardo J. G. B. Campello
Parte deste material é baseado em adaptações e extensões de slides
disponíveis em http://ww3.datastructures.net (Goodrich & Tamassia).
O TAD Árvore
Operações Genéricas:
Operações de Consulta:
size(T): no. de nós da árvore.
isInternal(T, p): Nó p é interno ?
isEmpty(T): árvore T vazia ?
isExternal(T, p): Nó p é externo ?
isRoot(T, p): Nó p é raiz de T ?
Operações de Acesso:
root(T): retorna referência
para o nó raiz ou para nulo
se árvore T for vazia.
parent(T, p): retorna ref. p/ o
nó pai do nó referenciado por
p ou para nulo se p é raiz.
children(T, p): retorna lista
de referências para os filhos
do nó referenciado por p.
Lista vazia se p for folha.
Operações de Atualização:
swap(T, p, q): Troca elementos
da árvore T armazenados nos
nós referenciados por p e q.
replace(T, p, e): Substitui por “e”
o elemento armazenado no nó
referenciado por p.
...
2
1
TAD Árvore Binária
O TAD Árvore Binária estende o TAD árvore, ou seja, herda
todas as suas operações.
Operações Adicionais:
leftChild(T, p): retorna referência para o nó filho esquerdo do nó
referenciado por p ou para nulo (p. ex. se p é externo).
rightChild(T, p): retorna referência para o nó filho direito do nó
referenciado por p ou para nulo (p. ex. se p é externo).
sibling(T, p): retorna referência para o nó irmão do nó referenciado
por p ou para nulo se p é filho único (árvore T imprópria).
3
O TAD Árvore Binária
Árvores são estruturas muito flexíveis, dando margem à diversos
tipos de operações possíveis para um TAD.
Por esta razão, TADs Árvore podem diferir bastante de
implementação para implementação, especialmente no que diz
respeito aos métodos de modificação. Exemplo:
Dois possíveis métodos que permitem modificar a estrutura:
removeAboveExternal(T, w)
expandExternal(T, v)
v
A
A
∅
v
∅
A
B
B
C
w
Permitem construir ou destruir completamente qualquer árvore binária!
4
2
Estrutura em Arranjo para Árvores Binárias
Utiliza o conceito de função
numeradora por nível:
f(v) = 1 se v é a raiz da árvore T.
f(v) = 2f(u) se v é filho esq. de u.
f(v) = 2f(u)+1 se v é filho dir. de u.
1
2
4
6
5
10
Cada nó da árvore é armazenado
na célula de um arranjo
3
7
11
O índice é dado pela função
numeradora.
O valor da função numeradora
fornece imediatamente a
localização dos filhos e do pai.
5
Estrutura em Arranjo para Árvores Binárias
Tamanho do arranjo é N = pM+1,
onde pM é o valor máximo de f(v).
Para índice inicial do arranjo = 0
1
3
2
n=7
N = 16
7
Problema:
Se a árvore não for completa,
células do arranjo serão alocadas
desnecessariamente.
Espaço é O(N) independente do
6
15
14
1
número n de nós da árvore.
No pior caso, a demanda de
memória é Exponencial!
N = 2(n+1)/2 para ABs próprias
N=
2n para
3
n=4
N = 16
7
15
ABs impróprias
3
Estrutura em Arranjo para ABs
Resumo:
a
b
d
f
e
1
2
3
4
5
6
7
...
a
b
c
d
e
f
g
...
g
Vantagens:
Simplicidade
Espaço apenas para armazenar conteúdo (elementos)
c
ligações estão implícitas nos valores dos índices
Desvantagens:
Espaços vagos se árvore não é completa
Inadequada para árvores com tamanho variável
7
Estrutura Encadeada para Árvores Binárias
∅
Um nó é representado por
um nodo, que armazena:
Elemento.
Ponteiro para pai.
Ponteiro para filho esquerdo.
Ponteiro para filho direito.
B
∅
∅
Espaço O(n)!
A
D
B
A
∅
D
C
E
∅
C
∅
∅
E
8
4
Tempos de Execução nas Duas Implementações
Operação
Arranjo / Encadeada
swap, replace
O(1)
root, parent, children
O(1)
leftChild, rightChild, sibling
O(1)
isInternal, isExternal , isRoot
O(1)
O(1)
expandExternal,
removeAboveExternal
(encadeada)
9
Estrutura Encadeada para Árvores
∅
Um nó é representado
por um nodo, que
armazena:
B
Elemento
∅
Ponteiro para nó pai.
Ponteiro para lista de
ponteiros para nós
filhos.
∅
A
D
F
B
D
A
C
F
E
∅
C
∅
E
10
5
O(n), onde
n é o no.
de nodos
Percurso Pré-Fixado
Um “percurso” visita os nodos de
uma árvore de forma sistemática.
travessia ou caminhamento
Em um percurso pré-fixado, um
nodo é visitado antes dos seus
descendentes.
Algoritmo PreOrder(T, v)
visite(T, v)
se isInternal(T, v) então
para w ∈ children(T, v) faça
PreOrder(T, w)
* Acesso seqüencial à lista children a
partir do primeiro filho.
Exemplo de Aplicação:
1
imprimir doc. estruturado
Documento
2
9
5
Capítulo 1
Capítulo 2
3
4
Seção 1.1
Seção 1.2
6
Referências
7
Seção 2.1
Seção 2.2
8
Seção 2.3
Percurso Pré-Fixado
Caso Particular
Árvores Binárias
Algoritmo PreOrder(T, v)
visite(T, v)
se isInternal(T, v) então
PreOrder(T, leftChild(T, v))
PreOrder(T, rightChild(T, v))
* Chamada: PreOrder(T, root(T))
6
O(n), onde
n é o no.
de nodos
Percurso Pós-Fixado
Em um percurso pós-fixado, um
nodo é visitado após seus
descendentes.
Algoritmo PosOrder(T, v)
se isInternal(T, v) então
para w ∈ children(T, v) faça
PosOrder(T, w)
visite(T, v)
Útil quando alguma propriedade de
um nodo depende da propriedade
dos seus descendentes.
* Acesso seqüencial à lista
Exemplo de Aplicação:
calcular o espaço utilizado em
árvores de arqs e diretórios.
children a partir do primeiro filho.
9
cs16/
3
8
7
homeworks/
todo.txt
1K
programs/
1
2
h1c.doc
3K
h1nc.doc
2K
4
5
DDR.java
10K
Stocks.java
25K
6
Robot.java
20K
13
Percurso Pós-Fixado
Caso Particular
Árvores Binárias
Algoritmo PosOrder(T, v)
se isInternal(T, v) então
PosOrder(T, leftChild(T, v))
PosOrder(T, rightChild(T, v))
visite(T, v)
* Chamada: PosOrder(T, root(T))
7
Avaliação de Expressões Aritméticas
Algoritmo EvalExpr(T, v)
se isInternal(T, v) então
x ← EvalExpr(T, leftChild(T, v))
y ← EvalExpr(T, rightChild(T, v))
◊ ← elem(T, v)
retorne x ◊ y
senão retorne elem(T, v)
Especialização de um
percurso pós-fixado:
visite(T, v) calcula e
retorna a op. x ◊ y se v
for interno, c.c. retorna o
valor armazenado em v.
+
* Chamada: EvalExpr(T, root(T))
×
×
−
2
5
3
Árvores
Binárias
2
1
PS. Assume disponível no TAD AB operação elem(T, v), que retorna info. do nó referenciado por v.
Percurso Inter-Fixado
Algoritmo InOrder(T, v)
Em um percurso interfixado um nodo é visitado se isInternal(T, v) então
após sua sub-árvore
InOrder(T, leftChild(T, v))
esquerda e antes da sua
visite(T,
v)
sub-árvore direita.
Exemplo de Aplicação:
Percurso não decrescente
em uma árvore binária de
busca onde cada nodo
interno armazena um
elemento maior (menor) ou
igual aos elementos
armazenados na sua subárvore esquerda (direita).
se isInternal(T, v) então
InOrder(T, rightChild(T, v) )
* Chamada: InOrder(T, root(T))
6
2
8
1
4
3
7
9
5
16
8
Exercícios
Escreva um algoritmo em pseudo-código que receba
uma árvore T e uma referência para um nó da árvore,
retornando a profundidade daquele nó na árvore.
O algoritmo deve ser iterativo (não-recursivo).
O algoritmo deve usar apenas as operações do TAD
Árvore (slide 3), independente da ED utilizada para
implementá-lo.
17
Exercícios
Faça um algoritmo em pseudo-código para cálculo da altura de
uma árvore binária própria T recebida como parâmetro:
O algoritmo deve ser recursivo.
Para tanto, a árvore não deve ser o seu único parâmetro.
O algoritmo deve usar apenas as operações do TAD Árvore
Binária (slides 3 e 5), independente da ED utilizada para
implementá-lo.
Você deve mostrar que o tempo de execução de pior caso do
algoritmo é linear em termos do número de nós da árvore.
18
9
Exercícios
Seja a seguinte expressão aritmética:
( −27 / ( ( 2 × (a + 8) ) − ( (3 × b) + 18 ) ) ) / ( c − 10 )
Represente essa expressão em uma árvore estritamente binária
de expressão aritmética.
Mostre em detalhes como essa árvore ficaria armazenada em
um arranjo segundo a estratégia de implementação baseada em
função numeradora por nível.
Mostre graficamente e em detalhes como essa árvore ficaria
armazenada em uma estrutura dinâmica.
Mostre o conteúdo de cada nó da árvore segundo a ordem de
visitas aos nós, nos seguintes percursos:
pré-fixado, pós-fixado e inter-fixado.
19
Exercícios
Implemente o TAD Árvore Binária em Linguagem C:
Via ED estática (arranjo).
Via ED dinâmica.
Faça a implementação de um dos TADs acima de modo a
armazenar números inteiros nos nodos da árvore. Então
implemente operações para imprimir todos esses números via:
Percurso pré-fixado.
Percurso pós-fixado.
Percurso inter-fixado.
Nota: Cada visita deve imprimir o valor do nó correspondente.
20
10
Bibliografia
M. T. Goodrich & R. Tamassia, Estruturas de Dados e
Algoritmos em Java, Bookman, 2002
M. T. Goodrich & R. Tamassia, Data Structures and
Algorithms in C++/Java, John Wiley & Sons, 2002/2005
J. L. Szwarcfiter & L. Markenzon, Estruturas de Dados e seus
Algoritmos, LTC, 1994
A. V. Aho, J. E. Hopcroft & J. Ullman, Data Structures and
Algorithms Addison Wesley, 1983
A. M. Tenembaum et al., Data Structures Using C, PrenticeHall, 1990
11