Estruturas de Dados
Árvores
Prof. Ricardo J. G. B. Campello
Créditos
Parte deste material consiste de:
Adaptações dos slides gentilmente cedidos
pela Profa. Maria Cristina F. de Oliveira
Adaptados dos originais de Walter Aoiama Nagai
e M. Graças Volpe Nunes
Adaptações e extensões dos originais de
Goodrich & Tamassia
Disponíveis em http://ww3.datastructures.net/
2
1
Introdução
Problema:
Listas Lineares
Lista Encadeada
Lista Seqüencial (ordenada)
Eficiente para inserção e remoção dinâmica de elementos,
mas ineficiente para busca
Eficiente para busca, mas ineficiente para inserção e
remoção de elementos
Possível Solução:
Árvores
Eficientes para inserção, remoção e busca
Representação não linear...
3
Introdução
Em computação, uma
árvore é um modelo
abstrato de uma
estrutura hierárquica.
Trata-se de uma
estrutura não-linear
constituída de nós
com relações de
parentesco (pai-filho).
Aplicações:
S.O.s (arquivos).
Linguagens (O.O.).
etc
ABC Computadores
Vendas
BR
Europa
Produção
Internacionais
Asia
Laptops
P&D
Desktops
EUA
4
2
Introdução
Árvores são adequadas para representar
estruturas hierárquicas não lineares, como
relações de descendência
pai, filhos, irmãos, etc.
Homer Simpson
Bart
Lisa
Maggie
5
Definição
RT
T1
T2
...
Tn
Árvore T: conjunto finito de elementos,
denominados nós, nodos ou vértices, tais que:
Se T = ∅ a árvore é dita vazia;
Caso Contrário:
(i) T contém um nó especial, denominado raiz (RT);
(ii) Os demais nós, ou constituem um único conjunto vazio, ou
são divididos em n conjuntos disjuntos não vazios
(T1,T2,…,Tn), que são, por sua vez, cada qual uma árvore;
T1,T2,…,Tn são chamadas sub-árvores de RT;
6
3
Terminologia
Se um nó Y é raiz de uma sub-árvore de um
nó X, então X é PAI de Y e Y é FILHO de X
Dois nós são IRMÃOs se são filhos do
mesmo pai
Se os nós Y1, Y2, ..., Yj são irmãos, e o nó Z
é filho de Y1, então Y2,...,Yj são TIOs de Z
7
Exemplo
Nós: A, B, C, D, E, F, G
RAIZ da
árvore
FILHOS
DE A
E
A
B
C
F
FILHOS
DE B
Folhas: E,F,C,G
D
G
FILHO
DE D
8
4
Terminologia
Raiz (root): nó sem pai (A).
Nó Interno: nó com pelo
menos um filho (A, B, C, F).
A
Nó Externo ou Folha: nó
sem filhos (E, I, J, K, G, H, D).
Ancestrais (de um nó): pai
ou ancestrais do pai do nó.
Descendentes (de um nó):
nós que o possuem como
ancestral.
Sub-Árvore: árvore
consistindo de um nó e dos
seus descendentes.
B
E
C
F
I
J
G
D
H
K
9
Sub-árvore
Exemplo
ANCESTRAIS DE G
TIOS de F e E
A
C
D
B
NÓS
IRMÃOS
DESCENDENTES
DE A
G
F
E
10
5
Terminologia
O NÍVEL de um nó X é definido como:
O nível de um nó raiz é 1
O nível de um nó não raiz é dado por
O GRAU de um nó X pertencente a uma
árvore é igual ao número de filhos de X
Nível de seu nó PAI + 1
Se X é folha, então Grau(X) = 0
O GRAU de uma árvore T é o maior entre
os graus de todos os seus nós
11
Exemplo:
NÍVEL 1
NÍVEL 2
B
F
G
H
M
N
O
P
NÍVEL 5
A
C
D
NÍVEL 3
I
NÍVEL 4
E
J
K
L
Grau de A: 4
Grau de B: 3
Grau de C: 0
Grau de M: 1
Grau da Árvore: 4
12
6
Terminologia
A
Profundidade (de um nó):
número de ancestrais.
B
E
F
G
H
Exemplo ao lado ⇒ 3.
I
Altura (de um nó): altura da
sub-árvore com raiz naquele nó.
Folhas possuem altura zero.
Raiz possui altura da árvore.
Profundidade (de uma árvore):
máx. profundidade de uma folha.
D
Raiz possui profundidade zero.
Altura (de uma árvore): máxima
profundidade de qualquer nó.
C
J
K
Nota: Terminologia não é universal!
Alguns autores consideram
como 1
Sub-Árvore
(ao invés de zero) a altura das folhas
e a profundidade da raiz, o que altera
as demais definições.
Equivalente à altura.
13
Exemplo:
A
B
F
G
M N
C
H
O
P
Altura Árvore = Profundidade Árvore = 4
D
I
E
J
K
L
ALTURA DE A:
4
ALTURA DE C:
0
ALTURA DE D:
1
PROF. DE A:
0
PROF. DE C:
1
PROF. DE D:
1
14
7
Outras Formas de Representação
Representação por Parênteses Aninhados:
( A (B) ( C ( D (G) (H) ) (E) ( F (I) ) ) )
ou seja, uma lista generalizada!!
Representação por Diagramas de Venn:
A
C
E
B
D H
G
F
I
15
RT
Árvores Binárias (AB)
TE
TD
Uma Árvore Binária T é um conjunto finito de
elementos, denominados nós, nodos ou
vértices, tal que:
(i) Se T = ∅, a árvore é dita vazia, ou
(ii) T contém um nó especial, chamado raiz de T (RT),
e os demais nós podem ser subdivididos em dois
sub-conjuntos distintos, TE e TD, os quais também
são árvores binárias (possivelmente vazias).
TE e TD são denominados sub-árvore esquerda e
sub-árvore direita de T, respectivamente
16
8
Árvores Binárias (AB)
A raiz da sub-árvore esquerda (direita) de um nó v,
se existir, é denominada filho esquerdo (direito)
de v.
Pela natureza da árvore binária, o filho esquerdo pode
existir sem o direito, e vice-versa
Exemplo:
A
B
C
F
E
D
G
H
I
17
Algumas Propriedades de ABs
Qual a altura máxima de uma AB com n nós?
0
Resposta: n – 1
Árvore degenerada ≡ Lista
1
n-1
Qual a altura mínima de uma AB c/ n nós?
Resposta: teto[ log2(n+1) ] – 1
1
2
4
3
5
6
7
n=1
n = 2, 3
n = 4, ..., 7
n = 8, ..., 15
...
n = 2h+1 – 1
⇒
⇒
⇒
⇒
h=0
h=1
h=2
h=3
⇒ h = log2(n+1) – 1
18
9
Árvore Binária Própria
Também denominada de árvore
estritamente binária, é tal que:
Aplicações:
Cada nó interno possui exatamente
2 filhos (não vazios).
Expressões aritméticas.
Processos de decisão.
etc
Denomina-se o par de filhos de:
filho esquerdo (left child), e
filho direito (right child).
A
Definição recursiva:
Uma árvore de um único nó raiz,
ou
Uma árvore cuja raiz possui um
par ordenado de filhos, cada um
dos quais é a raiz de uma árvore
binária própria.
B
C
D
E
H
F
G
I
19
Propriedades de Árvores Binárias Próprias
Notação:
n número de nós.
e número de nós
externos.
i número de nós
internos.
h altura.
Algumas Propriedades:
e= i + 1
n = 2e − 1
h ≤ i
h ≤ (n − 1)// 2
e ≤ 2h
h ≥ log2 e
h ≥ log2 (n + 1) − 1
20
10
Árvore Binária Própria
Exemplo de Aplicação:
Árvore de Expressão Aritmética
Árvore Binária associada com uma expressão aritmética
Nós internos: operadores
Nós externos: operandos
+
Exemplo: (2 × (a − 1) + (3 × b))
×
×
−
2
a
3
b
1
21
Árvore Binária Própria
Exemplo de Aplicação:
Árvore Binária de Decisão
Árvore binária associada a um processo de decisão
Nós internos: questões com respostas sim ou não
Nós externos: decisões
Exemplo:
Conservador?
Não
Sim
Poupança
Curto prazo?
Não
Sim
Fundo R. Fixa
Sim
Ações
Aceita Altos Riscos?
Não
Carteira 22
Mista
11
Árvore Binária Completa
Árvore Binária Completa (ABC):
É própria*
Se a profundidade da árvore é d, então cada nó folha está
no nível d ou no nível d+1
Os nós folha no nível d estão todos à direita dos internos
nível d
nível d+1
* Exceção pode eventualmente ser feita ao nó folha mais à direita do último nível, que pode não existir
23
Árvore Binária Cheia
Árvore Binária Completa Cheia (ABCC)
É ABC, e
Todos os seus nós folha estão no mesmo nível
A
C,D,E,F estão no nível 3
(profundidade 2)
G
B
C
D
E
F
24
12
Árvore Binária Cheia
Propriedade Importante:
Dada uma ABCC e sua profundidade d (ou altura
h), calcula-se o número n de nós na árvore como:
Nível 1 (d = 0): 1 nó (total = 1 nó)
Nível 2 (d = 1): 2 nós (total = 3 nós)
Nível 3 (d = 2): 4 nós (total = 7 nós)
...
Nível i (d = i−1): 2d nós (total = 2i – 1 = 2d+1 – 1 nós)
Logo: n = 2d+1 – 1 = 2h+1 – 1
25
Árvores Binárias Balanceadas
Árvores Balanceadas: São tais que qualquer de suas
sub-árvores com m nós possui altura O(log m)
Árvore Binária Balanceada: Para cada nó, as alturas
de suas sub-árvores diferem em, no máximo, 1
A
A
C
B
D
C
B
E
D
E
F
Não é difícil mostrar que essa condição implica de fato que a
árvore é balanceada segundo a definição geral acima
26
13
Árvores Binárias Balanceadas
Árvore Binária Perfeitamente Balanceada
Para cada nó, o no. de nós de suas sub-árvores
esquerda e direita difere em, no máximo, 1
Toda AB Perfeitamente Balanceada é AB Balanceada,
mas o inverso não é necessariamente verdade.
Exemplo:
A
C
B
D
E
27
Exercícios
Prove por contra-exemplo que uma AB própria não é
necessariamente uma AB completa.
Represente a seguinte expressão aritmética em uma
árvore binária própria de expressão aritmética:
( 5 + ( ( 2 / (a + 1) ) − (3 × b) ) ) × ( 10 / c )
Responda com relação à árvore do exercício anterior:
Qual a altura da árvore ?
Qual a profundidade da árvore?
Qual o grau da árvore?
Quais os ancestrais, os descendentes, a profundidade, a
altura, o nível, o grau, o pai, os tios, os irmãos e os filhos do
nó correspondente ao operador de subtração da expressão ?
14
Exercícios
Represente a árvore do exercício anterior via:
Parênteses Aninhados
Diagrama de Venn.
Qual a altura máxima que uma árvore estritamente
binária com 45 nós pode ter? Justifique.
Qual a altura máxima que uma árvore estritamente
binária com 27 nós externos pode ter? Justifique.
Qual a altura mínima que uma árvore estritamente
binária com 43 nós pode ter? Justifique.
Qual a altura mínima que uma árvore estritamente
binária com 30 nós externos pode ter? Justifique.
29
15