Árvores (introdução)
Anjolina Grisi de Oliveira
Obs: vários slides foram cedidos por
Adolfo Almeida Duran (UFBA)
Árvores
Uma árvore é um grafo conexo não orientado
e sem circuitos simples
Matemática Discreta/ Grafos
CIn - UFPE
141
Uma floresta é um grafo cujas componentes
conexas são árvores
Matemática Discreta/ Grafos
CIn - UFPE
142
Teorema
Um grafo não orientado é uma árvore se e somente
se existe um único caminho simples entre qualquer
par de vértices.
Prova
Assuma que G é uma árvore. Logo G é um grafo
conexo e sem circuitos simples. Sejam x e y dois nós de
G. Logo, como G é conexo, existe um caminho simples
entre x e y. Adicionalmente, esse caminho é único, pois
se existisse um outro caminho, o caminho formado
através da combinação do caminho de x até y com o
segundo caminho começando por y e chegando a x
formaria um circuito, o que contraria a hipótese de que
G é uma árvore.
Matemática Discreta/ Grafos
CIn - UFPE
143
Árvore Enraizada
Uma árvore T = (V,E) é denominado enraizada
quando algum vértice v é escolhido como especial.
Esse vértice v é a raiz da árvore.
Matemática Discreta/ Grafos
CIn - UFPE
144
Árvore Enraizada
Usualmente representamos graficamente a raiz no
topo. Podemos transformar uma árvore sem raiz
numa árvore enraizada simplesmente escolhendo
um vértice como raiz.
Matemática Discreta/ Grafos
CIn - UFPE
145
Árvore Enraizada
ancestrais de j={e,c}
Raiz = c
descendentes de j={i,k}
pai de j=e
filhos de j={i,k}
nível de j=2
altura da árvore =3
folhas={b,a,i,k,f,h,d}
Matemática Discreta/ Grafos
CIn - UFPE
146
Árvore Enraizada
Raiz = c
O nível de um vértice é
o tamanho do único
caminho da raiz até ele.
nível de j=2
A altura da árvore é o
maior nível entre os
nós. É o tamanho do
maior caminho da raiz
até uma das folhas.
altura da árvore =3
Matemática Discreta/ Grafos
CIn - UFPE
147
Árvore Enraizada
A raiz de uma árvore não possui pai, e todo vértice v
diferente de r, possui um único pai.
Uma folha é um vértice que não possui filhos.
Vértices que possuem filhos são chamados de vértices
internos.
Quando a raiz é o único nó do grafo ela é uma folha.
O nível da raiz é zero, de seus filhos é 1. O nível de um
nó é igual ao nível de seu pai mais um.
Para dois vértices irmãos v e w, nível(v)=nível(w).
A altura de uma árvore é o valor máximo de nível(r) para
todo vértice v de T.
Matemática Discreta/ Grafos
CIn - UFPE
148
Subárvore
Seja T(V,E) uma árvore enraizada e v  V.
Uma subárvore Tv de T é uma árvore enraizada cuja
raiz é v, definida pelo subgrafo induzido pelos
descendentes de v mais o próprio v.
A subárvore de raiz v é única para cada v  V.
s
u
v
v
t
w
Matemática Discreta/ Grafos
w
x
CIn - UFPE
x
149
Árvore m-ária
Uma árvore enraizada é chamada de m-ária se todo nó
interno não possui mais que m filhos. A árvore é
chamada árvore m-ária cheia se todo nó interno possui
exatamente m filhos. Uma árvore m-ária com m=2 é
chamada de árvore binária.
Binária
3-ária
Matemática Discreta/ Grafos
CIn - UFPE
150
Árvore m-ária
A árvore é chamada árvore m-ária cheia se todo
nó interno possui exatamente m filhos. Uma
árvore m-ária com m=2 é chamada de árvore
binária.
s
u
v
t
z
-
w
x
Binária cheia
Matemática Discreta/ Grafos
CIn - UFPE
151
Árvore m-ária
Uma árvore enraizada m-ária de altura h é
balanceada se todas as folhas estão no nível h
ou h-1.
Matemática Discreta/ Grafos
CIn - UFPE
152
Árvore Balanceada?
h=3
Nível(a) =1
Não está balanceada
Matemática Discreta/ Grafos
CIn - UFPE
153
Árvore Enraizada Ordenada
Na definição de árvore enraizada, é irrelevante a
ordem em que os filhos de cada vértice v são
considerados.
Caso a ordenação seja relevante a árvore é
denominada enraizada ordenada.
Assim, para cada vértice v pode-se identificar o
primeiro filho de v (o mais a esquerda), o segundo
filho (o segundo mais a esquerda), etc.
Matemática Discreta/ Grafos
CIn - UFPE
154
Árvores
Matemática Discreta/ Grafos
CIn - UFPE
155
Árvore enraizada ordenada
No caso de árvores binárias, se um nó interno
possui dois filhos, temos o filho da esquerda e o
filho da direita
A árvore cuja raiz é o filho da esquerda de um
vértice é chamada de subárvore da esquerda
desse vértice.
b
a
b
d
Matemática Discreta/ Grafos
d
c
e
e
Subárvore da esquerda de a
CIn - UFPE
156
Teorema
Uma árvore com n nós possui n-1 arestas.
Prova
Definimos uma bijeção entre as arestas e os
vértices diferentes da raiz, de forma que
associamos cada vértice terminal de uma aresta
com ela própria. Como existem n-1 nós além da
raiz, logo existem n-1 arestas na árvore.
Matemática Discreta/ Grafos
CIn - UFPE
157
Teorema
Uma árvore m-ária cheia com i nós internos contem
n = mi + 1 nós.
Prova
Cada vértice com exceção da raiz é filho de um nó
interno. Como cada um dos i nós internos possui m
filhos, existem mi nós na árvore além da raiz.
Consequentemente, a árvore contem n = mi + 1
nós.
Matemática Discreta/ Grafos
CIn - UFPE
158
Teorema
Uma árvore m-ária cheia com
(i) n nós possui i=(n-1)/m nós internos e
l
= ((m-1)n +1)/m folhas
(ii) i nós internos possui n = mi + 1 nós e f= (m-1)i + 1
folhas
(iii) f folhas possui n = (mf – 1)/ (m-1) nós e i= (f-1)/(m-1)
nós internos
Matemática Discreta/ Grafos
CIn - UFPE
159
Teorema - Prova
Uma árvore m-ária cheia com
(i) n nós possui i=(n-1)/m nós internos e
= ((m-1)n +1)/m folhas
Vimos que n= mi + 1, logo i = (n-1)/m.
Temos também que n = i + f, onde f é o número de
folhas.
Logo, f = n – i;
f = n – (n-1)/m = (mn – (n-1))/m = (mn – n + 1)/m =
((m-1)n + 1)/m
Matemática Discreta/ Grafos
CIn - UFPE
l
160
Exemplo
Suponha que alguém iniciou uma corrente de cartas.
Cada pessoa que recebe a carta é convidada a enviá-la
para outras quatro pessoas. Quantas pessoas
receberam a carta, incluindo a pessoa que iniciou a
corrente, se nenhuma pessoa recebeu mais que uma
carta e se a corrente acabou depois que 64 pessoas
leram a carta e não mais a enviaram? Quantas
pessoas enviaram a carta?
Matemática Discreta/ Grafos
CIn - UFPE
161
Solução
A corrente pode ser representada usando uma árvore 4ária. Os nós internos correspondem às pessoas que
enviaram a carta, e as folhas às pessoas que não a
enviaram.
Temos que 64 pessoas não enviaram a carta. Assim o
número de folhas f é igual a 64.
Temos n = i + f e n = mi + 1.
Logo: 64 + i = 4.i + 1 => 3.i = 63 => i = 21
Resposta: 21 pessoas enviaram a carta
Matemática Discreta/ Grafos
CIn - UFPE
162
Teorema
Existem no máximo mh folhas em uma árvore
m-ária de altura h.
Prova: por indução sobre a altura
 h-1
 h-1
