Á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,i,k,f,h,d}
Matemática Discreta/ Grafos
CIn - UFPE
146
Á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
147
Subárvore
Seja T(V,E) uma árvore enraizada e v pertencente
aV
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
pertencente a V.
Matemática Discreta/ Grafos
CIn - UFPE
148
Á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 completa se todo nó interno
possui exatamente m filhos. Uma árvore m-ária com
m=2 é chamada de árvore binária.
Matemática Discreta/ Grafos
CIn - UFPE
149
Á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
150
Á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
151
Árvores
Matemática Discreta/ Grafos
CIn - UFPE
152
Á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
153
Teorema
Uma árvore com n nós possui n-1 arestas.
Matemática Discreta/ Grafos
CIn - UFPE
154
Teorema
Uma árvore m-ária completa com i nós internos
contem n = mi + 1 nós.
Matemática Discreta/ Grafos
CIn - UFPE
155
Teorema
Uma árvore m-ária completa 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 + l nós e l= (m-1)i + 1
folhas
(iii) l folhas possui n = (ml – 1)/ (m-1) nós e i= (l-1)/(m-1)
nós internos
Matemática Discreta/ Grafos
CIn - UFPE
156
Exemplo
Suponha que alguém iniciou uma corrente de cartas.
Cada pessoa que recebe a carta é convidada a enviá-la
para outras quatro pessoas. Algumas pessoas fazem
isso, mas outras não mandam nenhuma carta. 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 100
pessoas leram a carta e não mais a enviaram? Quantas
pessoas enviaram a carta?
Matemática Discreta/ Grafos
CIn - UFPE
157
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.
Matemática Discreta/ Grafos
CIn - UFPE
158
Solução
Temos que 100 pessoas não enviaram a carta. Assim o
número de folhas l é igual a 100.
Aplicando o resultado do teorema visto: n = (ml -1)/(m-1)
Temos que n = (4.100 -1)/(4-1) = 133. São então 133
nós e assim 133 – 100 = 33 nós internos, ou pessoas
que enviaram a carta.
Matemática Discreta/ Grafos
CIn - UFPE
159
Teorema
Existem no máximo mh folhas em uma árvore
m-ária de altura h.
Prova: por indução sobre a altura.
Matemática Discreta/ Grafos
CIn - UFPE
160
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
161
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
162
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
163
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
164
Exemplo
a
b
e
f
j
Matemática Discreta/ Grafos
g
k
n
d
c
o
l
h
i
m
p
CIn - UFPE
165
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
166
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
167