Teoria dos Grafos
Árvore - Introdução
•• Em
Em nosso
nosso dia-a-dia
dia-a-dia nos
nos deparamos
deparamos com
com muitos
muitos
exemplos
exemplos de
de árvores:
árvores:
–– Árvore
Árvore genealógica.
genealógica.
–– Organograma
Organograma de
de uma
uma empresa.
empresa.
–– Tabela
Tabela de
de um
um torneio
torneio esportivo.
esportivo.
•• Na
Na computação:
computação:
–– Organização
Organização da
da estrutura
estrutura de
de arquivos
arquivos (diretório).
(diretório).
–– Armazenamento
e
busca
eficiente
Armazenamento e busca eficiente de
de dados.
dados.
–– Ordenação.
Ordenação.
–– Árvores
Árvores de
de decisão.
decisão.
Árvores
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Árvore Livre
Árvore Enraizada
•• Uma
Uma árvore
árvore (livre)
(livre) éé um
um grafo
grafo acíclico,
acíclico, não
não orientado
orientado ee
conectado.
conectado.
•• Uma
Uma floresta
floresta éé um
um grafo
grafo acíclico,
acíclico, não
não orientado
orientado mas,
mas,
possivelmente,
possivelmente, desconectado.
desconectado.
•• Considerando
Considerando que
que G
G == (V,
(V, E)
E) éé um
um grafo
grafo não
não orientado,
orientado, éé
equivalente
equivalente dizer:
dizer:
1.
1. G
G éé uma
uma árvore.
árvore.
2.
2. Um
Um par
par de
de vértice
vértice qualquer
qualquer (v,
(v, w)
w) de
de G
G está
está conectado
conectado
por
por apenas
apenas um
um caminho.
caminho.
3.
3. G
G éé conectado.
conectado. AA remoção
remoção de
de uma
uma aresta
aresta desconecta
desconecta G.
G.
4.
4. G
G éé conectado
conectado ee |E|
|E| == |V|
|V| -- 1.
1.
5.
5. G
G éé acíclico
acíclico ee |E|
|E| == |V|
|V| -- 1.
1.
6.
6. G
G éé acíclico.
acíclico. AA adição
adição de
de uma
uma aresta
aresta cria
cria um
um ciclo
ciclo em
em G.
G.
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
•• Tipo
Tipo especial
especial de
de árvore
árvore que
que apresenta
apresenta um
um vértice
vértice (raiz)
(raiz) que
que
se
se distingue
distingue dos
dos demais.
demais.
•• Utilizamos
Utilizamos oo termo
termo nó
nópara
parafazer
fazer referência
referência aos
aos vértices.
vértices.
7
3
8
6
12
5
4
11
2
1
9
Teoria dos Grafos
Algumas Definições
© Jorge Figueiredo, DSC/UFCG
Algumas Definições
•• Seja
Seja xx um
um nó
nó de
de uma
uma árvore
árvore enraizada
enraizada TT com
com raiz
raiz r:r:
–– Ancestral:
Ancestral:éé qualquer
qualquer nó
nó yy no
no caminho
caminho de
de rr aa x.
x.
–– Descendente:
Descendente:xx éé um
um descendente
descendente de
de yy se
se yy éé ancestral
ancestral
de
de x.
x.
–– Ancestral
Ancestral Próprio:
Próprio: yy éé ancestral
ancestral próprio
próprio de
de xx se
se yyéé
ancestral
ancestral de
de xx ee yy ≠≠ x.
x.
–– Descendente
Descendente Próprio:
Próprio: yy éé descendente
descendente próprio
próprio de
de xx se
se yy
éé descendente
descendente de
de xx ee yy ≠≠ x.
x.
–– Sub-árvore
Sub-árvore enraizada
enraizada em
em x:
x:árvore
árvore induzida
induzida pelos
pelos
descendentes
descendentes de
de x,
x, com
com xx sendo
sendo aa raiz.
raiz.
–– Filho:
Filho: xx éé filho
filho de
de yy se
se ele
ele éé um
um descendente
descendente direto.
direto.
–– Pai:
Pai: éé oo ancestral
ancestral próprio
próprio mais
mais próximo.
próximo. AA raiz
raiz éé oo único
único
nó
nó sem
sem pai.
pai.
Teoria dos Grafos
10
© Jorge Figueiredo, DSC/UFCG
––
––
––
––
Folha:
Folha: um
um nó
nó sem
sem filhos.
filhos.
Nó
Nó interno:
interno:um
um nó
nó que
que não
não éé folha.
folha.
Grau:
Grau:oo grau
grau de
de yy éé oo número
número de
de filhos
filhos de
de y.
y.
Profundidade:
Profundidade: oo comprimento
comprimento desde
desde aa raiz
raiz rr até
até xx éé aa
profundidade
profundidade de
de xx em
em T.
T.
–– Altura:
Altura:
•• aa altura
altura de
de um
um nó
nó em
em uma
uma árvore
árvore éé oo maior
maior
comprimento
comprimento do
do nó
nó até
até uma
uma folha.
folha.
•• AA altura
altura de
de uma
uma árvore
árvore éé aa altura
altura de
de sua
sua raiz.
raiz.
•• Altura
Altura da
da árvore
árvore éé aa maior
maior profundidade
profundidade de
de qualquer
qualquer
nó
nó da
da árvore.
árvore.
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
1
Exemplo
Implementação de Árvores
7
3
8
10
12
6
Profundidade 0
5
Profundidade 1
4
11
2
•• Além
Além da
da informação
informação de
de cada
cada nó,
nó, um
um link
link para
para cada
cada
um
um dos
dos filhos.
filhos.
•• Inconveniente:
Inconveniente: não
não sabemos
sabemos aa priori
priori aa quantidade
quantidade
de
de filhos
filhos em
em cada
cada nó.
nó.
Profundidade 2
1
Profundidade 3
9
Profundidade 4
Altura da árvore é 4
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Implementação de Árvores
Implementação de Árvores
•• Os
Os filhos
filhos de
de um
um nó
nó são
são mantidos
mantidos em
em uma
uma lista
lista
encadeada.
encadeada.
A
B
/
C
/
/
D
E
F
G
/
N
H
/
/
I
/
J
P
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
8
6
12
5
11
1
3
12
2
1
9
10
8
6
4
11
/
M
/
/
/
/
/
/
© Jorge Figueiredo, DSC/UFCG
2
5
raiz
9
TL
Árvores enraizadas iguais.
Árvores ordenadas diferentes.
Teoria dos Grafos
Q
L
•• Estrutura
Estrutura de
de nós
nós que
que éé definida
definida recursivamente
recursivamente através
através de
de
um
um conjunto
conjunto de
de nós:
nós:
–– Não
Não contém
contém nenhum
nenhum nó,
nó, ou;
ou;
–– Formada
Formada por
por 33 conjuntos
conjuntos disjuntos:
disjuntos: um
um nó
nó raiz,
raiz, duas
duas subsubárvores
árvores binárias
binárias (direita
(direita ee esquerda).
esquerda).
7
7
4
/
Árvore Binária
•• Árvore
Árvore enraizada
enraizada em
em que
que os
os filhos
filhos de
de cada
cada nó
nó estão
estão
ordenados.
ordenados.
10
/
K
Teoria dos Grafos
Árvore Ordenada
3
/
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
TR
© Jorge Figueiredo, DSC/UFCG
2
Árvore Binária – Conceitos Importantes
•• Árvore
Árvore vazia
vazia ou
ou nula:
nula: não
não contém
contém nenhum
nenhum nó.
nó.
•• Filho
Filho da
da esquerda:
esquerda: raiz
raiz da
da sub-árvore
sub-árvore da
da esquerda
esquerda (quando
(quando
houver).
houver).
•• Filho
da
direita:
raiz
da
sub-árvore
da
direita
(quando
Filho da direita: raiz da sub-árvore da direita (quando
houver).
houver).
•• Filho
Filho ausente:
ausente:quando
quando aa sub-árvore
sub-árvore dé
dé aa árvore
árvore nula.
nula.
Árvore Binária Cheia
•• Cada
Cada nó
nó ou
ou éé uma
uma folha
folha ou
ou tem
tem grau
grau exatamente
exatamente 2.
2.
7
3
12
4
8
6
11
2
5
O número de nós internos de uma árvore binária cheia é f – 1,
onde f é o número de folhas.
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
Árvore Binária Completa
Árvore k-ária Completa
•• Árvore
Árvore binária
binária em
em que
que todas
todas as
as folhas
folhas estão
estão em
em uma
uma mesma
mesma
profundidade
profundidade ee todos
todos os
os nós
nós internos
internos têm
têm grau
grau 2.
2.
7
3
12
4
8
11
© Jorge Figueiredo, DSC/UFCG
2
•• Em
Em uma
uma árvore
árvore posicional,
posicional, os
os filhos
filhos de
deum
um nó
nó são
são rotulados
rotulados
como
como inteiros
inteiros distintos.
distintos.
•• Árvore
Árvore k-ária
k-ária éé uma
uma árvore
árvore posicional
posicional onde
onde os
os filhos
filhos com
com
rótulos
rótulos maiores
maiores do
do que
que kk são
são ausentes.
ausentes.
•• Árvore
Árvore k-ária
k-ária completa
completa éé uma
uma árvore
árvore k-ária
k-ária onde
onde todas
todas as
as
folhas
folhas têm
têm aa mesma
mesma profundidade
profundidade ee todos
todos os
os nós
nós internos
internos
têm
têm grau
grau k.
k.
•• Uma
Uma árvore
árvore binária
bináriaéé uma
uma árvore
árvore k-ária
k-áriacom
com kk == 2.
2.
h
O número de nós internos de uma árvore binária completa é 2 – 1,
onde h é a altura da árvore.
h
O número de nós internos de uma árvore k-ária completa é k – 1/ k - 1,
onde h é a altura da árvore.
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
Aplicação: Árvores de Expressões
•Seja
•Seja aa expressão
expressão (a+b*c)+((d*e+f)*g):
(a+b*c)+((d*e+f)*g):
–Folhas
–Folhas são
são operandos.
operandos.
–Nós
–Nós internos
internos são
são operadores.
operadores.
© Jorge Figueiredo, DSC/UFCG
Árvores de Expressões
•• Caminhamento
Caminhamento em
em ordem:
ordem:
–– produz
produz expressão
expressão na
na notação
notação infixa.
infixa.
((a+(b*c))+(((d*e)+f)*g))
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
3
Árvores de Expressões
Árvore Binária de Pesquisa - ABP
•• Caminhamento
Caminhamento em
em pós-ordem:
pós-ordem:
–– produz
produz expressão
expressão na
na notação
notação pósfixa.
pósfixa.
•• Árvore
Árvore binária
binária em
em que
que cada
cada nó
nó tem
tem uma
uma chave
chave que
que
não
não éé menor
menor do
do que
que as
as chaves
chaves dos
dos nós
nós de
de sua
sua subsubárvore
árvore esquerda
esquerda ee não
não éé maior
maior do
do quas
quas chaves
chaves dos
dos nós
nós
da
da sub-árvore
sub-árvore direita.
direita.
Expressão pósfixa:
ABP
abc*+de*f+g*+
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Não é ABP
Teoria dos Grafos
Heap Binário
© Jorge Figueiredo, DSC/UFCG
Implementação de Heap Binário
•• Árvore
Árvore binária
binária com
comduas
duas propriedades:
propriedades:
–– Estrutura:
Estrutura: árvore
árvore binária
binária quase
quase completa.
completa. O
O último
último nível
nível
pode
pode não
não ser
ser completado.
completado.
–– Ordem:
Ordem: todo
todo filho
filho éé maior
maior (ou
(ou igual)
igual) do
do que
que oo pai.
pai.
•• Usar
Usar um
um array:
array:
–– Parent(i)
Parent(i) == ⎣i/2⎦
⎣i/2⎦
–– Left(i)
Left(i) == 2i
2i
–– Right(i)
Right(i) == 2i
2i ++ 11
06
06
1
14
45
78
83
18
91
47
77
81
84
53
99
64
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
14
45
2
3
78
18
47
53
4
5
6
7
83
91
81
77
84
99
64
8
9
10
11
12
13
14
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Inserção em Heap Binário
Inserção em Heap Binário
•• Manter
Manter propriedades
propriedades de
de ordem
ordem ee estrutura.
estrutura.
•• Inserir
Inserir no
no slot
slot livre
livre ee depois
depois procurar
procurar lugar
lugar correto.
correto.
06
14
45
06
78
14
83
78
83
18
91
81
18
45
47
77
84
91
81
47
77
84
53
99
64
42
53
99
64
42
Próximo slot livre
Trocar com o pai, se necessário
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
4
Inserção em Heap Binário
Inserção em Heap Binário
06
06
14
78
18
91
83
14
45
77
81
84
78
42
47
99
64
18
91
83
53
42
77
81
45
47
84
99
64
53
Propriedade de ordem OK!!
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Inserção em Heap Binário
Remoção em Heap Binário
•• Manter
Manter propriedades
propriedades de
de ordem
ordem ee estrutura.
estrutura.
•• Sempre
Sempre remove
remove oo menor
menor elemento.
elemento.
06
14
42
06
78
18
91
83
77
81
84
14
45
47
99
64
53
78
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
18
91
83
42
77
81
•• Manter
Manter propriedades
propriedades de
de ordem
ordem ee estrutura.
estrutura.
•• Sempre
Sempre remove
remove oo menor
menor elemento.
elemento.
Teoria dos Grafos
14
42
84
78
45
47
77
53
53
18
81
64
© Jorge Figueiredo, DSC/UFCG
06
14
91
99
Remoção em Heap Binário
•• Manter
Manter propriedades
propriedades de
de ordem
ordem ee estrutura.
estrutura.
•• Sempre
Sempre remove
remove oo menor
menor elemento.
elemento.
83
84
Teoria dos Grafos
Remoção em Heap Binário
78
45
47
99
64
83
53
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
42
18
91
81
45
47
77
84
99
64
06
© Jorge Figueiredo, DSC/UFCG
5
Remoção em Heap Binário
Remoção em Heap Binário
•• Manter
Manter propriedades
propriedades de
de ordem
ordem ee estrutura.
estrutura.
•• Sempre
Sempre remove
remove oo menor
menor elemento.
elemento.
•• Manter
Manter propriedades
propriedades de
de ordem
ordem ee estrutura.
estrutura.
•• Sempre
Sempre remove
remove oo menor
menor elemento.
elemento.
53
14
14
78
18
91
83
53
42
77
81
84
78
45
47
99
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
18
91
83
64
42
77
81
•• Manter
Manter propriedades
propriedades de
de ordem
ordem ee estrutura.
estrutura.
•• Sempre
Sempre remove
remove oo menor
menor elemento.
elemento.
14
18
18
42
53
81
84
78
45
47
77
64
© Jorge Figueiredo, DSC/UFCG
14
91
99
Remoção em Heap Binário
•• Manter
Manter propriedades
propriedades de
de ordem
ordem ee estrutura.
estrutura.
•• Sempre
Sempre remove
remove oo menor
menor elemento.
elemento.
83
84
Teoria dos Grafos
Remoção em Heap Binário
78
45
47
99
83
64
42
53
91
81
45
47
77
84
99
64
Propriedade de ordem OK!!
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
Aplicação em Ordenação: HeapSort
••
••
••
••
Inserir
Inserir NN itens
itens no
no heap.
heap.
executar
executar NN operações
operações de
de remoção.
remoção.
O(N
O(N log
log N).
N).
Não
Não éé necessário
necessário armazenamento
armazenamento extra.
extra.
Teoria dos Grafos
© Jorge Figueiredo, DSC/UFCG
6