Aula18. Arvores Conceitos e Definicoes

Prévia do material em texto

1
Estruturas de Dados
Árvores
Prof. Ricardo J. G. B. Campello
2
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
3
Introdução
� Problema:
� Listas Lineares
� Lista Encadeada
� Eficiente para inserção e remoção dinâmica de elementos, 
mas ineficiente para busca
� Lista Seqüencial (ordenada)
� 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...
4
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 P&DProdução
Laptops DesktopsBR Internacionais
Europa Asia EUA
3
5
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
6
Definição
� Á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;
RT
T1 T2 Tn...
4
7
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
8
RAIZ da RAIZ da 
árvoreárvore
Nós: A, B, C, D, E, F, G
Folhas: E,F,C,G
FILHOS 
DE A
FILHOS 
DE B
FILHO 
DE D
A
B C D
GFE
Exemplo
5
9Sub-árvore
Terminologia
Raiz (root): nó sem pai (A).
Nó Interno: nó com pelo 
menos um filho (A, B, C, F).
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.
A
B DC
G HE F
I J K
10
A
C D B
G EF
NÓS 
IRMÃOS
DESCENDENTES 
DE A
ANCESTRAIS DE GTIOS de F e E
Exemplo
6
11
� 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
� Nível de seu nó PAI + 1
� O GRAU de um nó X pertencente a uma 
árvore é igual ao número de filhos de X
� 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
Terminologia
12
Exemplo: A
DCB E
IGF JH K L
NM O
P
NÍVEL 1
NÍVEL 2
NÍVEL 3
NÍVEL 4
NÍVEL 5
Grau de A: 4
Grau de B: 3
Grau de C: 0
Grau de M: 1
Grau da Árvore: 4
7
13
Terminologia
Profundidade (de um nó): 
número de ancestrais.
� Raiz possui profundidade zero.
Altura (de uma árvore): máxima 
profundidade de qualquer nó. 
� Exemplo ao lado ⇒ 3.
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.
� Equivalente à altura.
Sub-Árvore
A
B DC
G HE F
I J K
Nota: Terminologia não é universal!
Alguns autores consideram como 1
(ao invés de zero) a altura das folhas
e a profundidade da raiz, o que altera
as demais definições.
14
A
DCB E
IGF JH K L
NM O
P
Exemplo:
ALTURA DE A: 4
ALTURA DE C: 0
ALTURA DE D: 1
PROF. DE A: 0
PROF. DE C: 1
PROF. DE D: 1
Altura Árvore = Profundidade Árvore = 4
8
15
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
B
C
D
E
F
G
I
H
16
Árvores Binárias (AB)
� 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
RT
TE TD
9
17
Á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
G
C
FED
IH
18
Algumas Propriedades de ABs
� Qual a altura máxima de uma AB com n nós?
� Resposta: n – 1
� Árvore degenerada ≡ Lista
� Qual a altura mínima de uma AB c/ n nós?
� Resposta: teto[ log2(n+1) ] – 1
0
1
n-1
1
2 3
5 6 74
n = 1 ⇒ h = 0
n = 2, 3 ⇒ h = 1
n = 4, ..., 7 ⇒ h = 2
n = 8, ..., 15 ⇒ h = 3
...
n = 2h+1 – 1 ⇒ h = log2(n+1) – 1 
10
19
Árvore Binária Própria
Também denominada de árvore 
estritamente binária, é tal que:
� Cada nó interno possui exatamente 
2 filhos (não vazios).
Denomina-se o par de filhos de:
� filho esquerdo (left child), e
� filho direito (right child).
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.
Aplicações:
� Expressões aritméticas.
� Processos de decisão.
� etc
A
B C
F GD E
H I
20
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
11
21
Á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 1
3 b
22
Poupança
Conservador?
Curto prazo?
Fundo R. Fixa Aceita Altos Riscos?
Sim Não
Sim Não
Ações Carteira Mista
Sim Não
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:
Árvore Binária Própria
12
23
Á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
24
Á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
B G
C E FD
C,D,E,F estão no nível 3 
(profundidade 2)
13
25
Á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
26
Á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
� Não é difícil mostrar que essa condição implica de fato que a 
árvore é balanceada segundo a definição geral acima
A
B C
D E
A
B C
FED
14
27
� Á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:
Árvores Binárias Balanceadas
A
B C
ED
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 ?
15
29
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.