Matemática Discreta/ Grafos
 h-1
Cada uma dessas
subárvores possui altura no
máximo h-1. Portanto, pela
H.I. existem no máximo mh-1
folhas em cada uma delas.
Como existem no máximo m
dessas subárvores, cada
uma com no máximo mh-1
folhas, então existem no
máximo m.mh-1 = mh folhas.
CIn - UFPE
163
Aplicações: Árvore binária de busca
Busca de itens numa lista.
Cada vértice é rotulado por uma chave de forma que a
chave de um vértice é maior do que as chaves de todos
os nós da subárvore da esquerda e menor do que as
chaves dos nós da subárvore da direita.
55
30
20
35
32
Matemática Discreta/ Grafos
80
90
45
CIn - UFPE
164
Construindo uma árvore binária de busca
Procedimento recursivo que recebe uma lista de itens.
O primeiro item da lista é a raiz da árvore.
Para adicionar um novo item compare-o com os nós que
já estão na árvore: comece pela raiz e siga para a
esquerda se o item é menor que o item que rotula o nó
que está sendo comparado ou siga para a direita, caso
contrário. Quando o novo item é menor que um item
cujo nó não tem filho da esquerda, adicione-o como filho
da esquerda desse nó. Analogamente, quando o item é
maior que o item cujo nó não tem filho da direita,
adicione-o como filho da direita desse nó,
Matemática Discreta/ Grafos
CIn - UFPE
165
Construindo uma árvore binária de busca
Construa uma árvore binária de busca a partir da
seguinte lista:
55,30,80,90,35,32,20,45
Matemática Discreta/ Grafos
CIn - UFPE
166
Exemplo: árvore binária de busca
Use a ordem alfabética para construir uma árvore
binária de busca com as palavras da seguinte frase:
O título de uma das músicas de sucesso do cantor
Bruno Mars é ``The Lazy Song´´.
Matemática Discreta/ Grafos
CIn - UFPE
167
Caminhado em árvores enraizadas e
ordenadas
Procedimento universal para ordenar os seus nós:
• Rotule a raiz com o inteiro 0. Em seguida rotule seus k
filhos da esquerda para direita com 1,2,3,....,k.
• Para cada vértice v no nível n com rótulo A, rotule
seus k filhos da esquerda para a direita com A.1, A.2,
...A.k.
Matemática Discreta/ Grafos
CIn - UFPE
168
Exemplo
0
1
2
1.1
1.1.1
1.2 3.1
Matemática Discreta/ Grafos
3.2
3.3
1.1.2
3.1.1
1.1.2.1
3
1.1.2.2
3.1.2
1.1.2.3
CIn - UFPE
169
Procedimento universal para ordenar os
nós
• Podemos ordenar os nós usando a ordem
lexicográfica de seus rótulos.
x1.x2....xn < y1.y2....ym se
• existe um i, 0  i  n, com x1= y1, x2=y2, ...xi-1 = yi-1 e
xi< yi; ou
• n < m e xi=yi, para i =1,2,...,n.
Matemática Discreta/ Grafos
CIn - UFPE
170
Caminhamento em pré-ordem
Seja T uma árvore enraizada e ordenada com
raiz r. Se T possui apenas r, então o
caminhamento em pré-ordem de T é r. Caso
contrário, sejam T1, T2,... Tn as subárvores de r da
esquerda para a direita. O caminhamento em préordem começa visitando r e continua fazendo um
caminhamento em pré-ordem em T1, em seguida
em T2, e assim sucessivamente até que Tn seja
percorrida em pré-ordem.
Matemática Discreta/ Grafos
CIn - UFPE
171
Exemplo
a
b
e
f
j
Matemática Discreta/ Grafos
g
k
n
d
c
o
l
h
i
m
p
CIn - UFPE
172
Caminhamento em ordem
Seja T uma árvore enraizada e ordenada com
raiz r. Se T possui apenas r, então o
caminhamento em ordem de T é r. Caso
contrário, sejam T1, T2,... Tn as subárvores de r da
esquerda para a direita. O caminhamento em
ordem começa fazendo um percorrendo em
ordem em T1 em ordem, em seguida visita r, e
continua fazendo um caminhamento em ordem
em T2, em T3 , e finalmente em Tn .
Matemática Discreta/ Grafos
CIn - UFPE
173
Caminhamento em pós-ordem
Seja T uma árvore enraizada e ordenada com
raiz r. Se T possui apenas r, então o
caminhamento em pós-ordem de T é r. Caso
contrário, sejam T1, T2,... Tn as subárvores de r da
esquerda para a direita. O caminhamento em
pós-ordem começa percorrendo T1 em pósordem, em seguida T2, T3 , ... Tn , e finaliza
visitando r.
Matemática Discreta/ Grafos
CIn - UFPE
174
Notação infixa, pré-fixa e pós-fixa
Podemos representar expressões complicadas,
tais como proposições compostas, combinações
de conjuntos, e expressões aritméticas usando
árvores enraizadas ordenadas.
• O nós internos representam operações
• As folhas representam as variáveis ou valores
• As operações são executadas na subárvore da
esquerda e depois na direita
Matemática Discreta/ Grafos
CIn - UFPE
175
Notação infixa: exemplo
Árvore que representa a expressão
((x+y)^2) + ((x-4)/3):
• A árvore binária é construída de baixo para cima.
• Construímos a subárvore (x+y), depois a incorporamos
como parte de uma subárvore maior que representa
(x+y)^2.
^
+
+
x
y
x
Matemática Discreta/ Grafos
2
CIn - UFPE
y
176
Notação infixa: ((x+y)^2) + ((x-4)/3)
• Do mesmo modo a subárvore (x-4) é construída e
incorporada à subárvore maior de (x-4)/3
^
+
+
x
2
y
x
y
/
-
x
Matemática Discreta/ Grafos
-
4
x
CIn - UFPE
3
4
177
Notação infixa: ((x+y)^2) + ((x-4)/3)
Por último as subárvore de ((x+y)^2) e de
((x-4)/3) são combinadas para formar a expressão
toda
+
^
+
x
Matemática Discreta/ Grafos
/
2
y
-
x
3
4
CIn - UFPE
178
Caminhamento em ordem:
((x+y)^2) + ((x-4)/3)
+
^
+
x
Matemática Discreta/ Grafos
/
2
y
-
x
3
4
CIn - UFPE
179
Qual é a forma pré-fixa da expressão
((x+y)^2) + ((x-4)/3) ? (notação polonesa)
Fazemos um caminhamento em pré-ordem
+^+xy2/-x43
+
^
+
x
Matemática Discreta/ Grafos
/
2
y
x
3
4
CIn - UFPE
180
Qual o valor da expressão
+ - * 2 3 5 / ^2 3 4 ?
+ - * 2 3 5 / ^2 3 4
+-*235/ 8 4
+- 6 52
+-*235 /84
+ -65 2
+-*235 2
+ 1 2
+- *23 52
+ 1 2
+- 6 52
Matemática Discreta/ Grafos
3
CIn - UFPE
181
Qual é a forma pós-fixa da expressão
((x+y)^2) + ((x-4)/3) ? Fazemos um
caminhamento em pós-ordem
xy+2^x4–3/+
+
^
+
x
Matemática Discreta/ Grafos
/
2
y
x
3
4
CIn - UFPE
182
Qual o valor da expressão em notação
pós-fixa?
7 2 3 * - 4 ^9 3 / +
7 6 - 4 ^9 3 / +
14^93/+
193/+
13+
4
Matemática Discreta/ Grafos
CIn - UFPE
183
Encontre a árvore enraizada ordenada que
representa a seguinte proposição composta
(¬(pΛq))↔(¬p v ¬q)
¬
Λ
¬
↔
p
q
p
¬
v
Λ
p
q
q
Matemática Discreta/ Grafos
v
¬
¬
¬
p
q
Λ
p
CIn - UFPE
q
¬
¬
p
q
184
Forneça a notação pré-fixa e pós-fixa dessa
expressão (¬(pΛq))↔(¬p v ¬q)
Pré-fixa: ↔¬Λpqv¬p¬q
↔
Pós-fixa: pqΛ¬p¬q¬v↔
v
¬
Λ
p
q
¬
¬
p
q
O caminhamento em ordem
colocaria a negação
imediatamente após o seu
operando. Isso acontece
sempre com os operadores
unários.
A expressões em notação pré-fixa e pós-fixa não são
ambíguas. Por esse motivo, são utilizadas em computação.
Especialmente na construção de compiladores
Matemática Discreta/ Grafos
CIn - UFPE
185
Desenhe a árvore enraizada ordenada da seguinte
expressão aritmética escrita usando a notação préfixa.
+*+-53214
Em seguida, escreva a mesma expressão em
notação infixa.
+
*
5
((((5-3)+2)*1)+4)
1
+
-
4
2
3
Matemática Discreta/ Grafos
CIn - UFPE
186
Mais aplicações de árvores
1 Árvores de decisão
2 Código de prefixo
-Pode ser usado em compactação de arquivos ou
criptografia
-Considere o problema em que letras são
codificadas por sequências de bits
-Uma maneira de garantir que nenhuma sequência
de bits corresponde a mais de uma sequência de
letras, é escolher códigos de forma que a cadeia de
bits para uma letra nunca ocorre como prefixo de
uma cadeia de bits de outra letra.
Matemática Discreta/ Grafos
CIn - UFPE
187
Construa a árvore binária com os códigos de
prefixo que representam os seguintes esquemas
de codificação:
1) a:11, e:0, r:101, s:100
2) a:1,e:01,r:001, s:0001, n:00001
0
e
0
s
Matemática Discreta/ Grafos
1
1
0
a
1
r
CIn - UFPE
188
2) a:1,e:01,r:001, s:0001, n:00001
0
0
a
1
e
1
0
1
r
1
s
Matemática Discreta/ Grafos
CIn - UFPE
189