transp_ho

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Estruturas de Dados
e
Te´cnicas de Programac¸a˜o
Tomasz Kowaltowski
Instituto de Computac¸a˜o
Universidade Estadual de Campinas
www.ic.unicamp.br/∼tomasz
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o 1
Copyright c© 2010-2011 Tomasz Kowaltowski
Instituto de Computac¸a˜o
Universidade Estadual de Campinas
Algumas transpareˆncias foram adaptadas da apostila Estruturas de Dados
e Te´cnicas de Programac¸a˜o de autoria de Cla´udio L. Lucchesi e Tomasz
Kowaltowski.
Estas transpareˆncias somente podem ser copiadas para uso pessoal dos
docentes e alunos das disciplinas oferecidas pelo Instituto de Computac¸a˜o
da UNICAMP.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o 2
Introduc¸a˜o
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Introduc¸a˜o 3
Pre´-requisito e objetivos
I Pre´-requisito: curso ba´sico de programac¸a˜o em C
I Objetivos:
I Programac¸a˜o em (relativamente) baixo n´ıvel
I Te´cnicas de programac¸a˜o e estruturac¸a˜o de dados
I Preparac¸a˜o para:
I Ana´lise de algoritmos
I Programac¸a˜o de sistemas
I Programac¸a˜o em geral
I Bancos de dados
I Engenharia de software
I . . .
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Introduc¸a˜o 4
Programa
I Introduc¸a˜o a` ana´lise de algoritmos
I Estruturac¸a˜o elementar de dados: matrizes, registros, apontadores
I Estruturas lineares: pilhas, filas, filas duplas
I Recursa˜o e retrocesso
I A´rvores bina´rias: representac¸a˜o, percursos
I A´rvores gerais: representac¸a˜o, percursos
I Aplicac¸a˜o de a´rvores:
a´rvores de busca (AVL), filas de prioridade,
a´rvores B, a´rvores rubro-negras, a´rvores digitais
I Listas generalizadas
I Espalhamento
I Processamento de cadeias de caracteres
I Gerenciamento de memo´ria
I Algoritmos de ordenac¸a˜o
I Algoritmos em grafos
I Tipos abstratos de dados e orientac¸a˜o a objetos
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Introduc¸a˜o 5
Bibliografia
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Bibliografia 6
A. V. Aho, J. E. Hopcroft, and J. Ullman.
Data Structures and Algorithms.
Addison-Wesley, 1983.
A. Drozdek.
Estrutura de Dados e Algoritmos em C++.
Thomson, 2002.
J. L. Szwarcfiter e L. Markenzon.
Estruturas de Dados e seus Algoritmos.
LTC Editora, 1994.
C. L. Lucchesi e T. Kowaltowski.
Estruturas de Dados e Te´cnicas de Programac¸a˜o.
Instituto de Computac¸a˜o – UNICAMP, 2003.
P. Feofiloff.
Algoritmos em Linguagem C.
Elsevier Editora Ltda., 2009.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Bibliografia 7
G. H. Gonnet.
Handbook of Algorithms and Data Structures.
Addison-Wesley, 1984.
E. Horowitz and S. Sahni.
Fundamentals of Data Structures in Pascal.
Computer Science Press, 1984.
D. E. Knuth.
The Art of Computer Programming, volume I: Fundamental
Algorithms.
Addison-Wesley, 1978.
E. M. Reingold and W. J. Hanson.
Data Structures.
Little Brown and Company, 1983.
R. Sedgewick.
Algorithms in C.
Addison-Wesley, 1990.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Bibliografia 8
D. F. Stubbs and N. W. Webre.
Data Structures with Abstract Data Types and Pascal.
Brooks/Cole, 1985.
A. M. Tenenbaum, Y. Langsam, and M. J. Augenstein.
Data Structures using C.
Prentice-Hall, 1990.
N. Wirth.
Algorithms + Data Structures = Programs.
Prentice-Hall, 1976.
N. Ziviani.
Projeto de Algoritmos (2a. ed.)
Thomson, 2004.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Bibliografia 9
Noc¸o˜es de Ana´lise de Algoritmos
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Noc¸o˜es de Ana´lise de Algoritmos 10
Escolha da estrutura
Importaˆncia da escolha de estrutura de dados – busca do k-e´simo
elemento numa sequ¨eˆncia:
. . .
x = a [ k ] ;
. . .
. . .
p = a ; i = 0 ;
whi le ( i<k ) {
p = p−>prox ;
i ++;
}
x = p−> i n f o ;
. . .
(a) (b)
(a) Nu´mero de operac¸o˜es constante (vetor).
(b) Nu´mero de operac¸o˜es proporcional a k (lista ligada).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Noc¸o˜es de Ana´lise de Algoritmos 11
Exemplo de ana´lise de trechos de programas
. . .
x = a+b ;
. . .
. . .
f o r ( i =0; i<n ; i ++)
x = a+b ;
. . .
. . .
f o r ( i =0; i<n ; i ++)
f o r ( j =0; j<n ; j ++)
x = a+b ;
. . .
(a) (b) (c)
a b c
ana´lise simples (1) 1 n n2
ana´lise detalhada (2) 2 5n+ 2 5n2 + 5n+ 2
(1): atribuic¸o˜es (2): atribuic¸o˜es, operac¸o˜es aritme´ticas e comparac¸o˜es
As duas ana´lises produzem resultados proporcionais para valores crescentes
de n.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Noc¸o˜es de Ana´lise de Algoritmos 12
Notac¸a˜o O()
Definic¸a˜o:
f(n) = O(g(n)) se existem n0 e k com f(n) ≤ k ∗ g(n) para todo n > n0.
Exemplos:
c = O(1) para qualquer constante c
2 = O(1)
5n+ 2 = O(n)
5n2 + 5n+ 2 = O(n2)
n2 = O(n3)
nk = O(nk+1), k ≥ 0
loga n = O(logb n), a, b > 0
log2 n = O(log10 n)
Outras notac¸o˜es importantes: Θ(), Ω(), etc.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Noc¸o˜es de Ana´lise de Algoritmos 13
Exemplo de ana´lise de um procedimento de ordenac¸a˜o
vo id Ordena ( i n t v [ ] , i n t n ) {
i n t i , k , m, t ;
f o r ( i =0; i<n−1; i ++) {
m = i ;
f o r ( k=i +1; k<n ; k++)
i f ( v [ k]<v [m] ) m = k ;
t = v [ i ] ; v [ i ] = v [m] ; v [m] = t ;
}
} /∗ Ordena ∗/
O nu´mero de comparac¸o˜es de elementos de v, para cada valor de i, e´
n− i− 1. O nu´mero total de comparac¸o˜es sera´:
n−2∑
i=0
(n− i− 1) = n
2
2
+
n
2
ou seja, o nu´mero de comparac¸o˜es e´ da ordem de O(n2).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Noc¸o˜es de Ana´lise de Algoritmos 14
Crescimento de algumas func¸o˜es
n log2 n n log2 n n
2 n3 2n
1 0 0 1 1 2
2 1 2 4 8 4
4 2 8 16 64 16
8 3 24 64 512 256
16 4 64 256 4.096 65.536
32 5 160 1.024 32.768 4.294.967.296
64 6 384 4.096 262.144 ≈ 18×1018
128 7 896 16.384 2.097.152 ≈ 34×1037
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Noc¸o˜es de Ana´lise de Algoritmos 15
Exemplo
Suponha duas ma´quinas M1 e M2, sendo a primeira cem vezes mais
ra´pida do que a segunda. Ambas as ma´quinas executam um algoritmo de
busca num vetor ordenado de comprimento n. A ma´quina M1 executa o
algoritmo de busca sequencial (pior caso: n operac¸o˜es); a ma´quina M2
executa o algoritmo de busca bina´ria (pior caso: log2 n operac¸o˜es).
A seguinte tabela poderia ser obtida atrave´s de medidas experimentais de
tempo de execuc¸a˜o para vetores de diversos tamanhos, usando alguma
unidade de tempo conveniente.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Noc¸o˜es de Ana´lise de Algoritmos 16
Exemplo (cont.)
n M1 (ra´pida) M2 (lenta)
16 16 400
32 32 500
64 64 600
128 128 700
256 256 800
512 512 900
1024 1024 1000
2048 2048 1100
. . . . . . . . .
220 1.048.576 2000
221 2.097.152 2100
. . . . . . . . .
230 1.073.741.824 3000
Supondo que a unidade seja 1µs (microssegundo), 2.097.152µs corresponde a 17
minutos e 1.073.741.824µs equivale a cerca de 12 horas.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Noc¸o˜es de Ana´lise de Algoritmos 17
Execuc¸a˜o de programas
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Execuc¸a˜o de programas 18
Exemplo de func¸o˜es simples
vo id g ( i n t x , i n t ∗y ) {
∗y = x ;
} /∗ g ∗/
vo id f ( i n t ∗ z ) {
i n t y ; char b ;
y = 2 3 5 ;
g ( y , z ) ;
} /∗ f ∗/
i n t main ( ) {
i n t i ; char c ;
char v [ 5 ] ;
f (& i ) ;
r e t u r n 0 ;
} /∗ main ∗/
Pilha de execuc¸a˜o (supo˜e inteiros de
dois bytes):
i c v
main
z y b
f
235
x y
235
g
235
Obs.: Na realidade, os inteiros sa˜o armazenados sob a forma bina´ria.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Execuc¸a˜o de programas 19
Exemplo de func¸o˜es com alocac¸a˜o dinaˆmica
typedef char Cade ia [ 5 ] ;
typedef Cade ia ∗ApCadeia ;
typedef s t r u c t {
Cade ia nome ;
i n t i d a d e ;
} Reg , ∗ApReg ;
ApCadeia apc ;
ApReg apr ;
i n t ∗ a p i ;
vo id Aloca ( ApCadeia ∗c , ApReg ∗ r ) {
a p i = m a l l o c ( s i z e o f ( i n t ) ) ;
∗ a p i = 1 0 ;
∗c = m a l l o c ( s i z e o f ( Cade ia ) ) ;
∗ r = m a l l o c ( s i z e o f ( Reg ) ) ;
} /∗ Aloca ∗/
i n t main ( ) {
Aloca (&apc ,& apr ) ; f r e e ( apc ) ;
f r e e ( apr ) ; f r e e ( a p i ) ;
r e t u r n 0 ;
} /∗ main ∗/
memo´ria dinaˆmica
pilha de execuc¸a˜o
apc apr api
global main
c r
Aloca
1010
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Execuc¸a˜o de programas 20
Exemplo de func¸a˜o recursiva
i n t main ( ) {
i n t m;
m = f a t ( 4 ) ;
r e t u r n 0 ;
} /∗ main ∗/
i n t f a t ( i n t n ) {
i f ( n==0)
r e t u r n 1 ;
e l s e
r e t u r n n∗ f a t ( n−1);
} /∗ f a t ∗/
m res n
4
res n
3
res n
2
res n
1
res n
011262424
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Execuc¸a˜o de programas 21
Estruturas ligadas
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 22
Listas ligadas simples
p
. . .
Declarac¸o˜es (equivalentes):
typedef
s t r u c t R e g L i s t a ∗ L i s t a ;
typedef
s t r u c t R e g L i s t a {
T i n f o ;
L i s t a prox ;
} R e g L i s t a ;
typedef
s t r u c t R e g L i s t a {
T i n f o ;
s t r u c t R e g L i s t a ∗ prox ;
} R e g L i s t a , ∗ L i s t a ;
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 23
Inserc¸a˜o e remoc¸a˜o com passagem por valor
. . . x . . .
p q
vo id I n s e r e ( L i s t a p , T x ) {
L i s t a q =
m a l l o c ( s i z e o f ( R e g L i s t a ) ) ;
q−> i n f o = x ;
q−>prox = p−>prox ;
p−>prox = q ;
}
vo id Remove ( L i s t a p , T ∗x ) {
L i s t a q = p−>prox ;
∗x = q−> i n f o ;
p−>prox = q−>prox ;
f r e e ( q ) ;
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 24
Inserc¸a˜o e remoc¸a˜o com passagem por valor (cont.)
. . . x . . .
p q
I O argumento p e´ o apontador para o predecessor do no´ a ser inserido
ou removido.
I A func¸a˜o ’Remove’ na˜o pode remover um no´ que e´ o u´nico da lista.
I A func¸a˜o ’Insere’ na˜o pode inserir um no´ no in´ıcio da lista, inclusive
se ela for vazia.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 25
Inserc¸a˜o e remoc¸a˜o com passagem por refereˆncia
. . . x . . .
p q
vo id I n s e r e ( L i s t a ∗p , T x ) {
L i s t a q =
m a l l o c ( s i z e o f ( R e g L i s t a ) ) ;
q−> i n f o = x ;
q−>prox = ∗p ;
∗p = q ;
}
vo id Remove ( L i s t a ∗p , T ∗x ) {
L i s t a q = ∗p ;
∗x = q−> i n f o ;
∗p = q−>prox ;
f r e e ( q ) ;
}
Esta convenc¸a˜o elimina os problemas da passagem por valor. Note-se que
as varia´veis p e q teˆm tipos diferentes.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 26
Lista simples com no´ cabec¸a
p
. . .
Lista vazia:
p
Esta convenc¸a˜o permite o uso de passagem por valor nas func¸o˜es ba´sicas.
O campo de informac¸a˜o do no´ cabec¸a pode ser aproveitado para guardar
alguma informac¸a˜o adicional (por exemplo, o comprimento da lista).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 27
Lista simples circular
p
. . .
Problema: lista vazia?
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 28
Lista circular com no´ cabec¸a
p
. . .
Lista vazia:
p
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 29
Busca em lista circular com no´ cabec¸a – sentinelas
L i s t a B u s c a C i r c u l a r (
L i s t a p , T x ) {
/∗ Busca sem s e n t i n e l a ∗/
L i s t a q = p ;
do {
q = q−>prox ;
} whi le ( ( q!=p ) &&
( q−> i n f o !=x ) ) ;
i f ( q==p )
r e t u r n NULL ;
e l s e
r e t u r n q ;
}
L i s t a B u s c a C i r c u l a r (
L i s t a p , T x ) {
/∗ Busca com s e n t i n e l a ∗/
L i s t a q = p ;
q−> i n f o = x ;
do {
q = q−>prox ;
} whi le ( q−> i n f o !=x ) ;
i f ( q==p )
r e t u r n NULL ;
e l s e
r e t u r n q ;
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 30
Lista duplamente ligada com no´ cabec¸a
p
. . .
Lista vazia:
p
I E´ poss´ıvel percorrer os elementos nas duas direc¸o˜es, a partir de
qualquer lugar da lista.
I E´ poss´ıvel remover o elemento apontado.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 31
Operac¸o˜es sobre listas duplamente ligadas
typedef
s t r u c t R e g L i s t a D u p l a {
T i n f o ;
s t r u c t R e g L i s t a D u p l a ∗ esq ,∗ d i r ;
} RegLis taDupla , ∗ L i s t a D u p l a ;
vo id I n s e r e D u p l a E s q (
L i s t a D u p l a p , T x ) {
L i s t a D u p l a q =
m a l l o c ( s i z e o f ( R e g L i s t a D u p l a ) ) ;
q−> i n f o = x ;
q−>esq = p−>esq ;
q−>d i r = p ;
p−>esq−>d i r = q ;
p−>esq = q ;
}
vo id RemoveDupla (
L i s t a D u p l a p , T ∗x ) {
p−>esq−>d i r = p−>d i r ;
p−>d i r−>esq = p−>esq ;
∗x = p−> i n f o ;
f r e e ( p ) ;
}
A func¸a˜o ’RemoveDupla’ supo˜e que ha´ pelo menos um elemento na lista.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 32
Exemplo: operac¸o˜es com polinoˆmios
Seja um polinoˆmio de grau n:
P (x) = anx
n + an−1xn−1 + . . .+ a1x1 + a0x0
onde an 6= 0, exceto possivelmente no caso n = 0.
Representac¸a˜o ligada omite os termos na˜o nulos. Por exemplo, os
polinoˆmios:
P1(x) = 5x
20 − 3x5 + 7 e P2(x) = 0:
podem ser representados por:
-1p1 5 20 -3 5 7 0
-1p2
Por convenc¸a˜o, o expoente do no´ cabec¸a e´ -1.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 33
Exemplo de func¸a˜o: impressa˜o
typedef s t r u c t AuxPol {
i n t expo ;
f l o a t c o e f ;
s t r u c t AuxPol ∗ prox ;
} Termo , ∗P o l i n o m i o ;
vo id Im pr ime Po l ino mi o ( P o l i n o m i o p ) {
i f ( p−>prox==p ) {
p r i n t f ( ” P o l i n oˆ m i o n u l o \n” ) ;
r e t u r n ;
}
p = p−>prox ;
whi le ( p−>expo !=−1) {
p r i n t f ( ”(%2d ,%5.1 f ) ” ,
p−>expo , p−>c o e f ) ;
p = p−>prox ;
}
p r i n t f ( ”\n” ) ;
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 34
Soma de polinoˆmios: paradigma de intercalac¸a˜o
-1p
pp0
. . .
pp
-1q
qq0
. . .
qq
-1r
rr0
. . .
rr
As varia´veis pp e qq representam os termos correntes dos polinoˆmios
dentro da malha de repetic¸a˜o e a varia´vel rr aponta para o u´ltimo termo ja´
calculado da soma; pp0, qq0 e rr0 sa˜o os valores iniciais das varia´veis pp,
qq e rr.
A implementac¸a˜o das operac¸o˜es e´ um exerc´ıcio. Note-se que o produto de
dois polinoˆmios pode ser calculado como uma sequeˆncia de somas de
produtos de um polinoˆmio por um termo.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 35
Matrizes esparsas
Exemplo:
∣∣∣∣∣∣∣∣
50 0 0 0
10 0 20 0
0 0 0 0
−30 0 −60 5
∣∣∣∣∣∣∣∣
Dada uma matriz n× n, quando o nu´mero de elementos na˜o nulos e´ uma
percentagem pequena de n2 (na˜o e´ o caso do exemplo!), pode ser
conveniente representar a matriz
por meio de uma estrutura de listas
ortogonais.
Suporemos, neste exemplo, que as linhas e as colunas sa˜o numeradas a
partir de 1.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 36
Matrizes esparsas: listas ortogonais
50 0 0 0
10 0 20 0
0 0 0 0
−30 0 −60 5
4 -1
3 -1
2 -1
1 -1
-1 -1 -1 1 -1 2 -1 3 -1 4
1 1
50
2 1
10
2 3
20
4 1
-30
4 3
-60
4 4
5
O acesso a` matriz e´ feito a partir do no´ cabec¸a das listas das cabec¸as das
linhas e das colunas (super-cabec¸a!).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 37
Operac¸o˜es sobre matrizes esparsas
Alguns exemplos:
typedef
s t r u c t RegEsparsa {
i n t l i n h a , c o l u n a ;
double v a l o r ;
s t r u c t RegEsparsa ∗ d i r e i t a , ∗ a b a i x o ;
} RegEsparsa , ∗M a t r i z ;
vo id I n i c i a l i z a M a t r i z ( M a t r i z ∗a , i n t m, i n t n ) ;
vo id L i b e r a M a t r i z ( M a t r i z a ) ;
double ElementoMatr i z ( M a t r i z a , i n t i , i n t j ) ;
vo id A t r i b u i M a t r i z ( M a t r i z a , i n t i , i n t j , double x ) ;
vo id SomaMatr izes ( M a t r i z a , M a t r i z b , M a t r i z ∗c ) ;
vo id M u l t i p l i c a M a t r i z e s ( M a t r i z a , M a t r i z b , M a t r i z ∗c ) ;
E´ importante notar os casos em que a passagem do argumento do tipo
’Matriz’ e´ feita por refereˆncia. (Nas duas u´ltimas operac¸o˜es, a varia´vel ’c’
recebe o resultado.)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas ligadas 38
Estruturas lineares
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas lineares 39
Estruturas lineares em geral: operac¸o˜es t´ıpicas
I selecionar e modificar o k-e´simo elemento;
I inserir um novo elemento entre as posic¸o˜es k e k + 1;
I remover o k-e´simo elemento;
I concatenar duas sequeˆncias;
I desdobrar uma sequeˆncia;
I copiar uma sequeˆncia;
I determinar o tamanho de uma sequeˆncia;
I buscar um elemento que satisfaz uma propriedade;
I ordenar uma sequeˆncia;
I aplicar um procedimento a todos os elementos de uma sequeˆncia;
I . . .
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas lineares 40
Estruturas lineares particulares
I Pilha (stack): inserc¸a˜o e remoc¸a˜o na mesma extremidade da estrutura
I Fila (queue): inserc¸a˜o numa extremidade (fim) e remoc¸a˜o na outra
extremidade (in´ıcio)
I Fila dupla (double ended queue): inserc¸a˜o e remoc¸a˜o em ambas
extremidades da estrutura
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas lineares 41
Pilha: implementac¸a˜o sequencial
. . .. . .
0
topo
empilha (insere)
desempilha (remove)
Pilha vazia:
. . .
0
topo
(-1)
Inicialmente: topo=-1.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas lineares 42
Pilha: implementac¸a˜o sequencial (cont.)
. . .. . .
0
topo
empilha (insere)
desempilha (remove)
typedef
s t r u c t {
i n t topo ;
T e l e m e n t o s [TAM MAX ] ;
} P i l h a ;
vo id Empi lha ( P i l h a ∗p , T x ) {
i f ( (∗ p ) . topo==(TAM MAX−1))
T r a t a E r r o ( ” P i l h a c h e i a ” ) ;
(∗p ) . topo++;
( (∗ p ) . e l e m e n t o s ) [ ( ∗ p ) . topo ] = x ;
}
Exerc´ıcio: a func¸a˜o “Desempilha”.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas lineares 43
Pilha: implementac¸a˜o ligada
topo
. . .
Pilha vazia:
topo
(Uma lista ligada simples.)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas lineares 44
Pilha: implementac¸a˜o ligada (cont.)
topo
. . .
typedef s t r u c t E l e m P i l h a {
T i n f o ;
s t r u c t E l e m P i l h a ∗ prox ;
} ElemPi lha , ∗ P i l h a ;
vo id Empi lha ( P i l h a ∗p , T x ) {
P i l h a q =
m a l l o c ( s i z e o f ( E l e m P i l h a ) ) ;
i f ( q==NULL)
T r a t a E r r o ( ” F a l t a memo´ria ” ) ;
q−> i n f o = x ;
q−Prox = ∗p ;
∗p = q ;
}
Exerc´ıcio: a func¸a˜o “Desempilha”.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas lineares 45
Fila: implementac¸a˜o sequencial
. . . . . . . . .
frente fim
remove insere
Convenc¸a˜o: frente precede o primeiro elemento da fila; consequentemente,
o tamanho da fila e´ dado por fim−frente.
Fila vazia:
. . . . . .
frente
fim
Condic¸a˜o de fila vazia: frente == fim.
Inicialmente: frente = fim = −1.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas lineares 46
Fila: implementac¸a˜o ligada circular
fila
frente
. . .
fim
Fila vazia:
fila
frente
fim
A fila pode ser representada por uma u´nica varia´vel (fila) ou um par de
varia´veis (frente e fim).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas lineares 47
Fila: implementac¸a˜o sequencial circular
n-1 0 1
2
3
... frente
...
fim
...
Convenc¸a˜o: frente precede o primeiro elemento da fila; consequentemente,
o tamanho da fila e´ dado por (fim−frente + n)%n.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas lineares 48
Fila: implementac¸a˜o sequencial circular (cont.)
n-1 0 1
2
3
... frente
...
fim
...
Condic¸o˜es:
I Inicial: frente == fim == 0 (ou qualquer outro valor)
I Fila vazia: frente == fim
I Fila cheia: frente == fim (a mesma condic¸a˜o!)
I Soluc¸a˜o 1: sacrificar uma posic¸a˜o do vetor; a condic¸a˜o de fila cheia
fica: frente == (fim + 1)%n.
I Soluc¸a˜o 2: uma varia´vel adicional inteira com o tamanho da fila ou
booleana indicando se a fila esta´ vazia.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas lineares 49
Fila: implementac¸a˜o sequencial circular (cont.)
n-1 0 1 2
3
... frente
...
fim
...
#d e f i n e TAM MAX FILA 1000
typedef s t r u c t {
i n t f r e n t e , f im ;
T e l e m e n t o s [ TAM MAX FILA ] ;
} F i l a ;
vo id I n s e r e F i l a ( F i l a ∗ f , T x ) {
i f ( (∗ f ) . f r e n t e ==(((∗ f ) . f im+1)%TAM MAX FILA ) )
T r a t a E r r o ( ” F i l a c h e i a ” ) ;
(∗ f ) . f im = ( (∗ f ) . f im+1)%TAM MAX FILA ;
(∗ f ) . e l e m e n t o s [ ( ∗ f ) . f im ] = x ;
}
Exerc´ıcio: a func¸a˜o “RemoveFila”.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Estruturas lineares 50
Aplicac¸o˜es de pilhas
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Aplicac¸o˜es de pilhas 51
Aplicac¸o˜es de pilhas
I Processamento de linguagens parente´ticas:
I linguagens de programac¸a˜o
I XML
I Implementac¸a˜o da recursa˜o
I Percurso de estruturas hiera´rquicas (a´rvores)
I Avaliac¸a˜o expresso˜es em notac¸a˜o po´s-fixa (notac¸a˜o polonesa reversa)
I Transformac¸a˜o entre notac¸o˜es
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Aplicac¸o˜es de pilhas 52
Exemplo de aplicac¸a˜o simples: balanceamento de pareˆnteses
Correto Incorreto
� (
() )
[()] [)
[]()[()[]] ()()[
((([[[]]]))) )(
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Aplicac¸o˜es de pilhas 53
Balanceamento de pareˆnteses (cont.)
Pilha Resto da sequeˆncia
Vazia ([([][()])])
( [([][()])])
([ ([][()])])
([( [][()])])
([([ ][()])])
([( [()])])
([([ ()])])
([([( )])])
([([ ])])
([( )])
([ ])
( )
Vazia �
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Aplicac¸o˜es de pilhas 54
Notac¸o˜es para expresso˜es aritme´ticas
I Infixa:
I um operador una´rio precede o operando
I um operador bina´rio separa os dois operandos
I pareˆnteses indicam prioridades
I Po´s-fixa: os operadores seguem os operandos
I
Pre´-fixa: os operadores precedem os operandos
Exemplos:
infixa po´s-fixa pre´-fixa
a a a
a+ b ab+ +ab
a+ b ∗ c abc ∗+ +a ∗ bc
(a+ b) ∗ c ab+ c∗ ∗+ abc
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Aplicac¸o˜es de pilhas 55
Exemplo: avaliac¸a˜o de expresso˜es sob forma po´s-fixa
Notac¸a˜o infixa: (3 + 5) ∗ 2− (10− 3)/2
Notac¸a˜o po´s-fixa: 3 5 + 2 ∗ 10 3− 2/−
Estados consecutivos da pilha:
Pilha Entrada
Vazia 3 5 + 2 ∗ 10 3− 2/−
3 5 + 2 ∗ 10 3− 2/−
3 5 +2 ∗ 10 3− 2/−
8 2 ∗ 10 3− 2/−
8 2 ∗10 3− 2/−
16 10 3− 2/−
16 10 3− 2/−
16 10 3 −2/−
16 7 2/−
16 7 2 /−
16 3 −
13 Vazia
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Aplicac¸o˜es de pilhas 56
Exemplo: transformac¸a˜o de notac¸a˜o infixa para po´s-fixa
a ∗ b+ c ∗ d e/f − g ∗ h
Entrada infixa: a ∗ b+c ∗ d∧e / f−g ∗h
Sa´ıda po´s-fixa: a b ∗ c d e∧∗f /+g h ∗−
I As vara´veis sa˜o copiadas diretamente para a sa´ıda.
I Os operadores precisam ser lembrados numa pilha.
I Um operador e´ copiado da pilha para a sa´ıda somente quando aparece
na entrada um operador de prioridade menor ou igual.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Aplicac¸o˜es de pilhas 57
Transformac¸a˜o de notac¸a˜o infixa para po´s-fixa (cont.)
Sa´ıda Pilha Entrada
a ∗ b+ c ∗ d ∧ e/f − g ∗ h
a ∗ b+ c ∗ d ∧ e/f − g ∗ h
a ∗ b+ c ∗ d ∧ e/f − g ∗ h
ab ∗ + c ∗ d ∧ e/f − g ∗ h
ab∗ + c ∗ d ∧ e/f − g ∗ h
ab∗ + c ∗ d ∧ e/f − g ∗ h
ab ∗ c + ∗d ∧ e/f − g ∗ h
ab ∗ c +∗ d ∧ e/f − g ∗ h
ab ∗ cd +∗ ∧ e/f − g ∗ h
ab ∗ cd + ∗ ∧ e/f − g ∗ h
ab ∗ cde + ∗ ∧ /f − g ∗ h
ab ∗ cde∧ +∗ /f − g ∗ h
(continua)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Aplicac¸o˜es de pilhas 58
Transformac¸a˜o de notac¸a˜o infixa para po´s-fixa (cont.)
Sa´ıda Pilha Entrada
ab ∗ cde ∧ ∗ + /f − g ∗ h
ab ∗ cde ∧ ∗ +/ f − g ∗ h
ab ∗ cde ∧ ∗f +/ − g ∗ h
ab ∗ cde ∧ ∗f/ + − g ∗ h
ab ∗ cde ∧ ∗f/+ − g ∗ h
ab ∗ cde ∧ ∗f/+ − g ∗ h
ab ∗ cde ∧ ∗f/+ g − ∗ h
ab ∗ cde ∧ ∗f/+ g −∗ h
ab ∗ cde ∧ ∗f/+ gh −∗
ab ∗ cde ∧ ∗f/+ gh∗ −
ab ∗ cde ∧ ∗f/+ gh ∗ −
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Aplicac¸o˜es de pilhas 59
Exemplos de recursa˜o
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de recursa˜o 60
Exemplo 1: func¸a˜o fatorial
i n t f a t o r i a l ( i n t n ) {
i f ( n==0)
r e t u r n 1 ;
e l s e
r e t u r n n∗ f a t o r i a l ( n−1);
}
i n t f a t o r i a l ( i n t n ) {
i n t i , f =1;
f o r ( i =1; i<=n ; i ++)
f = f ∗ i ;
r e t u r n f ;
}
Eficieˆncia: ambos O(n) (n multiplicac¸o˜es).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de recursa˜o 61
Exemplo 2: nu´meros de Fibonacci
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
i n t f i b o ( i n t n ) {
i f ( n<=1)
r e t u r n n ;
e l s e
r e t u r n f i b o ( n−1)+ f i b o ( n−2);
}
i n t f i b o ( i n t n ) {
i n t f 1 =0, f 2 =1, f3 , i ;
f o r ( i =1; i<=n ; i ++) {
f 3 = f 1+f 2 ;
f 1 = f 2 ;
f 2 = f 3 ;
}
r e t u r n f 1 ;
}
Eficieˆncia:
O(1.6n) O(n)
n = 100: ≈ 1020 somas 100 somas
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de recursa˜o 62
Exemplo 3: Torres de Hanoi
A
. .. .
. .
N
B C
(origem) (destino) (auxiliar)
Objetivo: transferir os N discos da torre A para a torre B, usando a torre C
como auxiliar.
Regras:
I um disco de cada vez
I disco de diaˆmetro maior na˜o pode ficar em cima de um disco de
diaˆmetro menor
Soluc¸a˜o recursiva: func¸a˜o Hanoi(org,dest,aux,n).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de recursa˜o 63
Torres de Hanoi: transfereˆncia recursiva de N-1 discos
X
. .. .
. .
N
Y Z
Hanoi(X,Z,Y,N-1)
X Y Z
. .. .
. .
N-1
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de recursa˜o 64
Torres de Hanoi: movimento do maior disco
X Y Z
. .. .
. .
N-1
Move X para Y
X Y Z
. .. .
. .
N-1
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de recursa˜o 65
Torres de Hanoi: transfereˆncia recursiva final de N-1 discos
X Y Z
. .. .
. .
N-1
Hanoi(Z,Y,X,N-1)
X Y
. .. .
. .
N
Z
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de recursa˜o 66
Torres de Hanoi: func¸a˜o Hanoi
vo id Hanoi ( char org , char dest , char aux , i n t n ) {
i f ( n>0) {
Hanoi ( org , aux , dest , n−1);
p r i n t f ( ”Mova de %c para %c\n” , org , d e s t ) ;
Hanoi ( aux , dest , org , n−1);
}
}
I Chamada inicial: Hanoi(’A’,’B’,’C’,64).
I Nu´mero de movimentos: 2N − 1 (prova por induc¸a˜o).
I Este e´ o nu´mero m´ınimo.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de recursa˜o 67
Torres de Hanoi: exemplos de sa´ıda
N=1: N=3:
Mova de A para B Mova de A para B
Mova de A para C
Mova de B para C
N=2: Mova de A para B
Mova de C para A
Mova de A para C Mova de C para B
Mova de A para B Mova de A para B
Mova de C para B
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de recursa˜o 68
Torres de Hanoi: exemplos de sa´ıda (cont.)
N=4
Mova de A para C Mova de C para B
Mova de A para B Mova de C para A
Mova de C para B Mova de B para A
Mova de A para C Mova de C para B
Mova de B para A Mova de A para C
Mova de B para C Mova de A para B
Mova de A para C Mova de C para B
Mova de A para B
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de recursa˜o 69
Exemplo 4: gerac¸a˜o de permutac¸o˜es
Problema: Gerar todas as permutac¸o˜es dos m elementos de um vetor.
. . .
0 k-1 k m-1
. . .
I Suponha uma func¸a˜o Permuta(k,m) que gera (imprime) todas as
permutac¸o˜es dos elementos de 0 a k-1, seguidas dos elementos de k a
m-1.
I A chamada inicial Permuta(m,m) resolveria o problema.
I A soluc¸a˜o consistira´ em trocar o elemento de ı´ndice k-1
consecutivamente com todos os elementos que o precedem e aplicar a
func¸a˜o recursivamente.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de recursa˜o 70
Gerac¸a˜o das permutac¸o˜es (cont.)
Passo recursivo: i=k-1, ..., 0
. . .
0 k-1 k m-1
. . . . . .
i
Troca(i,k-1)
. . .
0 k-1 k m-1
. . . . . .
i
. . .
0 k-1 k m-1
. . . . . .
i
Permuta(k-1,m)
Troca(i,k-1)
. . .
0 k-1 k m-1
. . . . . .
i
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de recursa˜o 71
Gerac¸a˜o das permutac¸o˜es (cont.)
. . .
0 k-1 k m-1
. . .
Func¸a˜o Permuta:
vo id Permuta ( i n t k , i n t m) {
i f ( k==0)
Imprime (m) ;
e l s e {
i n t i ;
f o r ( i=k−1; i >=0; i−−) {
Troca ( i , k−1);
Permuta ( k−1,m) ;
Troca ( i , k−1);
}
}
}
I A func¸a˜o Imprime imprime os m elementos do vetor.
I Chamada inicial: Permuta(m,m).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de recursa˜o 72
Gerac¸a˜o das permutac¸o˜es (cont.)
Sa´ıda de Permuta(2,3)
1 2 3
2 1 3
1 3 2
3 1 2
3 2 1
2 3 1
Desafio: imprimir em ordem lexicogra´fica:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de recursa˜o 73
Exemplos de retrocesso
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de retrocesso 74
Exemplo 1: movimentos do cavalo
Movimentos poss´ıveis do cavalo no jogo de xadrez:
-2
-2
-1
-1
0
0
1
1
2
2
0
12
3
4
5 6
7
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de retrocesso 75
Movimentos do cavalo (cont.)
Um percurso da posic¸a˜o (0,0) ate´ (4,4) (existem
27.419 soluc¸o˜es).
0
0
1
1
2
2
3
3
4
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de retrocesso 76
Movimentos do cavalo (cont.)
Um percurso da posic¸a˜o (0,0) ate´ (4,4) cobrindo todas as posic¸o˜es:
0
0
1
1
2
2
3
3
4
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Obs.: Na˜o existe soluc¸a˜o para o tabuleiro da transpareˆncia anterior
(provar!).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de retrocesso 77
Movimentos do cavalo (cont.)
Tipos de soluc¸a˜o:
1. Achar uma soluc¸a˜o
2. Achar uma soluc¸a˜o que cobre todas as posic¸o˜es livres
3. Enumerar todas as soluc¸o˜es
Observac¸a˜o: Esta na˜o e´ a melhor maneira de resolver este problema mas
ilustra bem o mecanismo geral de retrocesso.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de retrocesso 78
Movimentos do cavalo (cont.)
-2
-2
-1
-1
0
0
1
1
2
2
0
12
3
4
5 6
7
#d e f i n e TAM MAX 20
#d e f i n e NUM MOV 8
typedef enum { f a l s e , t r u e } Boolean ;
i n t tab [TAM MAX ] [ TAM MAX ] ;
i n t d l [NUM MOV] = { −1, −2, −2, −1, 1 , 2 , 2 , 1 } ;
i n t dc [NUM MOV] = { 2 , 1 , −1, −2, −2, −1, 1 , 2 } ;
vo id ImprimeTab ( i n t tam ) {
i n t i , j ;
f o r ( i =0; i<tam ; i ++) {
f o r ( j =0; j<tam ; j ++)
p r i n t f ( ”%5d” , tab [ i ] [ j ] ) ;
p r i n t f ( ”\n” ) ;
}
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de retrocesso 79
Movimentos do cavalo: achar uma soluc¸a˜o
Boolean TentaMovimento ( i n t tam , i n t num , i n t l i n ,
i n t c o l , i n t ld , i n t cd ) {
i n t k , lp , cp ;
Boolean r e s = f a l s e ;
i f ((0<= l i n ) && ( l i n <tam ) && (0<= c o l ) &&
( c o l<tam ) && ( tab [ l i n ] [ c o l ]==0)) {
tab [ l i n ] [ c o l ] = num ;
i f ( ( l i n==l d ) && ( c o l==cd ) ) {
r e s = t r u e ; ImprimeTab ( tam ) ;
} e l s e { k = 0 ;
do { l p = l i n+d l [ k ] ; cp = c o l+dc [ k ] ;
r e s = TentaMovimento ( tam , num+1, lp , cp , ld , cd ) ;
k++;
} whi le ( ( ! r e s ) && ( k<NUM MOV) ) ;
}
tab [ l i n ] [ c o l ] = 0 ;
}
r e t u r n r e s ;
}
Chamada inicial: TentaMovimento(tam,1,lo,co,ld,cd)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de retrocesso 80
Movimentos do cavalo: exemplo de entrada e sa´ıda
0
0
1
1
2
2
3
3
4
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Entrada S a ı´ d a
−−−−−−−−−− −−−−−−−−−−−−−−−−−−−−−−−
5 1 4 9 12 −1
0 0 10 13 6 3 0
4 4 5 2 11 8 0
0 4 0 7 14 0 −1
3 4 −1 0 0 0 15
4 0
−1 −1
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de retrocesso 81
Movimentos do cavalo: achar uma soluc¸a˜o completa
Boolean TentaMovimento ( i n t tam , i n t num , i n t l i n ,
i n t c o l , i n t ld , i n t cd , i n t noc ) {
i n t k , lp , cp ;
Boolean r e s = f a l s e ;
i f ((0<= l i n ) && ( l i n <tam ) && (0<= c o l ) &&
( c o l<tam ) && ( tab [ l i n ] [ c o l ]==0)) {
tab [ l i n ] [ c o l ] = num ;
i f ( ( l i n==l d ) && ( c o l==cd ) && ( ( noc+num)==tam∗tam ) ) {
r e s = t r u e ; ImprimeTab ( tam ) ;
} e l s e { k = 0 ;
do { l p = l i n+d l [ k ] ; cp = c o l+dc [ k ] ;
r e s =
TentaMovimento ( tam , num+1, lp , cp , ld , cd , noc ) ;
k++;
} whi le ( ( ! r e s ) && ( k<NUM MOV) ) ;
}
tab [ l i n ] [ c o l ] = 0 ;
}
r e t u r n r e s ;
}
Chamada inicial: TentaMovimento(tam,1,lo,co,ld,cd,ocupadas)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de retrocesso 82
Movimentos do cavalo: achar todas as soluc¸o˜es
vo id TentaMovimento ( i n t tam , i n t num , i n t l i n ,
i n t c o l , i n t ld , i n t cd ) {
i n t k , lp , cp ;
i f ((0<= l i n ) && ( l i n <tam ) && (0<= c o l ) &&
( c o l<tam ) && ( tab [ l i n ] [ c o l ]==0)) {
tab [ l i n ] [ c o l ] = num ;
i f ( ( l i n==l d ) && ( c o l==cd ) ) {
ImprimeTab ( tam ) ;
} e l s e { k = 0 ;
do { l p = l i n+d l [ k ] ; cp = c o l+dc [ k ] ;
TentaMovimento ( tam , num+1, lp , cp , ld , cd ) ;
k++;
} whi le ( k<NUM MOV) ;
}
tab [ l i n ] [ c o l ] = 0 ;
}
}
Chamada inicial: TentaMovimento(tam,1,lo,co,ld,cd)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de retrocesso 83
Exemplo 2: distaˆncia de edic¸a˜o
RECURSA˜O E RETROCESSO
RCURC¸A˜O ER RTROCESOS
ˆ ˆ ˆ ˆ ˆ ˆ
| | | | | |
I S R I I R
I Operac¸o˜es elementares:
I A: avanc¸o (subentendido)
I I: inserc¸a˜o
I S: substituic¸a˜o
I R: remoc¸a˜o
I Cada operac¸a˜o recebe um custo (avanc¸o, em geral, zero)
I Problema: achar uma sequeˆncia de operac¸o˜es que torna as cadeias
iguais ao custo total m´ınimo.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de retrocesso 84
Distaˆncia de edic¸a˜o: func¸a˜o Distancia
i n t D i s t a n c i a ( char ∗ t e s t e , char ∗ c o r r e t a ) {
i n t dIns , dRem , dSub ;
i f ( ( (∗ t e s t e )==NUL CHAR) && ( (∗ c o r r e t a )==NUL CHAR ) )
r e t u r n 0 ;
d I n s = dRem = dSub = INT MAX ;
i f ( ( (∗ t e s t e )!=NUL CHAR) && ( (∗ c o r r e t a )!=NUL CHAR) &&
( (∗ t e s t e )==(∗ c o r r e t a ) ) )
r e t u r n D i s t a n c i a ( t e s t e +1, c o r r e t a +1);
i f ( ( (∗ t e s t e )!=NUL CHAR) && ( (∗ c o r r e t a )!=NUL CHAR ) )
dSub = custoSub+D i s t a n c i a ( t e s t e +1, c o r r e t a +1);
i f ( (∗ t e s t e )!=NUL CHAR)
dRem = custoRem+D i s t a n c i a ( t e s t e +1, c o r r e t a ) ;
i f ( (∗ c o r r e t a )!=NUL CHAR)
d I n s = c u s t o I n s+D i s t a n c i a ( t e s t e , c o r r e t a +1);
r e t u r n min ( d Ins , min (dRem , dSub ) ) ;
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de retrocesso 85
Distaˆncia de edic¸a˜o: desafios
I Melhorar o desempenho do algoritmo: o algoritmo e´ exponencial na˜o
sendo via´vel, sob esta forma, em aplicac¸o˜es pra´ticas
I Imprimir o nu´mero de operac¸o˜es de cada tipo (avanc¸o, inserc¸a˜o,
remoc¸a˜o e substituic¸a˜o) para obter a soluc¸a˜o
I Imprimir a sequeˆncia de operac¸o˜es para obter a soluc¸a˜o
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Exemplos de retrocesso 86
Eliminac¸a˜o da recursa˜o
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Eliminac¸a˜o da recursa˜o 87
Esquema de func¸a˜o recursiva
vo id Exemplo (T1 x1 , T2 x2 , . . . ) {
S1 y1 ; S2 y2 ; . . . ;
C i ; /∗ Comandos i n i c i a i s ∗/
i f (E ( . . . ) ) {
C0 ; /∗ Caso base ∗/
} e l s e { /∗ Chamadas r e c u r s i v a s ∗/
C1 ; Exemplo ( e11 , e12 , . . . ) ;
C2 ; Exemplo ( e21 , e22 , . . . ) ;
C3 ; Exemplo ( e31 , e32 , . . . ) ;
. . . ;
Cm; Exemplo (em1 , em2 , . . . ) ;
Cf ;
}
}
Os s´ımbolos Ci, C0, C1, . . ., Cm e Cf representam sequeˆncias,
possivelmente vazias, de comandos.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Eliminac¸a˜o da recursa˜o 88
Esquema de eliminac¸a˜o da recursa˜o
v o i d Exemplo (T1 x1 , T2 x2 , . . . ) {
S1 y1 ; S2 y2 ; . . . ;
C i ; /∗ Comandos i n i c i a i s ∗/
i f (E ( . . . ) ) {
C0 ; /∗ Caso base ∗/
} e l s e {
/∗ Chamadas r e c u r s i v a s ∗/
C1 ; Exemplo ( e11 , e12 , . . . ) ;
C2 ; Exemplo ( e21 , e22 , . . . ) ;
C3 ; Exemplo ( e31 , e32 , . . . ) ;
. . . ;
Cm; Exemplo (em1 , em2 , . . . ) ;
Cf ;
}
}
typedef enum {chamada1 , chamada2 , chamada3 , . . . } Chamadas ;
typedef enum { ent rada , s a i d a , r e t o r n o } Acoes ;
vo id Exemplo (T1 x1 , T2 x2 , . . . ) {
S1 y1 ; S2 y2 ; . . . ; /∗ v a
r i a´ v e i s l o c a i s o r i g i n a i s ∗/
T1 t1 , T2 t2 , . . . ; /∗ v a r i a´ v e i s t e m p o r a´ r i a s ∗/
P i l h a f ; Chamadas ch ; Acoes acao ;
I n i c i a l i z a P i l h a (& f ) ; acao = e n t r a d a ;
do {
switch ( acao ) {
case ( e n t r a d a ) : . . . break ;
case ( r e t o r n o ) : . . . break ;
case ( s a i d a ) : break ;
}
} whi le ( acao != s a i d a ) ;
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Eliminac¸a˜o da recursa˜o 89
Esquema de eliminac¸a˜o da recursa˜o (cont.)
v o i d Exemplo (T1 x1 , T2 x2 , . . . ) {
S1 y1 ; S2 y2 ; . . . ;
C i ; /∗ Comandos i n i c i a i s ∗/
i f (E ( . . . ) ) {
C0 ; /∗ Caso base ∗/
} e l s e {
/∗ Chamadas r e c u r s i v a s ∗/
C1 ; Exemplo ( e11 , e12 , . . . ) ;
C2 ; Exemplo ( e21 , e22 , . . . ) ;
C3 ; Exemplo ( e31 , e32 , . . . ) ;
. . . ;
Cm; Exemplo (em1 , em2 , . . . ) ;
Cf ;
}
}
case ( e n t r a d a ) :
Ci ; /∗ Comandos i n i c i a i s ∗/
i f (E ( . . . ) ) {
C0 ; acao = r e t o r n o ; /∗ Caso base ∗/
} e l s e { /∗ P r i m e i r a chamada r e c u r s i v a ∗/
C1 ; Empi lha ( f , x1 , x2 , . . . , y1 , y2 , . . . , chamada1 ) ;
t1 = e11 ; t2 = e12 ; . . . ;
x1 = t1 ; x2 = t2 ; . . . ; /∗ R e c a l c u l a argumentos ∗/
}
break ;
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Eliminac¸a˜o da recursa˜o 90
Esquema de eliminac¸a˜o da recursa˜o (cont.)
v o i d Exemplo (T1 x1 , T2 x2 , . . . ) {
S1 y1 ; S2 y2 ; . . . ;
C i ; /∗ Comandos i n i c i a i s ∗/
i f (E ( . . . ) ) {
C0 ; /∗ Caso base ∗/
} e l s e {
/∗ Chamadas r e c u r s i v a s ∗/
C1 ; Exemplo ( e11 , e12 , . . . ) ;
C2 ; Exemplo ( e21 , e22 , . . . ) ;
C3 ; Exemplo ( e31 , e32 , . . . ) ;
. . . ;
Cm; Exemplo (em1 , em2 , . . . ) ;
Cf ;
}
}
case ( r e t o r n o ) :
i f ( P i l h a V a z i a ( f ) ) acao = s a i d a ;
e l s e {
Desempi lha ( f ,&x1 ,&x2 , . . . , & y1 ,&y2 , . . . , & ch ) ;
switch ( ch ) {
case ( chamada1 ) :
C2 ; Empi lha ( f , x1 , x2 , . . . , y1 , y2 , . . . , chamada2 ) ;
t1 = e21 ; t2 = e22 ; . . . ;
x1 = t1 ; x2 = t2 ; . . . ;
acao = e n t r a d a ; break ;
case ( chamada2 ) :
C3 ; Empi lha ( f , x1 , x2 , . . . , y1 , y2 , . . . , chamada3 ) ;
t1 = e31 ; t2 = e32 ; . . . ;
x1 = t1 ; x2 = t2 ; . . . ;
acao = e n t r a d a ; break ;
. . . ;
case ( chamadam ) :
Cf ; break ;
} /∗ s w i t c h ( ch ) ∗/
}
break ;
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Eliminac¸a˜o da recursa˜o 91
Exemplo 1: func¸a˜o fatorial
i n t f a t o r i a l ( i n t n ) {
i f ( n==0)
r e t u r n 1 ;
e l s e
r e t u r n n∗ f a t o r i a l ( n−1);
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Eliminac¸a˜o da recursa˜o 92
Func¸a˜o fatorial (cont.)
i n t f a t o r i a l ( i n t n ) {
i f ( n==0)
r e t u r n 1 ;
e l s e
r e t u r n n∗ f a t o r i a l ( n−1);
}
typedef enum {chamada1} Chamadas ;
typedef enum { ent rada , s a i d a , r e t o r n o } Acoes ;
i n t f a t o r i a l ( i n t n ) {
i n t r e s , t1 ;
P i l h a f ; Chamadas ch ; Acoes acao ;
I n i c i a l i z a P i l h a (& f ) ; acao = e n t r a d a ;
do {
switch ( acao ) {
case ( e n t r a d a ) : . . . break ;
case ( r e t o r n o ) : . . . break ;
case ( s a i d a ) : break ;
}
} whi le ( acao != s a i d a ) ;
r e t u r n r e s ;
} /∗ f a t o r i a l ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Eliminac¸a˜o da recursa˜o 93
Func¸a˜o fatorial (cont.)
i n t f a t o r i a l ( i n t n ) {
i f ( n==0)
r e t u r n 1 ;
e l s e
r e t u r n n∗ f a t o r i a l ( n−1);
}
case ( e n t r a d a ) :
i f ( n==0) {
r e s = 1 ; acao = r e t o r n o ;
} e l s e {
Empi lha ( f , n , chamada1 ) ;
t1 = n ; n = t1−1;
}
break ;
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Eliminac¸a˜o da recursa˜o 94
Func¸a˜o fatorial (cont.)
i n t f a t o r i a l ( i n t n ) {
i f ( n==0)
r e t u r n 1 ;
e l s e
r e t u r n n∗ f a t o r i a l ( n−1);
}
case ( r e t o r n o ) :
i f ( P i l h a V a z i a ( f ) ) acao = s a i d a ;
e l s e {
Desempi lha ( f ,&n,& ch ) ;
switch ( ch ) {
case ( chamada1 ) :
r e s = n∗ r e s ;
break ;
}
break ;
Obs.: Note como neste caso a varia´vel res e´ usada para guardar o
resultado da func¸a˜o.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Eliminac¸a˜o da recursa˜o 95
Exemplo 2: func¸a˜o Hanoi
vo id Hanoi ( char org , char dest , char aux , i n t n ) {
i f ( ! ( n>0))
;
e l s e {
Hanoi ( org , aux , dest , n−1);
p r i n t f ( ”Mova de %c para %c\n” , org , d e s t ) ;
Hanoi ( aux , dest , org , n−1);
}
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Eliminac¸a˜o da recursa˜o 96
Func¸a˜o Hanoi (cont.)
v o i d Hanoi ( char org , char dest , char aux , i n t n ) {
i f ( ! ( n>0))
;
e l s e {
Hanoi ( org , aux , dest , n−1);
p r i n t f ( ”Mova de %c para %c\n” , org , d e s t ) ;
Hanoi ( aux , dest , org , n−1);
}
}
typedef enum {chamada1 , chamada2 } ;
typedef enum { ent rada , s a i d a , r e t o r n o } Acoes ;
vo id Hanoi ( char org , char dest , char aux , i n t n ) {
char t1 ; char t2 ; char t3 ; i n t t4 ;
P i l h a f ; Chamadas ch ; Acoes acao ;
I n i c i a l i z a P i l h a (& f ) ; acao = e n t r a d a ;
do {
switch ( acao ) {
case ( e n t r a d a ) : . . . ; break ;
case ( r e t o r n o ) : . . . ; break ;
case ( s a i d a ) : break ;
}
} whi le ( acao != s a i d a ) ;
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Eliminac¸a˜o da recursa˜o 97
Func¸a˜o Hanoi (cont.)
v o i d Hanoi ( char org , char dest , char aux , i n t n ) {
i f ( ! ( n>0))
;
e l s e {
Hanoi ( org , aux , dest , n−1);
p r i n t f ( ”Mova de %c para %c\n” , org , d e s t ) ;
Hanoi ( aux , dest , org , n−1);
}
}
case ( e n t r a d a ) :
i f ( ! ( n>0)) {
acao = r e t o r n o ;
} e l s e {
Empi lha ( f , org , dest , aux , n , chamada1 ) ;
t1 = org ; t2 = aux ; t3 = d e s t ; t4 = n−1;
org = t1 ; d e s t = t2 ; aux = t3 ; n = t4 ;
}
break ;
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Eliminac¸a˜o da recursa˜o 98
Func¸a˜o Hanoi (cont.)
v o i d Hanoi ( char org , char dest , char aux , i n t n ) {
i f ( ! ( n>0))
;
e l s e {
Hanoi ( org , aux , dest , n−1);
p r i n t f ( ”Mova de %c para %c\n” , org , d e s t ) ;
Hanoi ( aux , dest , org , n−1);
}
}
case ( r e t o r n o ) :
i f ( P i l h a V a z i a ( f ) )
acao = s a i d a ;
e l s e {
Desempi lha ( f ,& org ,& dest ,& aux ,&n,& ch ) ;
switch ( ch ) {
case ( chamada1 ) :
p r i n t f ( ”Mova de %c para %c\n” , org , d e s t ) ;
Empi lha ( f , org , dest , aux , n , chamada2 ) ;
t1 = aux ; t2 = d e s t ; t3 = org ; t4 = n−1;
org = t1 ; d e s t = t2 ; aux = t3 ; n = t4 ;
acao = e n t r a d a ;
break ;
case ( chamada2 ) :
break ;
}
break ;
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Eliminac¸a˜o da recursa˜o 99
Exemplo de eliminac¸a˜o da recursa˜o caudal
Aplica´vel quando a u´ltima ac¸a˜o dentro do corpo da func¸a˜o e´ uma
chamada recursiva: reaproveita o mesmo registro de ativac¸a˜o da func¸a˜o,
mudando os valores dos argumentos.
vo id Hanoi ( char org , char dest , char aux , i n t n ) {
i f ( n>0) {
Hanoi ( org , aux , dest , n−1);
p r i n t f ( ”Mova de %c para %c\n” , org , d e s t ) ;
Hanoi ( aux , dest , org , n−1);
}
}
vo id Hanoi ( char org , char dest , char aux , i n t n ) {
char t ;
whi le ( n>0) {
Hanoi ( org , aux , dest , n−1);
p r i n t f ( ”Mova de %c para %c\n” , org , d e s t ) ;
t = org ; org = aux ; aux = t ;
}
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Eliminac¸a˜o da recursa˜o 100
Recursa˜o mu´tua:
Ana´lise sinta´tica
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Recursa˜o mu´tua: Ana´lise sinta´tica 101
Exemplo simples de recursa˜o mu´tua
i n t g ( i n t n ) ;
i n t f ( i n t n ) {
i f ( n==0)
r e t u r n 0 ;
e l s e
r e t u r n g ( n−1);
}
i n t g ( i n t n ) {
i f ( n==0)
r e t u r n 1 ;
e l s e
r e t u r n f ( n−1);
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Recursa˜o mu´tua: Ana´lise sinta´tica 102
Ana´lise de expresso˜es
Expresso˜es com operadores bina´rios ‘+’, ‘−’, ‘∗’, ‘/’ e pareˆnteses ‘(’ e ‘)’:
e = t1 ⊕ t2 ⊕ · · · ⊕ tn, n ≥ 1
t = f1 ⊗ f2 ⊗ · · · ⊗ fn, n ≥ 1
f = x ou f = ( e )
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Recursa˜o mu´tua: Ana´lise sinta´tica 103
Programa de traduc¸a˜o de infixa para po´s-fixa:
char e n t r a d a [TAM MAX ] ;
char ∗pe ;
vo id E x p r e s s a o ( ) ;
vo id Termo ( ) ;
vo id F a t o r ( ) ;
vo id InPos ( ) {
pe = &e n t r a d a [ 0 ] ;
E x p r e s s a o ( ) ;
i f ( (∗ pe )!= ’ \0 ’ )
E r r o ( ) ;
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Recursa˜o mu´tua: Ana´lise sinta´tica 104
Fator
f = x ou f = ( e )
vo id F a t o r ( ) {
char c o r r e n t e = ∗pe ;
switch ( c o r r e n t e ) {
case ’ a ’ : case ’ b ’ : . . . : case ’ z ’ :
S a i ( c o r r e n t e ) ; pe++; break ;
case ’ ( ’ :
pe++;
E x p r e s s a o ( ) ;
i f ( (∗ pe)== ’ ) ’ )
pe++;
e l s e
E r r o ( ) ;
break ;
d e f a u l t :
E r r o ( ) ;
}
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Recursa˜o mu´tua: Ana´lise sinta´tica 105
Termo
t = f1 ⊗ f2 ⊗ · · · ⊗ fn, n ≥ 1
vo id Termo ( ) {
char op ;
F a t o r ( ) ;
do {
op = ∗pe ;
i f ( ( op==’ ∗ ’ ) | | ( op==’ / ’ ) ) {
pe++;
F a t o r ( ) ;
S a i ( op ) ;
} e l s e
break ; /∗ do ∗/
} whi le ( t r u e ) ;
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Recursa˜o mu´tua: Ana´lise sinta´tica 106
Expressa˜o
e = t1 ⊕ t2 ⊕ · · · ⊕ tn, n ≥ 1
vo id E x p r e s s a o ( ) {
char op ;
Termo ( ) ;
do {
op = ∗pe ;
i f ( ( op==’+ ’ ) | | ( op==’− ’ ) ) {
pe++;
Termo ( ) ;
S a i ( op ) ;
} e l s e
break ; /∗ do ∗/
} whi le ( t r u e ) ;
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Recursa˜o mu´tua: Ana´lise sinta´tica 107
Operador de exponenciac¸a˜o
Fator redefinido:
f = p1 ∧ p2 ∧ · · · ∧ pn, n ≥ 1
Prima´rio:
p = x ou p = ( e )
Prioridade? Soluc¸a˜o:
f = p ou f = p ∧ f
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Recursa˜o mu´tua: Ana´lise sinta´tica 108
Fator redefinido
f = p ou f = p ∧ f
vo id F a t o r ( ) {
P r i m a r i o ( ) ;
i f ( (∗ pe)== ’ ˆ ’ ) {
pe++;
F a t o r ( ) ;
S a i ( ’ ˆ ’ ) ;
}
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Recursa˜o mu´tua: Ana´lise sinta´tica 109
Prima´rio
p = x ou p = ( e )
vo id P r i m a r i o ( ) {
c o r r e n t e = ∗pe ;
switch ( c o r r e n t e ) {
case ’ a ’ : case ’ b ’ : . . . : case ’ z ’ :
S a i ( c o r r e n t e ) ; pe++; break ;
case ’ ( ’ :
pe++;
E x p r e s s a o ( ) ;
i f ( (∗ pe)== ’ ) ’ )
pe++;
e l s e
E r r o ( ) ;
break ;
d e f a u l t :
E r r o ( ) ;
}
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Recursa˜o mu´tua: Ana´lise sinta´tica 110
Analogia para expresso˜es e termos
e = t ou e = e⊕ t
t = f ou t = t⊗ f
Problemas:
I como distinguir as alternativas
I repetic¸a˜o infinita no segundo caso (recursa˜o esquerda)
vo id E x p r e s s a o ( ) {
. . . ;
i f ( ? ? ? )
Termo ( ) ;
e l s e
E x p r e s s a o ( ) ;
. . .
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Recursa˜o mu´tua: Ana´lise sinta´tica 111
A´rvores bina´rias
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 112
Exemplo de a´rvore bina´ria 1: pedigree
Sugarted’s Bonnie
Carina de Wood Ladge
Matarazzo’s Beauty
Lady
Weberly
Johnson
Fancy Boots
Scotland dos Seis Irma˜os
Arisca dos
Seis Irma˜os
Ator dos
Seis Irma˜os
Jesse James
R. J. B. Helvetia
Carina de
Wood Ladge
R. J. B.
Sean
R. J. B. Hill
Lakeview
Lois
R. J. B.
Sean
I Alguns nomes sa˜o repetidos: eles devem ser tratados como instaˆncias
separadas.
I Pela pro´pria natureza da a´rvore, cada elemento tem dois
predecessores: a´rvore bina´ria.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 113
Exemplo de a´rvore bina´ria 2: a´rvore de decisa˜o
x1 ≤ x2
x2 ≤ x3
x1, x2, x3 x1 ≤ x3
x1, x3, x2 x3, x1, x2
x2 ≤ x3
x1 ≤ x3
x2, x1, x3 x2, x3, x1
x3, x2, x1
V F
V F
V F
V F
V F
I A a´rvore representa as deciso˜es tomadas por um algoritmo de
ordenac¸a˜o usando operac¸o˜es de comparac¸a˜o; V: verdadeiro, F: falso.
I Devido a` natureza das comparac¸o˜es, a a´rvore e´ bina´ria.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 114
Exemplo de a´rvore geral 1: descendentes
Indo-
Europeu
Balto-
Eslavo
Ba´ltico
Leta˜o
Lituano
Eslavo
Checo
Russo
Poloneˆs
Ita´lico Latim
Catala˜o
Italiano
Franceˆs
Castelhano
Portugueˆs
Indo-
Iraniano Persa
Antigo Persa
Hindustano
Urdu
Hindi
Germaˆnico
Germaˆnico
Setentrional
Sueco
Noruegueˆs
Dinamarqueˆs
Germaˆnico
Ocidental
Holandeˆs
Alema˜o
Ingleˆs
Grego
Cla´ssico
Grego Moderno
I A a´rvore e´ incompleta e na˜o necessariamente exata.
I Cada elemento pode ter um nu´mero varia´vel de sucessores: a´rvore
geral.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 115
Exemplo de a´rvore geral 2: descendentes
Fam´ılia
Subfam´ılia
Tribo
Geˆnero
Espe´cie
Subespe´cie
Hominidae
Homininae
Hominini
Homo
Homo
sapiens
Homo sapiens
sapiens
Homo
habilis
Homo
neander-
thalensis
. . .
Pan
Chimpanze´ Bonobo
Gorillini
Gorilla
Gorila
Ponginae
Pongo
Orangotango
I A´rvore da fam´ılia Hominidae determinada por comparac¸a˜o de DNA de
va´rias espe´cies (incompleta).
I Cada elemento pode ter um nu´mero varia´vel de sucessores: a´rvore
geral.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 116
Exemplo de a´rvore geral 3: organograma
UNICAMP
IC
DSC DSI DTC
IMECC
DE DM DMA
FEEC
DCA DEB DT
FCM
DAP DAN DTO
. . .
. . . . . .
Obs.: A UNICAMP tem 21 unidades acadeˆmicas. Algumas unidades teˆm
mais de 10 departamentos.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 117
Definic¸a˜o de a´rvore bina´ria
Uma a´rvore bina´ria e´ um conjunto de no´s que:
I ou e´ vazio (a´rvore bina´ria vazia)
I ou conte´m um no´ especial denominado raiz da a´rvore e o resto do
conjunto esta´ particionado em duas a´rvores bina´rias disjuntas
(possivelmente vazias), denominadas suba´rvore esquerda e suba´rvore
direita.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 118
Representac¸a˜o gra´fica, convenc¸o˜es e conceitos
n´ıvel 1
n´ıvel 2
n´ıvel 3
n´ıvel 4
A
B
D E
G
C
F
H
Raiz da a´rvore: A
Filho esquerdo de A: B Filho direito de A: C
Pai de F : C Irma˜o de E: D
Descendentes de B: B, D, E e G Antepassados de H: H, F , C e A
Folhas: D, G e H No´s internos: todos exceto as folhas
N´ıveis: indicados na figura Altura (profundidade) – n´ıvel ma´ximo: 4
Suba´rvores bina´rias vazias: 9 Suba´rvores bina´rias na˜o vazias: 7
Obs.: Alguns autores comec¸am a numerac¸a˜o dos n´ıveis a partir de zero.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas
de Programac¸a˜o A´rvores bina´rias 119
Fatos sobre a´rvores bina´rias
I Uma a´rvore bina´ria com n no´s tem:
I altura ma´xima n
I altura m´ınima dlog2(n+ 1)e
I suba´rvores vazias: n+ 1
I suba´rvores na˜o vazias: n− 1 (se n > 0)
I Uma a´rvore bina´ria de altura h tem:
I no m´ınimo h no´s
I no ma´ximo 2h − 1 no´s
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 120
Representac¸a˜o ligada comum
p
A
B C
D E F
G H
O acesso a todos os no´s da a´rvore pode ser realizado atrave´s de um
apontador para a raiz.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 121
Representac¸a˜o ligada com treˆs apontadores
p
A
B
D E
G
C
F
H
O terceiro apontador possibilita descer e subir pela estrutura,
analogamente a`s listas duplamente ligadas.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 122
Representac¸a˜o com o campo pai apenas
A
B C
D E F
G H
Problemas:
I E´ necessa´rio haver acesso (apontadores) pelo menos a todas as folhas.
I Na˜o e´ poss´ıvel distinguir entre os filhos esquerdos e direitos.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 123
Representac¸a˜o sequ¨encial: a´rvores bina´rias completas
A
B
C
D E
F
G H
I
J
K L
M
N O
0
1 2
3 4 5 6
7 8 9 10 11 12 13 14
No´ n:

filho esquerdo: 2n+ 1 (n ≥ 0)
filho direito: 2n+ 2 (n ≥ 0)
pai: b(n− 1)/2c (n > 0)
A
0
B
1
I
2
C
3
F
4
J
5
M
6
D
7
E
8
G
9
H
10
K
11
L
12
N
13
O
14
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 124
Representac¸a˜o sequ¨encial: a´rvores bina´rias quase completas
A
B
C
D E
F
G H
I
J
K
M
0
1 2
3 4 5 6
7 8 9 10 11
A
0
B
1
I
2
C
3
F
4
J
5
M
6
D
7
E
8
G
9
H
10
K
11
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 125
Percursos em profundidade
I Pre´-ordem:
Visitar a raiz
Percorrer a suba´rvore esquerda em pre´-ordem
Percorrer a suba´rvore direita em pre´-ordem
I Po´s-ordem:
Percorrer a suba´rvore esquerda em po´s-ordem
Percorrer a suba´rvore direita em po´s-ordem
Visitar a raiz
I Inordem (ou ordem sime´trica):
Percorrer a suba´rvore esquerda em inordem
Visitar a raiz
Percorrer a suba´rvore direita em inordem
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 126
Exemplos de percurso em profundidade
A
B
D E
G
C
F
H
Pre´-ordem: A,B,D,E,G,C,F ,H
Po´s-ordem: D,G,E,B,H,F ,C,A
Inordem: D,B,G,E,A,F ,H,C
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 127
Percurso em largura
Percurso por n´ıveis, da esquerda para a direita:
n´ıvel 1
n´ıvel 2
n´ıvel 3
n´ıvel 4
A
B
D E
G
C
F
H
Percurso: A,B,C,D,E,F ,G,H
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 128
Implementac¸a˜o recursiva de percursos
typedef s t r u c t NoArvBin {
T i n f o ;
s t r u c t NoArvBin ∗ esq , ∗ d i r ;
} NoArvBin , ∗ArvBin ;
vo id PreOrdem ( ArvBin p ) {
i f ( p!=NULL) {
V i s i t a ( p ) ;
PreOrdem ( p−>esq ) ;
PreOrdem ( p−>d i r ) ;
}
} /∗ PreOrdem ∗/
vo id InOrdem ( ArvBin p ) {
i f ( p!=NULL) {
InOrdem ( p−>esq ) ;
V i s i t a ( p ) ;
InOrdem ( p−>d i r ) ;
}
} /∗ InOrdem ∗/
vo id PosOrdem ( ArvBin p ) {
i f ( p!=NULL) {
PosOrdem ( p−>esq ) ;
PosOrdem ( p−>d i r ) ;
V i s i t a ( p ) ;
}
} /∗ PosOrdem ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 129
Eliminac¸a˜o da recursa˜o caudal
vo id PreOrdem ( ArvBin p ) {
i f ( p!=NULL) {
V i s i t a ( p ) ;
PreOrdem ( p−>esq ) ;
PreOrdem ( p−>d i r ) ;
}
} /∗ PreOrdem ∗/
vo id PreOrdem ( ArvBin p ) {
whi le ( p!=NULL) {
V i s i t a ( p ) ;
PreOrdem ( p−>esq ) ;
p = p−>d i r ;
}
} /∗ PreOrdem ∗/
I Transformac¸a˜o ana´loga pode ser feita para a inordem.
I E a po´s-ordem?
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 130
Percurso em pre´-ordem, usando uma pilha expl´ıcita
A figura indica a situac¸a˜o inicial e final do percurso de uma a´rvore
arbitra´ria (pode ser vazia). Inicialmente, o apontador para a a´rvore deve
estar no topo da pilha. Terminado o percurso, a pilha tera´ um elemento a
menos.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 131
Percurso em pre´-ordem, usando uma pilha expl´ıcita (cont.)
X
E D
Visita X Percorre E Percorre D
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 132
Percurso em pre´-ordem, usando uma pilha (cont.)
vo id PreOrdem ( ArvBin p ) {
P i l h a p l ;
I n i c i a l i z a P i l h a (& p l ) ;
Empi lha (& pl , p ) ;
do {
Desempi lha (& pl ,&p ) ;
i f ( p!=NULL) {
V i s i t a ( p ) ;
Empi lha (& pl , p−>d i r ) ;
Empi lha (& pl , p−>esq ) ;
}
} whi le ( ! P i l h a V a z i a ( p l ) ) ;
} /∗ PreOrdem ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 133
Percurso em largura, usando uma fila
Os no´s da a´rvore a serem visitados sa˜o guardados numa fila.
X
E D
n´ıvel k
n´ıvel k+1
Visita X
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 134
Percurso em largura, usando uma fila (cont.)
vo id L a r g u r a ( ArvBin p ) {
F i l a f l ;
I n i c i a l i z a F i l a (& f l ) ;
I n s e r e F i l a (& f l , p ) ;
do {
RemoveFi la (& f l ,&p ) ;
i f ( p!=NULL) {
V i s i t a ( p ) ;
I n s e r e F i l a (& f l , p−>esq ) ;
I n s e r e F i l a (& f l , p−>d i r ) ;
}
} whi le ( ! F i l a V a z i a ( f l ) ) ;
} /∗ L a r g u r a ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 135
Comparac¸a˜o dos percursos em pre´-ordem e em largura
vo id PreOrdem ( ArvBin p ) {
P i l h a p l ;
I n i c i a l i z a P i l h a (& p l ) ;
Empi lha (& pl , p ) ;
do {
Desempi lha (& pl ,&p ) ;
i f ( p!=NULL) {
V i s i t a ( p ) ;
Empi lha (& pl , p−>d i r ) ;
Empi lha (& pl , p−>esq ) ;
}
} whi le ( ! P i l h a V a z i a ( p l ) ) ;
} /∗ PreOrdem ∗/
vo id L a r g u r a ( ArvBin p ) {
F i l a f l ;
I n i c i a l i z a F i l a (& f l ) ;
I n s e r e F i l a (& f l , p ) ;
do {
RemoveFi la (& f l ,&p ) ;
i f ( p!=NULL) {
V i s i t a ( p ) ;
I n s e r e F i l a (& f l , p−>esq ) ;
I n s e r e F i l a (& f l , p−>d i r ) ;
}
} whi le ( ! F i l a V a z i a ( f l ) ) ;
} /∗ L a r g u r a ∗/
Quase ideˆnticos, exceto a troca de esquerda pela direita!
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 136
Preordem com pilha otimizada
vo id PreOrdem ( ArvBin p ) {
P i l h a p l ;
Boolean f im = f a l s e ;
I n i c i a l i z a P i l h a (& p l ) ;
do {
i f ( p!=NULL) {
V i s i t a ( p ) ;
i f ( p−>d i r !=NULL)
Empi lha ( p l , p−>d i r ) ;
p = p−>esq ;
} e l s e i f ( P i l h a V a z i a ( p l ) )
f im = t r u e
e l s e
Desempi lha ( p l ,&p ) ;
} whi le ( ! f im ) ;
} /∗ PreOrdem ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 137
Pre´-ordem com pilha embutida: Deutsch, Schorr e Waite
... ...
... ... ... ...
... ...
... ...
t p
NULL
I A varia´vel p aponta para a suba´rvore a ser percorrida.
I A varia´vel t aponta para o topo de uma pilha formada pelos no´s que
levam ao no´ p (apontadores invertidos).
I
Cada no´ devera´ conter uma marca indicando qual dos dois
apontadores esta´ invertido.
I A func¸a˜o seguinte implementa os treˆs percursos em profundidade.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 138
Pre´-ordem com pilha embutida (cont.)
vo id DSW( ArvBin p ) {
ArvBin t = NULL ; ArvBin q ; Boolean sobe ;
do {
whi le ( p!=NULL) { /∗ a` e s q u e r d a ∗/
P r e V i s i t a ( p ) ; p−>marca = MarcaEsq ; q = p−>esq ;
p−>esq = t ; t = p ; p = q ;
}
sobe = t r u e ;
whi le ( sobe && ( t !=NULL ) ) {
switch ( t−>marca ) {
case MarcaEsq : /∗ a` d i r e i t a ∗/
I n V i s i t a ( t ) ; sobe = f a l s e ; t−>marca = MarcaDir ;
q = p ; p = t−>d i r ; t−>d i r = t−>esq ; t−>esq = q ;
break ;
case MarcaDir : /∗ sobe ∗/
P o s V i s i t a ( t ) ; q = t−>d i r ; t−>d i r = p ; p = t ; t = q ;
break ;
}
}
} whi le ( t !=NULL ) ;
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 139
Desafios:
I melhorar a pre´-ordem com pilha otimizada
I inordem com pilha otimizada
I po´s-ordem com pilha otimizada
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 140
Reconstruc¸a˜o de a´rvores bina´rias
Pre´-ordem AB:
A
B
A
B
Inordem AB:
B
A
A
B
Po´s-ordem AB:
B
A
B
A
Pre´-ordem AB e po´s-ordem BA:
A
B
A
B
Conclusa˜o: uma u´nica ordem e a combinac¸a˜o de pre´- e po´s-ordens na˜o
determinam a a´rvore de maneira u´nica.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 141
Reconstruc¸a˜o de a´rvores bina´rias (cont.)
Verifica-se facilmente que a pre´-ordem (ou a po´s-ordem) combinada com a
inordem determinam, de maneira u´nica, a forma da a´rvore. No caso da
pre´-ordem e inordem, pode-se seguir o seguinte algoritmo:
I a partir da pre´-ordem, determine a raiz da a´rvore
I dada a raiz, ela separa a inordem em inordens das suas suba´rvores
esquerda e direita
I a partir da pre´-ordem, sa˜o determinadas as pre´-ordens das suba´rvores
que teˆm os mesmos comprimentos das respectivas inordens
I recursivamente sa˜o reconstru´ıdas as suba´rvores
O caso da po´s-ordem e´ ana´logo.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 142
Representac¸o˜es externas de a´rvores bina´rias
A
B
D E
G
C
F
H
I percursos canoˆnicos: inordem e pre´ (ou po´s)
-ordem (ja´ visto):
DBGEAFHC
ABDEGCFH
I percurso canoˆnico com indicadores de suba´rvores (pre´-ordem):
A11B11D00E10G00C10F01H00
O ı´ndice 0 indica a auseˆncia e 1 indica a existeˆncia de filho esquerdo
ou direito.
I descric¸a˜o parente´tica (inordem):
(((()D())B((()G())E()))A((()F (()H()))C()))
() representa uma a´rvore vazia; (αXβ) representa uma a´rvore de raiz
X e suba´rvores descritas pelas cadeias α e β.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias 143
A´rvores bina´rias de busca
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 144
Exemplo de a´rvore de busca: nu´meros
16
8
5 15
10
27
21
25
Para qualquer no´ da a´rvore, os elementos da sua suba´rvore esquerda
(direita) sa˜o menores ou iguais (maiores ou iguais) do que o elemento do
no´.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 145
Exemplo de a´rvore de busca: nomes
jul
fev
ago
abr dez
jan
set
mai
jun mar
nov
out
Para qualquer no´ da a´rvore, os elementos da sua suba´rvore esquerda
(direita) precedem (seguem) em ordem alfabe´tica o elemento do no´.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 146
Inserc¸a˜o em a´rvore de busca
A inserc¸a˜o de um valor X cria uma nova folha em lugar de uma suba´rvore
vazia. O ponto de inserc¸a˜o e´ determinado pelo percurso da a´rvore usando
a propriedade de a´rvores de busca.
Y
X < Y
Y
X
Y
X > Y
Y
X
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 147
Inserc¸a˜o recursiva
Boolean I n s e r e A r v B u s c a ( ArvBin ∗p , T x ) {
/∗ Vers a˜o r e c u r s i v a ∗/
i f ( (∗ p)==NULL) {
∗p = m a l l o c ( s i z e o f ( NoArvBin ) ) ;
(∗p)−>esq = (∗p)−>d i r = NULL ;
(∗p)−> i n f o = x ;
r e t u r n t r u e ;
} e l s e {
T i n f o = (∗p)−> i n f o ;
i f ( x< i n f o )
r e t u r n I n s e r e A r v B u s c a (&((∗p)−>esq ) , x ) ;
e l s e i f ( x> i n f o )
r e t u r n I n s e r e A r v B u s c a (&((∗p)−>d i r ) , x ) ;
e l s e
r e t u r n f a l s e ;
}
}
I Note-se o uso de passagem de paraˆmetro p por refereˆncia.
I Esta versa˜o apresenta somente recursa˜o caudal que pode ser
facilmente eliminada.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 148
Inserc¸a˜o iterativa
Boolean I n s e r e A r v B u s c a ( ArvBin ∗p , T x ) {
/∗ Vers a˜o i t e r a t i v a ∗/
T i n f o ;
whi le ( (∗ p )!=NULL) {
i n f o = (∗p)−> i n f o ;
i f ( x< i n f o )
p = &((∗p)−>esq ) ;
e l s e i f ( x> i n f o )
p = &((∗p)−>d i r ) ;
e l s e
r e t u r n f a l s e ;
}
∗p = m a l l o c ( s i z e o f ( NoArvBin ) ) ;
(∗p)−>esq = (∗p)−>d i r = NULL ;
(∗p)−> i n f o = x ;
r e t u r n t r u e ;
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 149
Remoc¸a˜o em a´rvore de busca
Caso 1: pelo menos uma das suba´rvores e´ vazia:
p
X
I p e´ o enderec¸o do campo ou da varia´vel que conte´m o apontador para
o no´ com a informac¸a˜o X.
I O caso de ambas as suba´rvores vazias tambe´m esta´ coberto.
I O caso de suba´rvore esquerda vazia mas direita na˜o vazia e´ ana´logo.
I O no´ com a informac¸a˜o X pode ser liberado.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 150
Remoc¸a˜o em a´rvore de busca (cont.)
Caso 2: as duas suba´rvores sa˜o na˜o vazias
p
X
Y
p
X
Y
Y
I Substituir a informac¸a˜o X por Y – o valor ma´ximo contido na
suba´rvore esquerda (ou m´ınimo na suba´rvore direita).
I Remover o no´ que originalmente continha Y (sua suba´rvore direita e´
vazia – aplica-se o caso 1).
I Implementac¸a˜o: exerc´ıcio.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 151
Inserc¸o˜es e remoc¸o˜es em a´rvores bina´rias de busca
I Problema: a altura da a´rvore pode crescer muito ja´ que numa a´rvore
com n no´s:
I altura ma´xima n
I altura m´ınima dlog2(n+ 1)e
I Se n ≈ 1.000:
I altura ma´xima 1.000
I altura m´ınima 10
I Se n ≈ 1.000.000:
I altura ma´xima 1.000.000
I altura m´ınima 20
I O pior caso ocorre, por exemplo, quando a inserc¸a˜o e´ feita em ordem
(crescente ou descrescente)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 152
Balanceamento de a´rvores
I Algoritmo o´bvio na˜o garante balanceamento
I Balanceamento perfeito (altura m´ınima):
I eficieˆncia de busca: O(log n)
I eficieˆncia de inserc¸a˜o: O(n) – inaceita´vel
I Balanceamento aproximado:
I a´rvores AVL – eficieˆncia de busca, inserc¸a˜o e remoc¸a˜o: O(log n)
I a´rvores rubro-negras – eficieˆncia de busca, inserc¸a˜o e remoc¸a˜o:
O(log n)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 153
A´rvores de altura balanceada (AVL)
I Autores: G. M. Adel’son-Vel’ski˘ı e E. M. Landis (1962)
I Uma a´rvore bina´ria de busca e´ do tipo AVL se ela e´ vazia, ou enta˜o,
se para todos os seus no´s a diferenc¸a de alturas entre as suba´rvores
esquerda e direita e´ no ma´ximo 1, em valor absoluto.
I A diferenc¸a entre as alturas direita e
esquerda e´ chamada fator de
balanceamento.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 154
Exemplos de a´rvores AVL
0
0 0
−
− +
+ 0 0
0
Note-se que a primeira a´rvore e´ de altura m´ınima enquanto que a segunda
na˜o e´.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 155
Pior caso de desbalanceamento: a´rvores de Fibonacci
F0
NULL
F1
0
F2
−
0
F3
−
− 0
−
F4
−
− −
− 0 0
0
Forma geral – altura h≥2:
Fh
−
Fh−1 Fh−2
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 156
A´rvores de Fibonacci: propriedades −
Fh−1 Fh−2
I Para uma dada altura h, a a´rvore conte´m o nu´mero m´ınimo de no´s
poss´ıvel preservando ainda a propriedade AVL.
I Qualquer outra a´rvore AVL com o mesmo nu´mero de no´s tem altura
menor ou igual – este e´ o pior caso.
I Nu´mero de no´s de Fh: N(h) = N(h− 1) +N(h− 2) + 1, h ≥ 2
I Demonstra-se por induc¸a˜o: N(h) = fh+2 − 1, onde fi e´ o i-e´simo
nu´mero de Fibonacci.
I Usando a aproximac¸a˜o fi ≈ ((1 +
√
(5))/2)i/
√
(5) obte´m-se:
h ≈ 1, 44 log2(n+ 2) (no ma´ximo).
I Operac¸a˜o de busca usara´ O(log n) operac¸o˜es.
I A ser visto: inserc¸a˜o e remoc¸a˜o tambe´m usara˜o O(log n) operac¸o˜es.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 157
Inserc¸a˜o em a´rvores AVL
A explicac¸a˜o a seguir supo˜e que a inserc¸a˜o e´ realizada por uma func¸a˜o
recursiva cujo cabec¸alho e´:
Boolean B u s c a I n s e r e ( ArvAVL ∗p , T x , Boolean ∗ a l t ) ;
onde
I p: enderec¸o da varia´vel que conte´m o apontador para a a´rvore
I x: valor a ser inserido de algum tipo T conveniente
I alt: enderec¸o da varia´vel na qual e´ devolvida a informac¸a˜o que indica
se a a´rvore aumentou ou na˜o de altura
I se na˜o houver aumento de altura numa chamada recursiva, o resto da
a´rvore na˜o sofre mudanc¸a
I conforme sera´ visto, o aumento da altura sera´ no ma´ximo de um e
pode acontecer somente numa a´rvore vazia ou enta˜o cuja raiz tem
fator de balanceamento igual a zero; neste caso, o fator resultante
sera´ diferente de zero, exceto quando a a´rvore era vazia.
O valor devolvido pela func¸a˜o indica se a inserc¸a˜o foi efetivamente
realizada ou se o elemento x ja´ pertencia a` arvore.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 158
Inserc¸a˜o em a´rvores AVL (cont.)
Explicac¸a˜o geral: caso de chamada recursiva sem aumento de altura
p
h
x α alt: ? p
h
x ? alt: false
α
Neste caso, na˜o havera´ mais modificac¸o˜es na a´rvore.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 159
Inserc¸a˜o em a´rvores AVL (cont.)
Explicac¸a˜o geral: caso de chamada recursiva com aumento de altura
p
h
x α alt: ? p
h+1
x ? alt: true
α
Neste caso, havera´ modificac¸a˜o no no´ corrente com poss´ıvel propagac¸a˜o
para as chamadas anteriores.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 160
Inserc¸a˜o em a´rvores AVL (cont.)
Caso 1: Inserc¸a˜o em a´rvore vazia:
NULL
h = 0
X
0
h = 1
Neste caso a altura h aumenta. Este fato sera´ propagado no retorno da
func¸a˜o atrave´s de valor verdadeiro da varia´vel alt.
Nos casos seguintes, sera´ suposto sempre que a inserc¸a˜o foi realizada na
suba´rvore esquerda; o caso da inserc¸a˜o do lado direito e´ ana´logo.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 161
Inserc¸a˜o em a´rvores AVL (cont.)
Caso 2: Inserc¸a˜o do lado mais baixo:
+
h
+
x
h
alt: true
0
x
h
alt: false
O conteu´do do retaˆngulo representa o resultado da chamada recursiva. O
fator de balanceamento sera´ modificado somente se a a´rvore esquerda
aumentou de tamanho.
Neste caso a altura permanece inalterada. Este fato sera´ propagado no
retorno da func¸a˜o atrave´s de valor falso da varia´vel alt. Como
consequeˆncia, o processo de inserc¸a˜o pa´ra (exceto os retornos).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 162
Inserc¸a˜o em a´rvores AVL (cont.)
Caso 3: Inserc¸a˜o quando as duas alturas sa˜o iguais
0
h
0
x
h+1
alt: true
−
x
h+1
alt: true
Neste caso, se houve aumento de altura na chamada recursiva, a altura
total tambe´m aumentara´. Este fato sera´ propagado no retorno da func¸a˜o
atrave´s de valor verdadeiro da varia´vel alt.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 163
Inserc¸a˜o em a´rvores AVL (cont.)
Caso 4: Inserc¸a˜o do lado mais alto
−
h
−
x
h-1 h+1
alt: true
Neste caso, se houve aumento de altura na chamada recursiva, a a´rvore
deixara´ de ser do tipo AVL. Havera´ enta˜o dois subcasos, dependendo do
lado da suba´rvore esquerda em que houve inserc¸a˜o. A identificac¸a˜o do
subcaso sera´ feita pelo valor do fator de balanceamento final da suba´rvore
que aumentou de altura durante a chamada recursiva.
Nos dois casos havera´ rearranjos convenientes mas locais da a´rvore.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 164
Inserc¸a˜o em a´rvores AVL (cont.)
Caso 4a: inserc¸a˜o do lado esquerdo da suba´rvore (rotac¸a˜o LL)
−
x
h-1 h+1
alt: true
−
−
A
B
x
h-2
h-1 h-2T1 T2
T3
0
0
B
A
x h-2
h-1
h-2
T1
T2 T3
0
B
x
h
alt: false
Neste caso e´ realizada uma transformac¸a˜o denominada rotac¸a˜o simples LL
(esquerda, esquerda). A altura final permanece inalterada e a varia´vel alt
recebe valor falso.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 165
Inserc¸a˜o em a´rvores AVL (cont.)
Caso 4b: inserc¸a˜o do lado direito da suba´rvore (rotac¸a˜o LR)
−
x
h-1 h+1
alt: true
−
+
+0−
A
B
C
x x
T1
T2 T3
T4
h-2
h-2
h-2/h-3
AB
C
0
−/0 0/+
h-2/h-3
T1
T2 T3
T4x x
h-2 h-2
0
C
x
h
alt: false
Neste caso, a inserc¸a˜o pode ter sido realizada na suba´rvore esquerda ou
direita do lado que cresceu, ou enta˜o no pro´prio no´ C quando h = 2. Os
fatores de balanceamento finais dependem disto, mas o da raiz sera´ 0. A
transformac¸a˜o e´ denominada rotac¸a˜o dupla LR (esquerda, direita). A
altura final permanece inalterada e a varia´vel alt recebe valor falso.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 166
Func¸a˜o de inserc¸a˜o em a´rvores AVL
Boolean B u s c a I n s e r e ( ArvAVL ∗p , T x , Boolean ∗ a l t ) {
/∗ Devo lve ’ t r u e ’ ou ’ f a l s e ’ conforme houve ou na˜o i n s e r c¸ a˜ o ;
s e houve i n s e r c¸ a˜ o , ’ a l t ’ i n d i c a s e houve aumento da a l t u r a .
∗/
i f (∗p==NULL) {
∗p = m a l l o c ( s i z e o f ( NoArvAVL ) ) ;
(∗p)−>esq = (∗p)−>d i r = NULL ; (∗p)−> i n f o = x ;
(∗p)−>b a l = z e r o ; ∗ a l t = t r u e ;
r e t u r n t r u e ;
} e l s e {
T i n f o = (∗p)−> i n f o ;
i f ( x==i n f o )
r e t u r n f a l s e ;
e l s e i f ( x< i n f o ) { /∗ d e s c e a` e s q u e r d a ∗/
Boolean r e s = B u s c a I n s e r e (&((∗p)−>esq ) , x , a l t ) ;
i f ( ! r e s )
r e t u r n f a l s e ;
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 167
Func¸a˜o de inserc¸a˜o em a´rvores AVL (cont.)
i f (∗ a l t ) { /∗ aumento de a l t u r a ∗/
ArvAVL p1 , p2 ;
switch ( (∗ p)−>b a l ) {
case mais : (∗p)−>b a l = z e r o ; ∗ a l t = f a l s e ; break ;
case z e r o : (∗p)−>b a l = menos ; break ;
case menos :
p1 = (∗p)−>esq ;
i f ( p1−>b a l==menos ) {
/∗ Rotac¸ a˜o s i m p l e s LL ∗/
} e l s e {
/∗ Rotac¸ a˜o d u p l a LR ∗/
}
p1−>b a l = z e r o ; ∗ a l t = f a l s e ;
break ;
}
}
r e t u r n t r u e ;
} e l s e {
/∗ d e s c e a` d i r e i t a − a n a´ l o g o ∗/
}
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 168
Exemplos de inserc¸a˜o em a´rvores AVL
Inserc¸a˜o de 33:
50
25 65
20 35 55
6010 30 45
70
4033
−
+
− +
0 0
0
−
+
0−
0
50
25 65
20 35 55
6010 30 45
70
4033
−
+
− +
0 +
00
−
0
0−
0
Neste caso, houve uma inserc¸a˜o simples e a mudanc¸a de fatores de
balanceamento afetou os no´s marcados.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 169
Exemplos de inserc¸a˜o em a´rvores AVL (cont.)
Inserc¸a˜o de 63:
50
25 65
20 35 55
6010 30 45
70
40 63
−
+
− +
0 0
0
−
+
0−
0
50
25 65
20 35 60
6310 30 45
70
40
55
−
+
− 0
0 0
0
0
−
+
0−
0
Neste caso, a inserc¸a˜o causou uma rotac¸a˜o simples do tipo RR, afetando
os no´s marcados.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 170
Exemplos de inserc¸a˜o em a´rvores AVL (cont.)
Inserc¸a˜o de 41:
50
25 65
20 35 55
6010 30 45
70
40
41
−
+
− +
0 0
0
−
+
0−
0
50
25 65
20 35 55
6010 30 41
70
40 45
−
+
− +
0 0
0
−
+
00
0
0
Neste caso, a inserc¸a˜o causou uma rotac¸a˜o dupla do tipo LR, afetando os
no´s marcados.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 171
Remoc¸a˜o em a´rvores AVL
1. Transformac¸a˜o em remoc¸a˜o de uma folha - treˆs casos:
I o no´ tem grau zero: ja´ e´ uma folha
I o no´ tem grau um: pela propriedade AVL, a sua u´nica suba´rvore e´
necessariamente constitu´ıda por uma folha, cujo valor e´ copiado para o
no´ pai; o no´ a ser eliminado e´ a folha da suba´rvore
I o no´ tem grau dois: o seu valor e´ substit´ıdo pelo maior valor contido na
sua suba´rvore esquerda (ou o menor valor contido na sua suba´rvore
direita); o no´ que continha o menor (ou maior) valor copiado tem
necessariamente grau zero ou um, recaindo num dos casos anteriores.
2. Remoc¸a˜o propriamente dita.
3. O algoritmo de remoc¸a˜o sera´ apresentado novamente como uma
func¸a˜o recursiva que indica se houve diminuic¸a˜o da altura da a´rvore
apo´s a remoc¸a˜o. Sera˜o estudados apenas os casos de remoc¸a˜o do
lado esquerdo; os outros sa˜o ana´logos.
4. A implementac¸a˜o do algoritmo e´ um exerc´ıcio.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 172
Remoc¸a˜o em a´rvores AVL (cont.)
Caso 1: Remoc¸a˜o de uma folha
X
0
h = 1
NULL
h = 0
Neste caso a altura h diminui. Este fato sera´ propagado no retorno da
func¸a˜o atrave´s de valor verdadeiro da varia´vel alt.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 173
Remoc¸a˜o em a´rvores AVL (cont.)
Caso 2: Remoc¸a˜o quando as duas alturas sa˜o iguais
0
x
h
0
h
alt: true
+
h
alt: false
O conteu´do do retaˆngulo representa o resultado da chamada recursiva. O
fator de balanceamento sera´ modificado somente se a a´rvore esquerda
diminuiu de tamanho.
Neste caso, mesmo que haja diminuic¸a˜o de altura na chamada recursiva, a
altura total permanece a mesma. Este fato sera´ propagado no retorno da
func¸a˜o atrave´s de valor falso da varia´vel alt.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 174
Remoc¸a˜o em a´rvores AVL (cont.)
Caso 3: Remoc¸a˜o do lado mais alto
−
x
h
−
alt: true
h-1
0
alt: true
h-1
Neste caso, se a chamada recursiva indica diminuic¸a˜o da altura da
suba´rvore, a altura final da a´rvore tambe´m diminui e o processo continua.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 175
Remoc¸a˜o em a´rvores AVL (cont.)
Caso 4: Remoc¸a˜o do lado mais baixo
+
x
h
+
alt: true
h h-2
Caso a suba´rvore esquerda tenha sua altura diminu´ıda, a a´rvore deixa de
ser do tipo AVL. Ha´ treˆs subcasos, dependendo do fator de balanceamento
do filho direito da raiz.
Note-se que, neste caso, tem-se h ≥ 3.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 176
Remoc¸a˜o em a´rvores AVL (cont.)
Caso 4a: Fator de balanceamento 0 (rotac¸a˜o RR)
+
alt: true
h h-2
+
0
A
B
h-2
h-3
h-2
T1
T2 T3
−
+
B
A
h-2
h-3
h-2
T1
T2
T3
−
B
h
alt: false
Neste caso e´ realizada uma transformac¸a˜o denominada rotac¸a˜o simples RR
(direita, direita). A altura final permanece inalterada e a varia´vel alt
recebe valor falso. O processo de ajuste da a´rvore pa´ra.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 177
Remoc¸a˜o em a´rvores AVL (cont.)
Caso 4b: Fator de balanceamento +1 (rotac¸a˜o RR)
+
alt: true
h h-2
+
+
A
B
h-2
h-3
h-3
T1
T2
T3
0
0
B
A
h-2
h-3 h-3
T1 T2
T3
h-1
0
B
h-1
alt: true
Neste caso tambe´m e´ realizada a transformac¸a˜o denominada
rotac¸a˜o simples RR (direita, direita). A altura final diminui e a varia´vel alt
recebe o valor verdadeiro. O processo de ajuste da a´rvore continua.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 178
Remoc¸a˜o em a´rvores AVL (cont.)
Caso 4c: Fator de balanceamento -1 (rotac¸a˜o RL)
+
alt: true
h h-2
+
−
+0−
A
B
CT1
T2 T3
T4
h-3
h-3
h-3/h-4
C
A B
0
−/0 0/+
h-3/h-4
T1
T2 T3
T4
h-3 h-3
0
C
h-1
alt: true
Neste caso tambe´m e´ realizada uma transformac¸a˜o denominada
rotac¸a˜o dupla RL (direita, esquerda). A altura final diminui e a varia´vel
alt recebe o valor verdadeiro. O processo de ajuste da a´rvore continua.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 179
Exemplos de remoc¸a˜o em a´rvores AVL
Remoc¸a˜o de 40:
50
25 65
20 35 55
6010 30 45
70
40
−
+
− +
0 0
0
−
+
0−
0
50
25 65
20 35 55
6010 30 45
70
0
0
− +
0 0
−
0
00
0
Neste caso, houve uma remoc¸a˜o simples e a mudanc¸a de fatores de
balanceamento afetou os no´s marcados.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 180
Exemplos de remoc¸a˜o em a´rvores AVL (cont.)
Remoc¸a˜o de 60:
50
25 65
20 35 55
6010 30 45
70
40
−
+
− +
0 0
0
−
+
0−
0
35
25 50
20 30 45 65
10 40 55 70
0
−
− −
0 0 0
+
0 0
0
Neste caso, a remoc¸a˜o causou, apo´s a volta da chamada com a raiz
original, uma rotac¸a˜o dupla do tipo LR, afetando os no´s marcados.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores bina´rias de busca 181
A´rvores do tipo B
(B trees)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 182
Discos magne´ticos
Esboc¸o esquema´tico do corte vertical de uma unidade com quatro discos
(oito superf´ıcies):
0
1
2
3
4
5
6
7
cabec¸as leitoras/gravadoras
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 183
Discos magne´ticos (cont.)
Esboc¸o esquema´tico de uma superf´ıcie de um disco:
...
uma trilha
um cilindro
(trilhas iguais)
setores
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 184
Discos magne´ticos (cont.)
Dados para um disco fict´ıcio de 40 gigabytes:
I 10 cabec¸as leitoras/gravadoras
I 20.000 trilhas (2.000 por superf´ıcie)
I 400 setores por trilha
I 512 bytes por setor (unidade m´ınima de enderec¸amento)
I tempo me´dio de busca da trilha enderec¸ada (seek): ∆S
(10 milissegundos)
I tempo me´dio de lateˆncia – espera pelo setor enderec¸ado: ∆L
(10 milissegundos)
I tempo de transfereˆncia de dados: ∆T (60 megabytes/segundo)
I Estes tempos sa˜o va´rias ordens de grandeza maiores do que tempo de
acesso a` memo´ria RAM (tipicamente 100.000 vezes).
I Nu´mero de acessos: altura da a´rvore – log2 n na˜o e´ mais aceita´vel
I Soluc¸a˜o: logk n, com k >> 2
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 185
A´rvores B
I Autores: Rudolf Bayer e Ed McCreight (1971)
I T e´ uma a´rvore B de ordem b≥2 se:
1. todas as folhas de T teˆm o mesmo n´ıvel;
2. cada no´ interno tem um nu´mero varia´vel r de registros de informac¸a˜o e
r+1 de filhos, onde bb/2c ≤ r ≤ b se no´ 6= raiz
1 ≤ r ≤ b se no´ = raiz
3. cada folha tem um nu´mero varia´vel r de registros obedecendo a` mesma
restric¸a˜o do item anterior;
4. os campos de informac¸a˜o contidos nos registros obedecem a`
propriedade de a´rvores de busca.
I Alguns autores definem de maneira diferente o conceito de ordem.
I Pode-se provar que a altura ma´xima h de uma a´rvore B de ordem b
que conte´m n registros e´ dada por:
logbb/2c(n+ 1)/2.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 186
Exemplo de a´rvore B de ordem 3
Neste caso, cada no´ tem no m´ınimo um e no ma´ximo treˆs registros de
informac¸a˜o.
3 5 20 35 48 51 80 85 150 205
17 50 83 203
125
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 187
Exemplo de a´rvore B de ordem 5
Neste caso, cada no´ tem no m´ınimo dois e no ma´ximo cinco registros de
informac¸a˜o.
1 2 3 5 10 12 13 20 21 25 30 32 45 46 55 56 57 61 62 63 71 72 75 76 80
7 15 40 60 70
50
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 188
Nu´meros m´ınimos e ma´ximos de registros
A´rvore B de ordem 255:
m´ınimo ma´ximo
n´ıvel no´s registros no´s registros
1 1 1 1 1 × 255
2 2 2 × 127 2561 2561 × 255
3 2 × 1281 2 × 1281 × 127 2562 2562 × 255
4 2 × 1282 2 × 1282 × 127 2563 2563 × 255
5 2 × 1283 2 × 1283 × 127 2564 2564 × 255
Total 4.227.331 536.870.911 4.311.810.305 1.099.511.627.775
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 189
Exemplos de inserc¸a˜o
Inserc¸a˜o de 81:
3 5 20 35 48 51 80 85 150 205
17 50 83 203
125
3 5 20 35 48 51 80 81 85 150 205
17 50 83 203
125
Neste caso, foi feita inserc¸a˜o numa folha com espac¸o dispon´ıvel. Houve h
leituras e uma gravac¸a˜o (h e´ a altura da a´rvore). O processo na˜o se
propaga.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 190
Exemplos de inserc¸a˜o (cont.)
Inserc¸a˜o de 33:
3 5 20 35 48 51 80 85 150 205
17 50 83 203
125
3 5 20 33 48 51 80 85 150 205
17 35 83 203
50 125
A capacidade de uma folha seria excedida e foi feita uma quebra que
propagou-se para cima. Haveria no ma´ximo h leituras e 2h+1 gravac¸o˜es
(se a raiz tambe´m fosse quebrada).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 191
Representac¸a˜o de a´rvores B
#d e f i n e ORDEM 255
typedef s t r u c t NoArvB ∗ ArvB ;
typedef s t r u c t NoArvB {
i n t numregs ;
ArvB f i l h o s [ORDEM+1];
T i n f o [ORDEM] ;
} NoArvBin ;
Esta representac¸a˜o sera´ usada para simular a´rvores B na memo´ria RAM.
Normalmente, a´rvores B sa˜o implementadas em memo´rias externas como
discos. O enderec¸amento em discos e´ usado em lugar de apontadores
comuns.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 192
Inserc¸a˜o em a´rvores B
A explicac¸a˜o a seguir supo˜e que a inserc¸a˜o e´ realizada por uma func¸a˜o
recursiva auxiliar cujo cabec¸alho e´:
Boolean I n s e r e R e c A r v B ( ArvB ∗p , ArvB ∗ s , T ∗x , Boolean ∗ prop ) ;
onde
I p: enderec¸o da varia´vel que conte´m o apontador para a a´rvore
I prop: enderec¸o da varia´vel na qual e´ devolvida a informac¸a˜o que
indica se houve propagac¸a˜o de inserc¸a˜o no retorno
I x: enderec¸o de uma varia´vel
I numa chamada: conte´m o valor a ser inserido de algum tipo T
conveniente
I no retorno, se houver propagac¸a˜o: conte´m o valor a ser propagado que
separa os valores das a´rvores apontadas por p e por s
I s: enderec¸o da varia´vel que conte´m o apontador para a a´rvore
propagada (se houver)
I se na˜o houver propagac¸a˜o numa chamada recursiva, o resto da a´rvore
na˜o sofre mudanc¸a
O valor devolvido pela func¸a˜o indica se a inserc¸a˜o foi efetivamente
realizada ou se o elemento x ja´ pertencia a` arvore.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 193
Inserc¸a˜o em a´rvores B (cont.)
Explicac¸a˜o geral: caso de chamada recursiva sem propagac¸a˜o no retorno
p x s prop: ?α ?
p x s prop: false? ?
α
Neste caso, na˜o havera´ mais modificac¸o˜es na a´rvore.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 194
Inserc¸a˜o em a´rvores B (cont.)
Explicac¸a˜o geral: caso de chamada recursiva com propagac¸a˜o no retorno
p x s prop: ?α ?
p x s
< >
prop: trueβ
α α
Neste caso, a modificac¸a˜o devera´ ser propagada para cima. O valor α da
varia´vel x foi inserido numa das duas a´rvores (ou e´ o β). Se p apontava
para a raiz da a´rvore, sera´ necessa´rio criar uma nova raiz, com um u´nico
valor β, e suba´rvores apontadas por p e s.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 195
Inserc¸a˜o em a´rvores B (cont.)
Caso 1: a´rvore vazia
p x s prop: ?α ?
p x s prop: trueα
Neste caso, sa˜o adotados valores das varia´veis x, s e prop de maneira a
recair no caso geral de propagac¸a˜o.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 196
Inserc¸a˜o em a´rvores B (cont.)
Caso 2: inserc¸a˜o com espac¸o dispon´ıvel (r<b)
p
0 i−1 i r−1 b−1
... ...xi−1 xi
Ti
x s ? prop: ?α
(inserc¸a˜o recursiva em Ti)
p
0 i−1 i r−1 b−1
... ...xi−1 xi x s prop: trueβ
p
0 i−1 i r b−1
... ...xi−1 xi x s ? prop: false?β
Neste caso, o valor propagado apo´s a chamada recursiva e´ absorvido no no´
corrente e a propagac¸a˜o pa´ra.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 197
Inserc¸a˜o em a´rvores B (cont.)
Caso 3: inserc¸a˜o sem espac¸o dispon´ıvel (r=b)
p
0 i−1 i b−1
... ...xi−1 xi
Ti
xb−1 x s ? prop: ?α
(inserc¸a˜o recursiva em Ti)
p
0 i−1 i b−1
... ...xi−1 xi xb−1 x s prop: trueβ
p
0 i−1 i b−1
... ...xi−1 xi xb−1 x s ? prop: ??β
b
Neste caso, o valor propagado apo´s a chamada recursiva na˜o pode ser
absorvido pois o no´ teria que ser aumentado ale´m da capacidade ma´xima;
continua com quebra do no´ (o espac¸o extra e´ apenas conceitual).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 198
Inserc¸a˜o em a´rvores B (cont.)
Caso 3: inserc¸a˜o sem espac¸o dispon´ıvel – quebra do no´
p
0 i−1 i b−1
... ...xi−1 xi xb−1 x s ? prop: ??β
b
(equivalente)
p
0 k b−1
... ...yk yb x s ? prop: ??
Tk Tk+1 Tb+1
b
p
0 k b−1
yk−1
Tk
x s
prop: true
yk
0 b−k b−1
Tk+1 Tb+1
yk+1
O no´ corrente e´ quebrado em dois; o primeiro (no´ original apontado
por p)
rete´m k = db/2e+1 primeiros registros; o k-e´simo elemento e um novo no´
com b−k registros restantes sa˜o propagados de volta.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 199
Func¸a˜o de inserc¸a˜o auxiliar (esboc¸o)
Boolean I n s e r e R e c A r v B ( ArvB ∗p , ArvB ∗ s , T ∗x , Boolean ∗ prop ) {
i n t i ; Boolean i n s e r i u ;
i f ( p==NULL) {
∗ prop = t r u e ; ∗ s = NULL ; r e t u r n t r u e ;
}
i = I n d i c e A r v B ( p , x ) ; // l o c a l i z a o ponto de i n s e r c¸ a˜ o
i f ( ( i <((∗p)−>numregs ) ) && ( x==((∗p)−> i n f o ) [ i ] ) ) {
∗ prop = f a l s e ; r e t u r n f a l s e ;
}
i n s e r i u = I n s e r e R e c A r v B (&((∗p)−> f i l h o s [ i ] ) , s , x , prop ) ;
i f (∗ prop ) {
I n s e r e I n f o A r v B ( p , s , x , i ) } ; // i n s e r e ’ s ’ e ’ x ’ no no´
( (∗ p)−>numregs )++;
i f ( ( (∗ p)−>numregs<=ORDEM) )
∗ prop = f a l s e ;
e l s e {
QuebraNoArvB ( p , s , x ) ; ∗ prop = t r u e ; // quebra
}
}
r e t u r n i n s e r i u ;
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 200
Func¸a˜o de inserc¸a˜o inicial
Boolean I n s e r e A r v B ( ArvB ∗p , T ∗x ) {
/∗ Devo lve ’ f a l s e ’ s e o v a l o r de ’ x ’ j a´ o c o r r e na a´ r v o r e ’ p ’ ∗/
Boolean prop ;
ArvB q , s ;
Boolean i n s e r i u = I n s e r e R e c A r v B ( p,& s , x ,& prop ) ;
i f ( prop ) {
q = ( ArvB ) m a l l o c ( s i z e o f ( NoArvB ) ) ;
q−>numregs = 1 ;
( q−> f i l h o s ) [ 0 ] = ∗p ; ( q−> f i l h o s ) [ 1 ] = s ;
( q−> i n f o ) [ 0 ] = ∗x ;
∗p = q ;
}
r e t u r n i n s e r i u ;
}
O eventual aumento da altura da a´rvore se dara´ sempre nesta func¸a˜o.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 201
Exemplos de remoc¸a˜o
Remoc¸a˜o de 51:
3 5 20 35 48 51 80 85 150 205
17 50 83 203
125
3 5 20 35 48 80 85 150 205
17 50 83 203
125
Neste caso, foi feita remoc¸a˜o numa folha com nu´mero de registros acima
do m´ınimo. Houve h leituras e uma gravac¸a˜o (h e´ a altura da a´rvore). O
processo na˜o se propaga.
Em todos os casos, a remoc¸a˜o devera´ iniciar-se numa folha. Se necessa´rio,
um elemento de um no´ interno devera´ ser substitu´ıdo convenientemente.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 202
Exemplos de remoc¸a˜o (cont.)
Remoc¸a˜o de 85:
3 5 20 35 48 51 80 85 150 205
17 50 83 203
125
3 5 20 35 48 51 83 150 205
17 50 80 203
125
Neste caso, foi feita remoc¸a˜o numa folha com nu´mero m´ınimo de
registros, e foi feito um “empre´stimo” de um no´ irma˜o imediato com sobra
de registros. O empre´stimo passa pelo no´ pai a fim de manter a
propriedade de a´rvore de busca. Haveria no ma´ximo h+ 2 leituras e treˆs
gravac¸o˜es. O processo na˜o se propaga.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 203
Exemplos de remoc¸a˜o (cont.)
Remoc¸a˜o de 150:
3 5 20 35 48 51 80 85 150 205
17 50 83 203
125
3 5 20 35 48 51 80 85 203 205
17 50 125
83
Neste caso, foi feita remoc¸a˜o numa folha com nu´mero m´ınimo de registros
e cujos irma˜os tambe´m esta˜o no m´ınimo. Foi feita enta˜o uma junc¸a˜o de
dois no´s e inclu´ıdo o valor do no´ pai que os separa. A remoc¸a˜o deste valor
do no´ pai seguira´ o mesmo esquema de remoc¸o˜es, e podera´ se propagar
ate´ a raiz. Haveria no ma´ximo 3h− 2 leituras e 2h− 1 gravac¸o˜es.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 204
Observac¸o˜es
I Verifica-se facilmente que tanto no caso de quebras (inserc¸a˜o) como
no caso de junc¸o˜es (remoc¸a˜o), os no´s resultantes preservam as
propriedades de a´rvores B.
I O nu´mero de leituras e gravac¸o˜es e´ sempre proporcional a` altura da
a´rvore.
I O no´ raiz da a´rvore e´ normalmente guardado na memo´ria, diminuindo
o nu´mero de acessos ao disco.
I De acordo com a definic¸a˜o das a´rvores B, a utlizac¸a˜o m´ınima do
espac¸o dos no´s e´ de cerca de 50%; pode-se provar que a utilizac¸a˜o
me´dia e´ de cerca de 69%.
I Usando te´cnicas probabil´ısticas, pode-se mostrar que as operac¸o˜es
mais complicadas sa˜o muito infrequentes.
I A remoc¸a˜o pode ser implementada de maneira ana´loga a` inserc¸a˜o e
sera´ deixada para exerc´ıcio.
I Uma a´rvore B inicial pode ser constru´ıda por inserc¸o˜es sucessivas o
que seria muito ineficiente; na pra´tica, utiliza-se um algoritmo direto.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 205
Variantes de a´rvores B
I A´rvores B∗: o nu´mero de registros ocupados de um no´ e´ no m´ınimo 23
da sua capacidade.
I A´rvores B+:
I no´s internos com chaves apenas para orientar o percurso
I pares (chave, valor) apenas nas folhas
I regra de descida:
I suba´rvore esquerda: menor
I suba´rvore direita: maior ou igual
I apontadores em lugar de valores tornando mais eficiente a
movimentac¸a˜o dos registros durante inserc¸o˜es e remoc¸o˜es
I ligac¸o˜es facilitando percurso em ordem de chaves
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 206
Variantes de a´rvores B (cont.)
Exemplo de a´rvore B+ de ordem 3:
4 6 8 11 12 14 15 18 20 23 25 26 29 35
11 15 26
23
Setas tracejadas indicam apontadores para os valores da informac¸a˜o. A
lista ligada das folhas permite percurso simples e eficiente em ordem de
chaves.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores do tipo B 207
Filas de prioridade
(Priority queues)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Filas de prioridade 208
Definic¸a˜o e propriedades
I Uma fila de prioridade e´ uma a´rvore bina´ria com as propriedades:
I a a´rvore e´ completa ou quase completa;
I em cada no´ da a´rvore, o valor da chave e´ maior ou igual aos valores
das chaves dos filhos (e consequentemente, de todos os descendentes).
I Uma fila de prioridade na˜o e´ uma a´rvore de busca!
I A determinac¸a˜o do elemento ma´ximo de uma fila de prioridade pode
ser feita em tempo constante (esta´ na raiz).
I As operac¸o˜es de inserc¸a˜o e de remoc¸a˜o podem ser realizadas em
tempo proporcional a` altura (O(log n)).
I Filas de prioridade podem ser implementadas eficientemente de
maneira sequencial.
I Em algumas aplicac¸o˜es e´ conveniente utilizar filas de prioridade em
que um elemento e´ menor ou igual a todos os seus descendentes.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Filas de prioridade 209
Exemplo
0
95
1
88
2
75
3
30
4
45
5
40
6
38
7
15
8
10
9
23
Implementac¸a˜o sequencial (heap):
95
0
88
1
75
2
30
3
45
4
40
5
38
6
15
7
10
8
23
9
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Filas de prioridade 210
Operac¸a˜o de subida
Supondo que, exceto pelo u´ltimo elemento, a a´rvore e´ uma fila de
prioridade, a operac¸a˜o torna a a´rvore inteira uma fila va´lida.
0
95
1
88
2
75
3
30
4
45
5
40
6
38
7
15
8
10
9
23
10
90
0
95
1
90
2
75
3
30
4
88
5
40
6
38
7
15
8
10
9
23
10
45
Setas duplas indicam as operac¸o˜es de troca a serem realizadas.
Obviamente, o nu´mero de operac¸o˜es de troca executadas e´, no ma´ximo,
igual a` altura da a´rvore original (log2 n).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Filas de prioridade 211
Operac¸a˜o de descida
Supondo que, exceto por um u´nico valor que na˜o e´ maior ou igual do que
seus descendentes, a a´rvore e´ uma fila de prioridade, a operac¸a˜o torna a
a´rvore inteira uma fila va´lida.
0
95
1
13
2
75
3
30
4
88
5
40
6
38
7
15
8
10
9
23
0
95
1
88
2
75
3
30
4
23
5
40
6
38
7
15
8
10
9
13
Setas duplas indicam as operac¸o˜es de troca a serem realizadas.
Obviamente, o nu´mero de operac¸o˜es de troca executadas e´ menor do que
a altura da a´rvore original (log2 n).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Filas de prioridade 212
Implementac¸a˜o das operac¸o˜es
#d e f i n e TAM MAX 50
typedef s t r u c t {
T v e t o r [TAM MAX ] ;
i n t tam ;
} Heap ;
vo id Sobe ( Heap ∗h , i n t m) {
i n t j = (m−1)/2;
T x = (∗h ) . v e t o r [m] ;
whi le ( (m>0) && ( (∗ h ) . v e t o r [ j ]<x ) ) {
(∗h ) . v e t o r [m] = (∗h ) . v e t o r [ j ] ;
m = j ;
j = ( j −1)/2;
}
(∗h ) . v e t o r [m] = x ;
} /∗ Sobe ∗/
Note-se que as operac¸o˜es de troca foram otimizadas com a utilizac¸a˜o da
varia´vel tempora´ria x.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Filas de prioridade 213
Implementac¸a˜o das operac¸o˜es (cont.)
vo id Desce ( Heap ∗h , i n t m) {
i n t k = 2∗m+1;
T x = (∗h ) . v e t o r [m] ;
whi le ( k<(∗h ) . tam ) {
i f ( ( k<((∗h ) . tam)−1) && ( (∗ h ) . v e t o r [ k ]<(∗h ) . v e t o r [ k +1]))
k++;
i f ( x<(∗h ) . v e t o r [ k ] ) {
(∗h ) . v e t o r [m] = (∗h ) . v e t o r [ k ] ;
m = k ;
k = 2∗k+1;
} e l s e
break ;
}
(∗h ) . v e t o r [m] = x ;
} /∗ Desce ∗/
Tambe´m neste caso, as operac¸o˜es de troca foram otimizadas.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Filas de prioridade 214
Construc¸a˜o inicial
Dado um vetor com elementos em ordem arbitra´ria, deve-se transforma´-lo
numa fila de prioridade:
vo id C on s t r o iH e a p1 ( Heap ∗h ) {
i n t i ;
f o r ( i =1; i <(∗h ) . tam ; i ++)
Sobe ( h , i ) ;
} /∗ C on s t r o iH e a p1 ∗/
vo id C on s t r o iH e a p2 ( Heap ∗h ) {
i n t i ;
f o r ( i =((∗h ) . tam−2)/2; i >=0; i−−)
Desce ( h , i ) ;
} /∗ C on s t r o iH e a p2 ∗/
Verifica-se facilmente que a eficieˆncia da func¸a˜o ConstroiHeap1 e´
O(n log n). Pode-se demonstrar, tambe´m, que a eficieˆncia de
ConstroiHeap2 e´ O(n) (linear).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Filas de prioridade 215
Inserc¸a˜o e remoc¸a˜o
vo id I n s e r e H e a p ( Heap ∗h , T x ) {
v e t o r [ ( ∗ h ) . tam ] = x ;
( (∗ h ) . tam)++;
Sobe ( h , ( ( ∗ h ) . tam )−1);
} /∗ I n s e r e H e a p ∗/
vo id RemoveHeap ( Heap ∗h , T ∗x ) {
∗x = (∗h ) . v e t o r [ 0 ] ;
( (∗ h ) . tam)−−;
(∗h ) . v e t o r [ 0 ] =
(∗h ) . v e t o r [ ( ∗ h ) . tam ] ;
Desce ( h , 0 ) ;
} /∗ RemoveHeap ∗/
Note-se que a func¸a˜o RemoveHeap remove e devolve na varia´vel x o
elemento ma´ximo da fila. Obviamente, as duas func¸o˜es realizam no
ma´ximo O(n log n) operac¸o˜es.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Filas de prioridade 216
Algoritmo de ordenac¸a˜o Heapsort
O algoritmo constro´i um heap inicial. Em seguida, remove um a um o
elemento ma´ximo e o coloca na posic¸a˜o final do vetor.
vo id HeapSort ( Heap ∗h ) {
i n t i , n = (∗h ) . tam ;
/∗ c o n s t r o´ i heap ∗/
f o r ( i =(n−2)/2; i >=0; i−−)
Desce ( h , i ) ;
/∗ ordena ∗/
f o r ( i=n−1; i >0; i−−) {
T t = (∗h ) . v e t o r [ 0 ] ;
(∗h ) . v e t o r [ 0 ] = (∗h ) . v e t o r [ i ] ;
(∗h ) . v e t o r [ i ] = t ;
(∗h ) . tam−−;
Desce ( h , 0 ) ;
}
(∗h ) . tam = n ;
} /∗ HeapSort ∗/
Nu´mero de operac¸o˜es: O(n log n) (um dos algoritmos o´timos).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Filas de prioridade 217
A´rvores gerais
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores gerais 218
Exemplo de a´rvore geral
A
B
F G
C
H
D E
I
L
J K
I a´rvores gerais nunca sa˜o vazias
I as suba´rvores sa˜o ordenadas: primeira, segunda, etc
I o nu´mero de suba´rvores pode ser qualquer, inclusive zero
I conceitos naturais: grau, filhos, pai, descendente, altura, etc
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores gerais 219
Representac¸a˜o de a´rvores gerais
#d e f i n e GRAU MAX 10
typedef s t r u c t
NoArvGera l ∗A r v G e r a l ;
typedef s t r u c t NoArvGera l {
T i n f o ;
i n t grau ;
A r v G e r a l f i l h o s [GRAU MAX ] ;
} NoArvGera l ;
. . .
p = m a l l o c ( s i z e o f ( NoArvGera l ) ) ;
. . .
typedef s t r u c t
NoArvGera l ∗A r v G e r a l ;
typedef s t r u c t NoArvGera l {
T i n f o ;
i n t grau ;
A r v G e r a l f i l h o s [ 1 ] ;
} NoArvGera l ;
. . .
p = m a l l o c ( s i z e o f ( NoArvGera l )+
( grau −1)∗ s i z e o f ( A r v G e r a l ) ) ;
. . .
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores gerais 220
Florestas
Uma floresta e´ uma sequeˆncia, possivelmente vazia, de a´rvores gerais.
Exemplo:
A
D
J
E
K L
F G
M
B C
H I
N O
Q
P
Note-se que as suba´rvores de um no´ de uma a´rvore geral constituem uma
floresta.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores gerais 221
Floresta representada como a´rvore bina´ria
A
D
J
E
K L
F G
M
B C
H I
N O
Q
P
I o campo esquerdo aponta para a raiz da primeira suba´rvore original
I o campo direito aponta para o no´ irma˜o seguinte
I as ra´ızes das a´rvores da floresta sa˜o consideradas irma˜s.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores gerais 222
Floresta representada como a´rvore bina´ria (cont.)
I A a´rvore bina´ria B(F ) que representa uma floresta
F = (T1, T2, . . . , Tm) e´ definida por:
I a´rvore bina´ria vazia se F e´ uma floresta vazia (m = 0);
I a´rvore bina´ria cuja raiz conte´m a mesma informac¸a˜o da raiz de T1; cuja
suba´rvore esquerda e´ dada por B((T11, T12, . . . , T1m1)) onde
(T11, T12, . . . , T1m1) e´ a floresta das suba´rvores de T1; e cuja suba´rvore
direita e´ dada por B((T2, . . . , Tm)).
I Conclui-se facilmente que toda floresta tem uma u´nica representac¸a˜o
bina´ria.
I A implementac¸a˜o de a´rvores bina´rias e´ mais simples.
I Exerc´ıcio: definir a transformac¸a˜o contra´ria F(T ) que obte´m a
floresta a partir da a´rvore bina´ria T que a representa.
I Exerc´ıcio: verificar se toda a´rvore bina´ria representa uma floresta.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores gerais 223
Percursos em profundidade de florestas
Os percursos de uma floresta F = (T1, T2, . . . , Tm) sa˜o definidos por:
I Pre´-ordem de florestas:
Visitar a raiz de T1
Percorrer a floresta F1 em pre´-ordem de florestas
Percorrer a floresta (T2, . . . , Tm) em pre´-ordem de
florestas
I Po´s-ordem de florestas:
Percorrer a floresta F1 em po´s-ordem de florestas
Percorrer a floresta (T2, . . . , Tm) em po´s-ordem de
florestas
Visitar a raiz de T1
I Inordem de florestas:
Percorrer a floresta F1 em inordem de florestas
Visitar a raiz de T1
Percorrer a floresta (T2, . . . , Tm) em inordem de florestas
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores gerais 224
Percursos em profundidade de florestas (cont.)
A
D
J
E
K L
F G
M
B C
H I
N O
Q
P
Pre´-ordem: A,D,J ,E,K,L,F ,G,M ,B,C,H,I,N ,O,Q,P
Po´s-ordem: J ,L,K,M ,G,F ,E,D,Q,P ,O,N ,I,H,C,B,A
Inordem: J ,D,K,L,E,F ,M ,G,A,B,H,N ,Q,O,P ,I,C
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores gerais 225
Percursos em profundidade de florestas (cont.)
Propriedades:
I percurso de uma floresta F produz o mesmo resultado que o percurso
(bina´rio) correspondente da a´rvore B(F ).
I pre´-ordem de florestas e´ semelhante a` pre´-ordem
de a´rvores bina´rias
I inordem de florestas e´ semelhante a` po´s-ordem de a´rvores bina´rias
I po´s-ordem de florestas na˜o tem uma interpretac¸a˜o natural
Desafio:
Elabore um algoritmo para percurso em largura de a´rvores gerais sob
representac¸a˜o bina´ria.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores gerais 226
A´rvores digitais
(Tries)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores digitais 227
Conjuntos de cadeias de caracteres
Exemplo:
a at from his no
an be had i not
and but have in of
are by he is on
as for her it or
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores digitais 228
A´rvore digital
a at from his no
an be had i not
and but have in of
are by he is on
as for her it or
a b f h i n o
n r s t e u y o r a e i n s t o f n r
d e t r o d v r s t
m e
I Arestas sa˜o rotuladas com as letras das palavras.
I No´s cheios indicam o fim de uma cadeia.
I Sa˜o fatorados os prefixos comuns das cadeias.
I Nu´meros para o exemplo:
I 39 no´s
I 20 folhas
I 19 no´s internos (na˜o folhas)
I 25 no´s cheios (25 palavras)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores digitais 229
Implementac¸a˜o de a´rvores digitais
a b c y z
. . .
I Algoritmos de busca, inserc¸a˜o e remoc¸a˜o o´bvios (exerc´ıcio).
I Uso de memo´ria:
I 39× 26 = 1014 campos apontadores
I 38 campos sa˜o na˜o nulos
I Eliminando apontadores das folhas:
I 19× 26 = 494 campos apontadores
I 38 campos sa˜o na˜o nulos
I Existem alternativas mais econoˆmicas para representar os no´s.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores digitais 230
A´rvore digital com subcadeias
a at from his no
an be had i not
and but have in of
are by he is on
as for her it or
d
re s s e ut y or rom
d ve r
is n s t
t
f n r
a b f h i n o
n r s t e u y o r a e i n s t o f n r
d d v r t
I Uso de memo´ria:
I 12× 26 = 312 campos apontadores
I 31 campos sa˜o na˜o nulos
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores digitais 231
Autoˆmato finito minimal ac´ıclico
Exemplo: as 15 formas dos verbos ingleses: do, redo e undo
do redo undo
does redoes undoes
did redid undid
doing redoing undoing
done redone undone
r e d o i n g
u n
i
n
e
d
d
s
e
I Sa˜o fatorados tanto os prefixos quanto os sufixos comuns das cadeias.
I Algoritmo de busca igual ao de a´rvores digitais.
I Algoritmos de inserc¸a˜o e de remoc¸a˜o muito mais complicados.
I Uso de memo´ria:
I 11× 26 = 286 campos apontadores (no´s internos)
I 16 campos sa˜o na˜o nulos
I Se fosse a´rvore digital:
I 26× 26 = 676 campos apontadores (no´s internos)
I 37 campos seriam na˜o nulos
I As estruturas para um exemplo ana´logo em portugueˆs seriam maiores
(mais de 50 formas verbais) mas resultariam em muito mais economia.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o A´rvores digitais 232
Listas generalizadas
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 233
Conceito e exemplos
I Um a´tomo e´ um inteiro ou uma cadeia de caracteres.
I Uma lista generalizada e´ uma sequeˆncia:
(α1, α2, . . . , αn)
onde αi denota um a´tomo ou uma lista generalizada (definic¸a˜o
recursiva).
I Exemplos de listas:
A: ((4,7),(4,7,(8)))
B: ((1,4),(7,8))
C: (3,B,B)
D: (5,8,D)
E: ()
I As listas A, B, C, D e E teˆm, respectivamente, 2, 2, 3, 3 e 0
elementos.
I A definic¸a˜o de a´tomo poderia ser estendida para outros tipos de
valores.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 234
Expansa˜o de listas
A: ((4,7),(4,7,(8)))
B: ((1,4),(7,8))
C: (3,B,B)
D: (5,8,D)
E: ()
As listas C e D podem ser expandidas com as definic¸o˜es correspondentes:
C: (3,((1,4),(7,8)),((1,4),(7,8)))
D: (5,8,(5,8,(5,8,(...))))
A lista D tem treˆs elementos, mas inclui um nu´mero infinito de inteiros,
por ser recursiva.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 235
Implementac¸a˜o compartilhada
A: ((4,7),(4,7,(8)))
B: ((1,4),(7,8))
C: (3,B,B)
D: (5,8,D)
E: ()
A: 4 7
4 7 8
B: 7 8
1 4
C: 3
D: 5 8
E: NULL
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 236
Implementac¸a˜o com co´pia
A: ((4,7),(4,7,(8)))
B: ((1,4),(7,8))
C: (3,B,B)
D: (5,8,D)
E: ()
B: 7 8
1 4
C:
3
7 8
1 4
7 8
1 4
D:
5 8
5 8
5 8
. . .
I Na˜o e´ poss´ıvel completar a expansa˜o da lista D.
I As representac¸o˜es das listas A, B e E na˜o mudam.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 237
Representac¸a˜o de listas generalizadas
typedef s t r u c t RegLis taGen ∗ L i s t a G e n ;
typedef s t r u c t RegLis taGen {
L i s t a G e n prox ;
Boolean eAtomo ;
union {
i n t atomo ; /∗ ’ eAtomo ’ v e r d a d e i r o ∗/
L i s t a G e n l i s t a ; /∗ ’ eAtomo ’ f a l s o ∗/
} i n f o ;
} RegLis taGen ;
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 238
Exemplo de manipulac¸a˜o
Func¸a˜o de contagem de a´tomos:
i n t ContaAtomos ( L i s t a G e n p ) {
i n t s = 0 ;
whi le ( p!=NULL) {
i f ( p−>eAtomo )
s++;
e l s e
s += ContaAtomos ( p−> i n f o . l i s t a ) ;
p = p−>prox ;
}
r e t u r n s ;
} /∗ ContaAtomos ∗/
Problemas com compartilhamento:
I contagem repetida (caso da lista C ); pode ser intencional
I repetic¸a˜o infinita (caso da lista D)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 239
Representac¸a˜o alternativa
typedef s t r u c t RegLis taGen ∗ L i s t a G e n ;
typedef s t r u c t RegLis taGen {
Boolean v i s i t a d o ; /∗ i n i c i a l m e n t e f a l s o ∗/
L i s t a G e n prox ;
Boolean eAtomo ;
union {
i n t atomo ; /∗ ’ eAtomo ’ v e r d a d e i r o ∗/
L i s t a G e n l i s t a ; /∗ ’ eAtomo ’ f a l s o ∗/
} i n f o ;
} RegLis taGen ;
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 240
Exemplo de manipulac¸a˜o
Func¸a˜o geral de contagem de a´tomos:
i n t ContaAtomos ( L i s t a G e n p ) {
i n t s = 0 ;
whi le ( ( p!=NULL) && ! ( p−>v i s i t a d o ) ) {
p−>v i s i t a d o = t r u e ;
i f ( p−>eAtomo )
s++;
e l s e
s += ContaAtomos ( p−> i n f o . l i s t a ) ;
p = p−>prox ;
}
r e t u r n s ;
} /∗ ContaAtomos ∗/
Problema: restaurac¸a˜o dos valores do campo visitado para o pro´ximo
percurso.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 241
Exemplo de aplicac¸a˜o
Manipulac¸a˜o de polinoˆmios em mu´ltiplas varia´veis:
P (x, y, z) = x10y3z2 + 2x8y3z2 + 3x8y2z2 + x4y4z − 6x3y4z + 2yz
Representac¸a˜o poss´ıvel para cada termo:
coef x y z
I Problema: muito inflex´ıvel, somente para polinoˆmios em treˆs varia´veis.
I Alternativa: um polinoˆmio em k≥1 varia´veis pode ser considerado
um polinoˆmio em uma varia´vel, com coeficientes que sa˜o polinoˆmios
em k−1 varia´veis, etc:
P (x, y, z) = ((x10 + 2x8)y3 + 3x8y2)z2 + ((x4 − 6x3)y4 + 2x0y)z
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 242
Representac¸a˜o de polinoˆmios
((x10 + 2x8)y3 + 3x8y2)z2 + ((x4 − 6x3)y4 + 2x0y)z
Alternativa 1: representac¸a˜o uniforme em todos os n´ıveis:
z 2 1
y 4 1
x 02
x 4 31 −6
y 3 2
x 83
x 10 81 2
Note-se que o termo 2x0y e´ representado de maneira completa. Esta
representac¸a˜o torna os algoritmos mais simples.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 243
Representac¸a˜o
de polinoˆmios (cont.)
((x10 + 2x8)y3 + 3x8y2)z2 + ((x4 − 6x3)y4 + 2x0y)z
Alternativa 2: representac¸a˜o que elimina polinoˆmios “degenerados”
z 2 1
y 4 1
x 02
2
x 4 31 −6
y 3 2
x 83
x 10 81 2
Note-se que o termo 2x0y e´ representado como 2y. Esta representac¸a˜o
economiza memo´ria (retaˆngulo tracejado).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 244
Declarac¸a˜o de tipo
typedef s t r u c t Termo ∗ApTermo ;
typedef ApTermo P o l i n o m i o ;
typedef s t r u c t Termo {
P o l i n o m i o prox ;
Boolean eCabeca ;
union {
char v a r i a v e l ; /∗ s e e´ cabe c¸a ∗/
s t r u c t { /∗ s e e´ termo ∗/
i n t e x p o e n t e ;
Boolean c o e f I n t e i r o ;
union {
i n t c o e f I n t ;
P o l i n o m i o c o e f P o l i n ;
} c o e f ;
} termo ;
} no ;
} Termo ;
Exerc´ıcio: escrever as func¸o˜es de soma e de multiplicac¸a˜o para polinoˆmios
em mu´ltiplas varia´veis.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 245
LISP: uma linguagem para processamento de listas
I Programas sa˜o expressos como listas.
I Dados sa˜o a´tomos e listas.
I Aplicac¸o˜es:
I inteligeˆncia artificial
I scripts para Emacs
I scripts para AutoCAD
I ...
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 246
LISP (cont.)
Exemplo 1: func¸a˜o fatorial
( defun f a t o r i a l ( n )
( cond ( l e q n 1)
1
( mult n ( f a t o r i a l ( minus n 1 ) ) )
)
)
I A expressa˜o: (fatorial 5) produz: 120.
I Deve-se notar o uso de notac¸a˜o pre´-fixa.
I As implementac¸o˜es comuns de LISP permitem o uso de s´ımbolos de
operac¸o˜es como <=, + e ∗ em lugar de a´tomos.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 247
LISP (cont.)
Exemplo 2: concatenac¸a˜o e inversa˜o de listas
( defun c o n c a t ( p q )
( cond ( n u l l p )
q
( cons ( c a r p ) ( c o n c a t ( c d r p ) q ) )
)
)
( defun i n v e r t e ( p )
( cond ( n u l l p )
n i l
( c o n c a t ( i n v e r t e ( c d r p ) ) ( c a r p ) )
)
)
I A expressa˜o: (inverte ’(A B C D)) produz D C B A.
I A expressa˜o (car L) devolve o primeiro elemento da lista L.
I A expressa˜o (cdr L) devolve a lista L sem o primeiro elemento.
I A operac¸a˜o (cons x L) devolve a lista L com o elemento x inserido
na frente da lista.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Listas generalizadas 248
Espalhamento
(Hashing ou scattering)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 249
Tabelas de espalhamento
Exemplo de tabela com b=7 linhas e s=3 colunas:
1 2 3
0
1
2
f(’jo~ao’)→ 3 jo~ao
4
5
6
Supo˜e-se, neste caso, que:
I a func¸a˜o de espalhamento f produz resultados entre 0 e 6
I f(’jo~ao’) = 3
I existem no ma´ximo treˆs valores (s) a serem inseridos que produzem o
mesmo valor da func¸a˜o f .
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 250
Tabelas de espalhamento (cont.)
Exemplo de tabela com b=26 linhas e s=2 colunas:
1 2
0 anto^nio a´tila
1
2 carlos ce´lio
3 douglas
4 ernesto este^v~ao
5
· · ·
24
25 zoroastro
Foi usada uma func¸a˜o (muito ingeˆnua!) de espalhamento: ı´ndice da
primeira letra (a: 0, b: 1, ...).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 251
Virtudes e poblemas
I Virtudes
I simplicidade
I busca muito ra´pida (se a func¸a˜o de espalhamento for eficiente)
I Problemas
I escolha da func¸a˜o de espalhamento
I tratamento de coliso˜es
I tratamento de estouro da tabela
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 252
Construc¸a˜o de func¸o˜es de espalhamento
I Propriedades deseja´veis:
I eficieˆncia de ca´lculo
I bom espalhamento
I Te´cnicas:
I espalhamento m´ınimo perfeito
I espalhamento pseudo-aleato´rio: combinac¸a˜o de va´rias te´cnicas
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 253
Construc¸a˜o de func¸o˜es de espalhamento (cont.)
Divisa˜o
I O nome, tratado como um nu´mero na base 26, e´ dividido por um
nu´mero p relativamente primo f(x) = x mod p; p sera´ adotado como
o nu´mero de linhas da tabela.
I Para p = 51 ter´ıamos:
f(carlos) = ( ((((2× 26 + 0)× 26 + 17)× 26 + 11)
×26 + 14)× 26 + 18 ) mod 51
= 24.069.362 mod 51 = 14
I Na realidade, o ca´lculo pode ser simplificado, com a operac¸a˜o mod
aplicada a cada passo.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 254
Construc¸a˜o de func¸o˜es de espalhamento (cont.)
Selec¸a˜o de algarismos e meio-do-quadrado
I O nome e´ tratado como uma sequeˆncia de algarismos ou de bytes ou
de bits, e uma subsequeˆncia e´ selecionada para representar o ı´ndice.
I Por exemplo, suponhamos que todos os nomes sa˜o representados
como a sequeˆncia de d´ıgitos x = d0d1 · · · d11 em alguma base
conveniente; uma escolha seria f(x) = d3d5d9.
I Exemplo: a representac¸a˜o de ‘carlos’ poderia ser 020017111418.
Supusemos que cada letra e´ indicada por dois d´ıgitos que indicam a
posic¸a˜o no alfabeto, ou seja 00 para ‘a’, 01 para ‘b’, etc. Ter´ıamos
enta˜o f(carlos) = 074.
I Frequentemente, antes de fazer a selec¸a˜o, e´ calculado o quadrado do
identificador (tratado como nu´mero); e´ o me´todo
“meio-do-quadrado” (mid-square).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 255
Construc¸a˜o de func¸o˜es de espalhamento (cont.)
Dobramento (folding)
I O nome e´ tratado como uma sequeˆncia de algarismos ou de bytes ou
de bits, e algumas subsequeˆncias sa˜o combinadas por operac¸o˜es
convenientes para produzir um ı´ndice.
I Por exemplo, suponhamos que todos os nomes sa˜o representados
como uma sequeˆncia de bits x = b0b1b2b3b4 · · · ; uma escolha seria:
f(x) = b0b1b2b3b4b5 ⊕ b6b7b8b9b10b11 ⊕ · · ·
onde ⊕ denota a operac¸a˜o de ou exclusivo bit a bit.
I Exemplo: a representac¸a˜o de ‘carlos’ usada anteriormente poderia
ser (com cinco bits para cada nu´mero):
00010 00000 10001 01011 01110 10010
produzindo a sequencia de bits: 000100000010001010110111010010 e
o resultado:
f(000100000010001010110111010010) =
000100⊕000010⊕001010⊕110111⊕010010 = 101001 = 4110
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 256
Tratamento de coliso˜es: enderec¸amento aberto
I Busca sistema´tica de outras entradas dispon´ıveis na tabela:
I reespalhamento linear
I reespalhamento quadra´tico
I reespalhamento duplo
I Em todos os casos, os algoritmos de busca, inserc¸a˜o e remoc¸a˜o
devera˜o ser coerentes.
I Exemplos usam: anto^nio, carlos, douglas, ce´lio, armando,
zoroastro, a´tila, alfredo (nesta ordem).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 257
Reespalhamento linear
anto^nio, carlos, douglas, ce´lio, armando, zoroastro, a´tila, alfredo
Usando (f(x) + i) mod b, (i = 0, 1, · · · ), procura a primeira posic¸a˜o livre.
0 anto^nio
1 armando
2 carlos
3 douglas
4 ce´lio
5 a´tila
6 alfredo
7
· · · · · ·
25 zoroastro
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 258
Reespalhamento quadra´tico
anto^nio, carlos, douglas, ce´lio, armando, zoroastro, a´tila, alfredo
Usando (f(x) + i2) mod b, (i = 0, 1, · · · ), procura a primeira posic¸a˜o livre.
0 anto^nio
1 armando
2 carlos
3 douglas
4 a´tila
5
6 ce´lio
7
8
9 alfredo
· · · · · ·
25 zoroastro
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 259
Reespalhamento duplo
anto^nio, carlos, douglas, ce´lio, armando, zoroastro, a´tila, alfredo
I Usando (f(x) + i× g(x))
mod b, (i = 0, 1, · · · ) procura a primeira
posic¸a˜o livre.
I g(x) e´ a func¸a˜o de reespalhamento;
por exemplo, g(x) = (cmod 3) + 1
onde c e´ a segunda letra.
0 anto^nio
1
2 carlos
3 douglas
4 ce´lio
5
6 armando
7
8 a´tila
9 alfredo
· · · · · ·
25 zoroastro
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 260
Remoc¸a˜o
I La´pides (tombstones):
I entradas que indicam posic¸o˜es ocupadas para fins de busca, mas livres
para fins de inserc¸a˜o.
I podem ser usadas com qualquer esquema de espalhamento
I Exemplo: remoc¸a˜o da entrada armando (tabela com reespalhamento
linear):
0 anto^nio
1 armando
2 carlos
3 douglas
4 ce´lio
5 a´tila
6 alfredo
7
· · · · · ·
25 zoroastro
0 anto^nio
1 ++++++++
2 carlos
3 douglas
4 ce´lio
5 a´tila
6 alfredo
7
· · · · · ·
25 zoroastro
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 261
Eficieˆncia com enderec¸amento aberto
I Nu´mero me´dio de comparac¸o˜es para encontrar um elemento:
C(n) = (2− α)/(2− 2α)
onde:
I α = n/b (fator de carga, 0 ≤ α ≤ 1)
I n e´ o nu´mero de entradas
I b e´ o tamanho da tabela
I Exemplo de tabela com 1000 entradas:
n C(n)
100 1,06
200 1,13
300 1,21
400 1,33
500 1,50
600 1,75
700 2,17
800 3,00
900 5,50
950 10,5
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 262
Tratamento de coliso˜es: listas ligadas
Te´cnica de encadeamento (chaining): utiliza listas ligadas para manter
entradas com o mesmo valor da func¸a˜o de espalhamento.
Exemplo:
anto^nio, carlos, douglas, ce´lio, armando, zoroastro, a´tila, alfredo
0
1
2
3
4
5
25
. . .
antoˆnio
carlos
douglas
ce´lio carlos
armando antoˆnio
zoroastro
a´tila armando antoˆnioalfredo a´tila armando antoˆnio
As listas poderiam ser ordenadas.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 263
Eficieˆncia com encadeamento
I Nu´mero me´dio de comparac¸o˜es para encontrar um elemento:
C(n) = 1 + α/2
onde:
I α = n/b (fator de carga, α > 0)
I n e´ o nu´mero de entradas
I b e´ o tamanho da tabela
I Exemplo de tabela com 1000 entradas:
n C(n)
100 1,05
200 1,10
400 1,20
500 1,25
1000 1,50
2000 2,00
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Espalhamento 264
Compressa˜o de textos
(Codificac¸a˜o de Huffman)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Compressa˜o de textos 265
Compressa˜o de textos
I Objetivos:
I economia de espac¸o
I velocidade de transmissa˜o
I Representac¸a˜o normal: um byte (8 bits) por caractere (alfabetos
“comuns”)
I Compressa˜o por contagem (run-length encoding)
I Codificac¸a˜o de Huffman
I Algoritmos de codificac¸a˜o aritme´tica (Lempel-Ziv – zip, gzip, winzip,
et.)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Compressa˜o de textos 266
Codificac¸a˜o de Huffman
I Explora frequeˆncias de ocorreˆncia de caracteres
I Exemplo de alfabeto: A = {a, b, c, d, e, f}
a b c d e f
frequeˆncia de cada letra 45 13 12 16 9 5
codificac¸a˜o usando 3 bits 000 001 010 011 100 101
codificac¸a˜o de tamanho varia´vel 0 101 100 111 1101 1100
I Para um arquivo de 100.000 caracteres:
I codificac¸a˜o fixa: 300.000 bits
I codificac¸a˜o varia´vel: 224.000 bits (economia de 25%)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Compressa˜o de textos 267
A´rvores bina´rias de codificac¸a˜o
Codificac¸a˜o fixa a: 000 b: 001 c: 010 d: 011 e: 100 f: 101
100
86
58
a:45 b:13
28
c:12 d:16
14
14
e:9 f:5
0 1
0 1 0
0 1 0 1 0 1
I Os ro´tulos das arestas da raiz ate´ uma folha compo˜em o co´digo da
letra correspondente.
I Para obter o co´digo de uma letra, e´ necessa´rio percorrer a a´rvore
partindo da folha correspondente ate´ a raiz.
I Exemplo: abc = 000‖001‖010 = 000001010.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Compressa˜o de textos 268
A´rvores bina´rias de codificac¸a˜o (cont.)
Codificac¸a˜o varia´vel a: 0 b: 101 c: 100 d: 111 e: 1101 f: 1100
100
a:45 55
25
c:12 b:13
30
14
f:5 e:9
d:16
0 1
0 1
0 1 0 1
0 1
I O co´digo de uma letra na˜o pode constituir um prefixo de uma outra
letra.
I Exemplo: abc = 0‖101‖100 = 0101100.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Compressa˜o de textos 269
Construc¸a˜o da a´rvore de Huffman
I Algoritmo (guloso):
1. Construa uma floresta de folhas, cada uma correspondendo a um
caractere, com a respectiva frequeˆncia como seu peso.
2. Enquanto a floresta tiver mais de uma a´rvore, repita:
I procure na floresta duas a´rvores t1 e t2 de menor peso
I construa uma nova a´rvore bina´ria t, com suba´rvores t1 e t2, e com peso
que e´ a soma dos pesos das duas suba´rvores
I remova t1 e t2 da floresta, e insira t.
I A soluc¸a˜o na˜o e´ u´nica (pode haver va´rias escolhas de peso m´ınimo),
mas todos os resultados sa˜o equivalentes quanto a` eficieˆncia de
compressa˜o.
I Se o alfabeto for razoavelmente grande, pode-se utilizar uma fila de
prioridade para selecionar, em cada passo, duas a´rvores de menor
peso.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Compressa˜o de textos 270
Construc¸a˜o da a´rvore de Huffman (cont.)
Exemplo:
a:45 b:13 c:12 d:16 e:9 f:5
a:45 b:13 c:12 d:16 14
f:5 e:9
a:45 d:16 14
f:5 e:9
25
c:12 b:13
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Compressa˜o de textos 271
Construc¸a˜o da a´rvore de Huffman (cont.)
a:45 d:16 14
f:5 e:9
25
c:12 b:13
a:45 25
c:12 b:13
30
14
f:5 e:9
d:16
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Compressa˜o de textos 272
Construc¸a˜o da a´rvore de Huffman (cont.)
a:45 25
c:12 b:13
30
14
f:5 e:9
d:16
a:45 55
25
c:12 b:13
30
14
f:5 e:9
d:16
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Compressa˜o de textos 273
Construc¸a˜o da a´rvore de Huffman (cont.)
a:45 55
25
c:12 b:13
30
14
f:5 e:9
d:16
100
a:45 55
25
c:12 b:13
30
14
f:5 e:9
d:16
0 1
0 1
0 1 0 1
0 1
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Compressa˜o de textos 274
Observac¸o˜es
I Adotadas certas hipo´teses, demonstra-se a otimalidade de compressa˜o
I Algoritmo de compressa˜o: para cada letra, deve acessar a folha
correspondente da a´rvore e reconstruir o caminho a` raiz – pode ser
preprocessado
I Algoritmo de descompressa˜o: percorre a a´rvore a partir da raiz
seguindo o caminho indicado por bits da codificac¸a˜o
I Variantes:
I a´rvore fixa, por exemplo, uma para cada l´ıngua
I a´rvore por texto (acompanha o arquivo)
I a´rvores dinaˆmicas (Faller, Gallager e Knuth).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Compressa˜o de textos 275
Gerenciamento de memo´ria
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 276
Gerenciamento de memo´ria
Va´rios aspectos:
I alocac¸a˜o com e sem disciplina de pilha
I caracter´ısticas da linguagem de programac¸a˜o
I registros de tamanho fixo ou varia´vel
I gerenciamento expl´ıcito (malloc e free)
I gerenciamento impl´ıcito (coleta de lixo e contagem de refereˆncias)
I gerenciamento misto
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 277
Gerenciamento expl´ıcito
Configurac¸a˜o gene´rica da memo´ria:
disp
mLivre: ? mEm uso:
Configurac¸a˜o inicial:
M
disp
I A varia´vel disp (memo´ria dispon´ıvel) e´ global.
I A lista das a´reas
livres e´ ordenada pelo valor dos apontadores.
I M denota o tamanho da a´rea livre inicial; m de uma a´rea livre ou em
uso.
I A func¸a˜o de alocac¸a˜o devolve o apontador para o primeiro byte livre
da a´rea.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 278
Gerenciamento expl´ıcito (cont.)
Uma versa˜o muito simples de malloc(n) (f e´ o tamanho da parte fixa de
cada a´rea – apontador mais o campo de tamanho):
1. procure na lista disp o primeiro elemento (ou o elemento de tamanho
m´ınimo) p com tamanho≥n+f
2. remova p da lista disp
3. quebre a a´rea apontada por p em duas partes: uma p1 de tamanho
n+ f e outra p2 com o que sobrar (se houver sobra suficiente)
4. insira p2 na lista disp (se existir)
5. devolva p1 + f
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 279
Gerenciamento expl´ıcito (cont.)
Uma versa˜o muito simples de free(p):
1. procure na lista disp o ponto de inserc¸a˜o para p (ordem crescente dos
apontadores)
2. verifique se o predecessor e/ou sucessor de p neste ponto sa˜o
adjacentes a` a´rea apontada por p
3. se for poss´ıvel, junte a a´rea liberada a` predecessora e/ou a` sucessora,
modificando os campos de tamanho
4. atualize a lista
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 280
Gerenciamento expl´ıcito (cont.)
Problemas:
I O que fazer quando malloc na˜o acha uma a´rea de tamano suficiente –
requer outra a´rea ao sistema operacional
I Fragmentac¸a˜o – apo´s va´rias alocac¸o˜es e liberac¸o˜es, com tamanhos
varia´veis, havera´ tendeˆncia a produzir muitas a´rea livres pequenas
I Busca numa lista ligada pode ser ineficiente
I Algumas soluc¸o˜es:
I blocos com marcas de fronteira (boundary tags)
I sistema de blocos conjugados (buddy system)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 281
Marcas de fronteira
t tmLivre:
f fmEm uso:
I As a´reas livres constituem uma lista duplamente ligada.
I m denota o tamanho da a´rea.
I t e f denotam os valores booleanos que indicam se a a´rea e´ livre.
I A func¸a˜o de alocac¸a˜o devolve o apontador para o primeiro byte livre
da a´rea.
I Na˜o e´ necessa´rio fazer uma busca na lista para encontrar as a´reas
vizinhas.
I Exerc´ıcio: esboc¸ar a implementac¸a˜o das func¸o˜es malloc e free.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 282
Sistema de blocos conjugados
0-15
0-1
0-3
0-1 2-3
4-7
4-5 6-7
8-15
8-11
8-9 10-11
12-15
12-13 14-15
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
k=4
k=3
k=2
k=1
k=0
I Uma a´rvore bina´ria imagina´ria em que cada no´ representa um bloco
de alocac¸a˜o.
I Cada folha da a´rvore representa um bloco m´ınimo de alocac¸a˜o.
I Cada n´ıvel k da a´rvore (a partir das folhas) representa a alocac¸a˜o de
uma a´rea constitu´ıda de 2k blocos m´ınimos.
I A´reas conjugadas (irma˜s) facilmente reconhecidos pelos ı´ndices sob
forma bina´ria.
I O exemplo exibe a a´rvore para uma memo´ria de 24=16 blocos.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 283
Sistema de blocos conjugados (cont.)
I Formato das a´reas:
t kLivre:
f kEm uso:
I t e f denotam os valores booleanos que indicam se a a´rea e´ livre.
I k indica que o tamanho da a´rea e´ 2k.
I Para cada valor de k, existe uma lista duplamente ligada disp[k] de
blocos livres de tamanho 2k.
I A func¸a˜o de alocac¸a˜o devolve o apontador para o primeiro byte livre
da a´rea.
I Dado o nu´mero do bloco inicial de uma a´rea (em bina´rio) de tamanho
2k, o nu´mero da a´rea conjugada e´ determinado complementando o
k-e´simo bit (a partir da direita); exemplo de bloco 12 para k=2:
1210=11002 =⇒ 10002=810
Portanto, a a´rea conjugada de quatro blocos tem in´ıcio no bloco 8.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 284
Sistema de blocos conjugados (cont.)
Esboc¸o da func¸a˜o malloc(n) (f e´ o tamanho da parte fixa de cada a´rea –
marca de uso, tamanho):
1. procure um k tal que 2k ≥ n+ f , e a lista de blocos para k na˜o esta´
vazia; remova desta lista uma a´rea p
2. se 2k−1 ≥ n+ f , quebre a a´rea p em duas (conjugadas), acerte os
tamanhos e insira uma delas na lista de a´reas para tamanho k − 1
3. repita o passo anterior para k − 2, k − 3, ..., enquanto poss´ıvel
4. devolva o apontador p+ f
Note-se que o desperd´ıcio de memo´ria de uma a´rea pode chegar a quase
50%.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 285
Sistema de blocos conjugados (cont.)
Esboc¸o da func¸a˜o free(p):
1. seja k o expoente correspondente ao tamanho de p
2. calcule o enderec¸o da a´rea q conjugada de p
3. se a a´rea q esta´ livre:
I remova q da lista disp[k]
I junte as a´reas p e q para formar uma nova a´rea livre p
I fac¸a k = k+1
I volte ao passo inicial
4. se a a´rea q na˜o esta´ livre (ou na˜o existe – p ja´ e´ a memo´ria inteira),
insira p na lista disp[k]
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 286
Sistema de blocos conjugados (cont.)
Uma outra alternativa e´ utilizar os nu´meros de Fibonacci:
0-12
0-7
0-4
0-2
0-1 3-4
5-7
5-6
8-12
8-10
8-9 11-12
0 1 2 3 4 5 6 7 8 9 10 11 12
F2=1
F3=2
F4=3
F5=5
F6=8
F7=13
I Esta soluc¸a˜o diminui o desperd´ıcio de memo´ria, mas torna mais
complicados os algoritmos.
I Exerc´ıcio: esboc¸ar as func¸o˜es malloc e free para esta alternativa.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 287
Gerenciamento impl´ıcito
Coleta de lixo (garbage collection)
I Caracter´ısticas:
I operac¸a˜o de alocac¸a˜o impl´ıcita em algumas operac¸o˜es
I na˜o existe operac¸a˜o de liberac¸a˜o expl´ıcita ou e´ opcional
I liberac¸a˜o de memo´ria realizada, em geral, quando na˜o ha´ mais espac¸o
para alocar
I exemplos: Java, LISP, Prolog, Perl, Python, Modula-3, ...
I contra-exemplos: C, Pascal, C++, ...
I Fases:
I marcac¸a˜o
I coleta ou compactac¸a˜o
I caso haja compactac¸a˜o: ca´lculo de destino; atualizac¸a˜o dos
apontadores; co´pia dos blocos
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 288
Marcac¸a˜o e coleta
I Hipo´teses
I Localizac¸a˜o conhecida das varia´veis apontadoras na pilha de execuc¸a˜o.
I Localizac¸a˜o conhecida de apontadores em cada bloco.
I Blocos de tamanho fixo ou com campos de comprimento.
I Marcas de utilizac¸a˜o em cada bloco, inicialmente falsas.
I Algoritmo:
I Percurso ana´logo a` pre´-ordem e marcac¸a˜o a partir das varia´veis na
pilha.
I Percurso linear da memo´ria para coleta de blocos livres e restaurac¸a˜o
das marcas.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 289
Marcac¸a˜o e coleta (cont.)
Exemplo de situac¸a˜o inicial:
I supo˜e blocos iguais
I setas mais fortes: apontadores nas varia´veis na pilha de execuc¸a˜o
I blocos acess´ıveis a serem marcados marcados em cor cinza
f f f f f f f f f f f f
Apo´s a marcac¸a˜o:
f t t t f t f t t f t t
Apo´s a coleta:
f f f f f f f f f f f f
disp
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 290
Marcac¸a˜o e coleta (cont.)
I Hipo´teses simplificadoras:
I tamanho fixo de registros
I localizac¸a˜o conhecida dos apontadores (um vetor)
I Declarac¸o˜es:
typedef s t r u c t Bloco ∗ApBloco ;
typedef s t r u c t Bloco {
Boolean marca ;
ApBloco d e s t i n o ; /∗ s e houver compactac¸ a˜o ∗/
. . .
i n t numAps ;
ApBloco a p o n t s [NUM MAX APONTS ] ;
}
Bloco ;
ApBloco d i s p ; /∗ i n i c i a l m e n t e t o d o s os b l o c o s ∗/
Bloco memoria [ TAM MEM DIN ] ;
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 291
Marcac¸a˜o e coleta (cont.)
Func¸a˜o de marcac¸a˜o:
vo id Marcar ( ApBloco p ) {
i n t i ;
i f ( p!=NULL) {
i f ( ! p−>marca ) {
p−>marca = t r u e ;
f o r ( i =0; i<p−>numAps ; i ++)
Marcar ( p−>a p o n t s [ i ] ) ;
}
}
} / ∗ Marcar ∗/
A func¸a˜o Marcar deve ser chamada para cada varia´vel apontadora na pilha
de execuc¸a˜o.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 292
Marcac¸a˜o e coleta (cont.)
Func¸a˜o de coleta:
vo id C o l e t a r ( ) {
i n t i ;
d i s p = NULL ;
f o r ( i =0; i<TAM MEM DIN ; i ++)
i f ( memoria [ i ] . marca ) /∗ em uso ∗/
memoria [ i ] . marca = f a l s e ;
e l s e { /∗ i n s e r e na l i s t a d i s p o n ı´ v e l ∗/
memoria [ i ] . a p o n t s [ 0 ] = d i s p ;
d i s p = &(memoria [ i ] ) ;
}
} /∗ C o l e t a r ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 293
Marcac¸a˜o e compactac¸a˜o
I Hipo´teses
I Localizac¸a˜o conhecida das varia´veis apontadoras na pilha de execuc¸a˜o.
I Localizac¸a˜o conhecida de apontadores em cada bloco.
I Blocos de tamanho fixo ou com campos de comprimento.
I Marcas de utilizac¸a˜o em cada bloco, inicialmente falsas.
I Algoritmo:
I Percurso ana´logo a` pre´-ordem e marcac¸a˜o a partir das varia´veis na
pilha.
I Ca´lculo dos novos enderec¸os dos blocos.
I Atualizac¸a˜o dos campos apontadores.
I Compactac¸a˜o (co´pia).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 294
Marcac¸a˜o e compactac¸a˜o (cont.)
Exemplo de situac¸a˜o inicial:
I supo˜e blocos iguais
I setas mais fortes: apontadores nas varia´veis na pilha de execuc¸a˜o
I blocos acess´ıveis a serem marcados marcados em cor cinza
f f f f f f f f f f f f
Apo´s a marcac¸a˜o:
f t t t f t f t t f t t
Apo´s o ca´lculo dos novos enderec¸os (tracejados):
f t t t f t f t t f t t
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 295
Marcac¸a˜o e compactac¸a˜o (cont.)
Apo´s o ca´lculo dos novos enderec¸os (tracejados):
f t t t f t f t t f t t
Apo´s a atualizac¸a˜o dos apontadores, inclusive os da pilha:
f t t t f t f t t f t t
Apo´s a compactac¸a˜o:
f f f f f f f f f f f f
disp
A varia´vel disp aponta para o in´ıcio da a´rea cont´ıgua liberada pela
operac¸a˜o de compactac¸a˜o (na˜o e´ necessa´rio usar uma lista ligada).
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 296
Marcac¸a˜o e compactac¸a˜o (cont.)
I Sa˜o adotadas as mesmas hipo´teses do caso de marcac¸a˜o e coleta.
I A func¸a˜o marcar e´ a mesma.
I Func¸a˜o de ca´lculo dos novos enderec¸os:
vo id C a l c u l a r D e s t i n o ( ) {
i n t i , j = 0 ;
f o r ( i =0; i<TAM MEM DIN ; i ++)
i f ( memoria [ i ] . marca ) {
memoria [ i ] . d e s t i n o = &(memoria [ j ] ) ;
j ++;
}
d i s p = &(memoria [ j ] ) ; /∗ p r i m e i r o b l o c o l i v r e ∗/
} /∗ C a l c u l a r D e s t i n o ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 297
Marcac¸a˜o e compactac¸a˜o (cont.)
Func¸a˜o de atualizac¸a˜o dos apontadores:
vo id A t u a l i z a ( ) {
i n t i , j = 0 ;
f o r ( i =0; i<TAM MEM DIN ; i ++)
i f ( memoria [ i ] . marca )
f o r ( j =0; j<memoria [ i ] . numAps ; j ++) {
memoria [ i ] . a p o n t s [ j ] =
( memoria [ i ] . a p o n t s [ j ])−> d e s t i n o ;
}
} /∗ A t u a l i z a ∗/
Devem ser atualizadas tambe´m todas as varia´veis apontadoras na pilha de
execuc¸a˜o.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 298
Marcac¸a˜o e compactac¸a˜o (cont.)
Func¸a˜o de compactac¸a˜o:
vo id Move ( ) {
i n t i ;
f o r ( i =0; i<TAM MEM DIN ; i ++)
i f ( memoria [ i ] . marca ) {
memoria [ i ] . marca = f a l s e ;
∗( memoria [ i ] . d e s t i n o ) = memoria [ i ] ;
}
} /∗ Move ∗/
Adaptac¸a˜o para blocos de tamanho varia´vel: introduzir o campo tamanho
em cada bloco e adaptar as func¸o˜es.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 299
Contagem de refereˆncias
I As te´cnicas de coleta de lixo (marcac¸a˜o e coleta ou compactac¸a˜o)
encontram e liberam toda a memo´ria dispon´ıvel de uma vez.
I O processo pode ser bastante demorado, com tempo de execuc¸a˜o
proporcional ao tamanho total da memo´ria dinaˆmica.
I A execuc¸a˜o da coleta de lixo interrompe o processo em curso; esta
interrupc¸a˜o pode demorar mais do que seria aceita´vel am algumas
aplicac¸o˜es.
I Dependendo da complexidade das estruturas de dados criadas pelo
programa, a fase de marcac¸a˜o pode exigir memo´ria adicional
aprecia´vel para manter a pilha de execuc¸a˜o.
I A te´cnica de contagem de refereˆncias tem a caracter´ıstica de, em
geral, distribuir o tempo de gerenciamento de memo´ria ao longo da
execuc¸a˜o normal do programa.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 300
Contagem de refereˆncias (cont.)
I Cada bloco alocado possui um campo inteiro refs contendo o nu´mero de
varia´veis (normais ou dinaˆmicas) que apontam para o bloco.
I Durante a alocac¸a˜o de um bloco, o seu campo refs recebe o valor inicial 1.
I Toda varia´vel ou campo apontador, antes de ser atribu´ıdo, recebe o valor
NULL.
I Todo comando de atribuic¸a˜o que envolve apontadores e´ implementado pela
func¸a˜o AtrbuiApont(ApBloco *p, ApBloco q):
typedef s t r u c t Bloco ∗ApBloco ;
typedef s t r u c t Bloco {
i n t r e f s ;
. . .
i n t numAps ;
ApBloco
a p o n t s [NUM MAX APONTS ] ;
} Bloco ;
vo id A t r i b u i A p o n t ( ApBloco ∗p ,
ApBloco q ) {
i f ( q!=NULL) ( q−>r e f s )++;
i f ( (∗ p )!=NULL) {
( (∗ p)−> r e f s )−−;
i f ( ( (∗ p)−> r e f s )==0)
D e s a l o c a R e f s (∗p ) ;
}
∗p = q ;
}
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 301
Contagem de refereˆncias (cont.)
I A func¸a˜o DesalocaRefs(p):
I desaloca o bloco apontado por p
I decrementa os contadores dos blocos referidos em p
I caso algum destes contadores torne-se nulo, a func¸a˜o e´ chamada
recursivamente
I Problemas:
I dependendo das estruturas de dados, o tempo de execuc¸a˜o de comando
de atribuic¸a˜o entre apontadores e´ imprevis´ıvel devido a` recurisividade
da func¸a˜o DesalocaRefs
I o me´todo, como exposto, na˜o funciona para estruturas com
circularidades; exemplo:
p
2 1 1 1 1
apo´s a atribuic¸a˜o p = NULL:
p
1 1 1 1 1
Os no´s da lista na˜o seriam liberados. Alguns sistemas utilizam um
esquema misto: contagem de refereˆncias e coleta de lixo.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Gerenciamento de memo´ria 302
Abstrac¸a˜o de Dados e Objetos
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 303
Tipos abstratos de dados
I Um tipo abstrato de dados (TAD) e´ constitu´ıdo por um conjunto de
valores e um conjunto de operac¸o˜es sobre estes valores.
I Os valores possuem uma representac¸a˜o e podem ser muito simples
(inteiros, bytes, ...) ou bastante complexos (pilhas, a´rvores, ...).
I Exemplo de especificac¸a˜o de um TAD Figura atrave´s de declarac¸o˜es
em C:
typedef vo id ∗ F i g u r a ;
F i g u r a R e ta n g u l o ( f l o a t a l t , f l o a t l a r g ) ;
F i g u r a C i r c u l o ( f l o a t r a i o ) ;
F i g u r a Quadrado ( f l o a t l a d o ) ;
f l o a t Area ( F i g u r a f i g ) ;
vo id T r a n s l a d a r ( F i g u r a f i g , f l o a t dx ,
f l o a t dy ) ;
vo id Desenhar ( F i g u r a f i g ) ;
I A espoecificac¸a˜o de um tipo como “void ∗” e´ uma te´cnica comum
em C para “esconder” a implementac¸a˜o.
I Normalmente, estas declarac¸o˜es, chamadas a`s vezes de interface ou
API (Application Programming Interface) estariam num arquivo
denominado figuras.h.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 304
Tipos abstratos de dados (cont.)
I Usando a especificac¸a˜o, e´ poss´ıvel escrever programas que utilizam o
TAD, mesmo sem completar a sua implementac¸a˜o.
I Exemplo de utilizac¸a˜o do TAD Figura:
#i n c l u d e ” f i g u r a s . h”
i n t main ( ) {
F i g u r a c = C i r c u l o ( 1 0 . 0 ) ;
F i g u r a r = R e t an g u lo ( 1 0 . 0 , 2 0 . 0 ) ;
F i g u r a q = Quadrado ( 5 0 . 0 ) ;
T r a n s l a d a r ( r , 5 . 0 , 8 . 0 ) ;
Desenhar ( q ) ;
p r i n t f ( ”%f \n” , Area ( c ) ) ;
p r i n t f ( ”%f \n” , Area ( r ) ) ;
p r i n t f ( ”%f \n” , Area ( q ) ) ;
r e t u r n 0 ;
} /∗ main ∗/
I As func¸o˜es Circulo, Retangulo e Quadrado devem construir e devolver
as representac¸o˜es dos valores correspondentes (construtores).
I A func¸a˜o main poderia estar num arquivo denominado main.c.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 305
Tipos abstratos de dados (cont.)
I A implementac¸a˜o de um TAD depende de va´rios fatores, mas deve
seguir sempre a sua especificac¸a˜o.
I Exemplo de declarac¸o˜es “naturais” para implementar o TAD Figura:
typedef enum { RETANGULO, CIRCULO , QUADRADO } FormaFigura ;
typedef s t r u c t {
FormaFigura forma ;
f l o a t posx , posy ;
union {
s t r u c t {
f l o a t a l t , l a r g ;
} l a d o s ;
f l o a t r a i o ;
} dados ;
} RegFigura , ∗ F i g u r a ;
Figura
forma posx posy
? ?
Retangulo
forma posx posy
0
alt larg
lados
Circulo
forma posx posy
1
raio
?
Quadrado
forma posx posy
2
alt larg
lados
I Deve-se notar a diferenc¸a entre os tipos Figura e Figura.
I Normalmente, estas declarac¸o˜es (e as seguintes) estariam num
arquivo figuras.c.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 306
Tipos abstratos de dados (cont.)
Declarac¸o˜es dos construtores:
F i g u r a R e ta n g u l o ( f l o a t a l t ,
f l o a t l a r g ) {
F i g u r a f =
m a l l o c ( s i z e o f ( R e g F i g u r a ) ) ;
f−>forma = RETANGULO;
f−>posx = 0 . 0 ;
f−>posy = 0 . 0 ;
f−>dados . l a d o s . a l t = a l t ;
f−>dados . l a d o s . l a r g = l a r g ;
r e t u r n f ;
} /∗ R et a n gu l o ∗/
F i g u r a C i r c u l o ( f l o a t r a i o ) {
F i g u r a f =
m a l l o c ( s i z e o f ( R e g F i g u r a ) ) ;
f−>forma = CIRCULO ;
f−>posx = 0 . 0 ;
f−>posy = 0 . 0 ;
f−>dados . r a i o = r a i o ;
r e t u r n f ;
} /∗ C i r c u l o ∗/
F i g u r a Quadrado ( f l o a t l a d o ) {
F i g u r a f =
R et a n gu l o ( lado , l a d o ) ;
f−>forma = QUADRADO;
r e t u r n f ;
} /∗ Quadrado ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 307
Tipos abstratos de dados (cont.)
Declarac¸o˜es das func¸o˜es:
f l o a t Area ( F i g u r a f i g ) {
F i g u r a f = f i g ;
switch ( f−>forma ) {
case RETANGULO:
case QUADRADO:
r e t u r n ( f−>dados . l a d o s . a l t )∗
( f−>dados . l a d o s . l a r g ) ;
case CIRCULO :
r e t u r n PI ∗( f−>dados . r a i o )∗
( f−>dados . r a i o ) ;
d e f a u l t :
e x i t ( 1 ) ; /∗ I m p o s s ı´ v e l ∗/
}
} /∗ Area ∗/
vo id T r a n s l a d a r ( F i g u r a f i g ,
f l o a t dx ,
f l o a t dy ) {
F i g u r a f = f i g ;
f−>posx += dx ;
f−>posy += dy ;
} /∗ T r a n s l a d a r ∗/
vo id Desenhar ( F i g u r a f ) {
/∗ Na˜o f o i implementada ∗/
} /∗ Desenhar ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 308
Tipos abstratos de dados (cont.)
I Nesta implementac¸a˜o do TAD Figura, a estrutura de dados que
implementa o tipo e as func¸o˜es sa˜o implementadas separadamente.
I E´ poss´ıvel mudar a implementac¸a˜o de maneira que as func¸o˜es passem
fazer parte da pro´pria estrutura de dados – uma caracter´ıstica de
objetos; neste caso sa˜o denominados me´todos.
I Nesta nova implementac¸a˜o do exemplo, por simplicidade, a te´cnica
sera´ aplicada somente a` func¸a˜o Area, mas poderia ser estendida a`s
outras func¸o˜es.
I Trata-se de uma nova implementac¸a˜o da mesma interface;
consequentemente os arquivos figuras.h (repetido abaixo) e
main.c permanecem iguais.
typedef vo id ∗ F i g u r a ;
F i g u r a R e ta n g u l o ( f l o a t a l t , f l o a t l a r g ) ;
F i g u r a C i r c u l o ( f l o a t r a i o ) ;
F i g u r a Quadrado ( f l o a t l a d o ) ;
f l o a t Area ( F i g u r a f i g ) ;
vo id T r a n s l a d a r ( F i g u r a f i g , f l o a t dx , f l o a t dy ) ;
vo id Desenhar ( F i g u r a f i g ) ;
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 309
Tipos abstratos de dados (cont.)
Declarac¸a˜o de Figura com um me´todo:
typedef f l o a t f u n c A r e a ( F i g u r a ) ; /∗ t i p o f un c¸ a˜ o ∗/
typedef enum { RETANGULO, CIRCULO , QUADRADO } FormaFigura ;
typedef s t r u c t {
FormaFigura forma ;
f l o a t posx , posy ;
f u n c A r e a ∗Area ; /∗ apontador para f u n c¸ a˜o ∗/
union {
s t r u c t { f l o a t a l t , l a r g ; } l a d o s ;
f l o a t r a i o ;
} dados ;
} RegFigura , ∗ F i g u r a ;
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 310
Tipos abstratos de dados (cont.)
Func¸o˜es do tipo funcArea:
f l o a t AreaRetangu lo ( F i g u r a f i g ) {
F i g u r a f = f i g ;
r e t u r n ( f−>dados . l a d o s . a l t )∗ ( f−>dados . l a d o s . l a r g ) ;
} /∗ AreaRetangu lo ∗/
f l o a t A r e a C i r c u l o ( F i g u r a f i g ) {
F i g u r a f = f i g ;
r e t u r n PI ∗( f−>dados . r a i o )∗ ( f−>dados . r a i o ) ;
} /∗ A r e a C i r c u l o ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 311
Tipos abstratos de dados (cont.)
Declarac¸o˜es dos construtores:
F i g u r a R e ta n g u l o ( f l o a t a l t ,
f l o a t l a r g ) {
F i g u r a f =
m a l l o c ( s i z e o f ( R e g F i g u r a ) ) ;
f−>forma = RETANGULO;
f−>posx = 0 . 0 ;
f−>posy = 0 . 0 ;
f−>Area = AreaRetangu lo ;
f−>dados . l a d o s . a l t = a l t ;
f−>dados . l a d o s . l a r g = l a r g ;
r e t u r n f ;
} /∗ R et a n gu l o ∗/
F i g u r a C i r c u l o ( f l o a t r a i o ) {
F i g u r a f =
m a l l o c ( s i z e o f ( R e g F i g u r a ) ) ;
f−>forma = CIRCULO ;
f−>posx = 0 . 0 ;
f−>posy = 0 . 0 ;
f−>Area = A r e a C i r c u l o ;
f−>dados . r a i o = r a i o ;
r e t u r n f ;
} /∗ C i r c u l o ∗/
F i g u r a Quadrado ( f l o a t l a d o ) {
F i g u r a f =
R e ta n g u l o ( lado , l a d o ) ;
f−>forma = QUADRADO;
r e t u r n f ;
} /∗ Quadrado ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 312
Tipos abstratos de dados (cont.)
Declarac¸o˜es das func¸o˜es:
f l o a t Area ( F i g u r a f i g ) {
r e t u r n ( ( F i g u r a ) f i g )−>Area ( f i g ) ;
}
vo id T r a n s l a d a r ( F i g u r a f i g , f l o a t dx , f l o a t dy ) {
F i g u r a f = f i g ;
f−>posx += dx ;
f−>posy += dy ;
} /∗ T r a n s l a d a r ∗/
vo id Desenhar ( F i g u r a f i g ) {
/∗ Na˜o f o i implementada ∗/
} /∗ Desenhar ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 313
Objetos
I O exemplo anterior demonstra que e´ poss´ıvel simular, dentro de
algumas limitac¸o˜es, a
implementac¸a˜o de objetos numa linguagem que
na˜o incorpora este conceito.
I Ha´ va´rios aspectos que ficam a cargo do pro´prio programador,
especialmente a consisteˆncia de tipos, fonte comum de erros.
I O exemplo anterior sera´ transformado de maneira a ilustrar a
implementac¸a˜o de objetos numa linguagem que possui este conceito.
I Sera´ usada uma linguagem fict´ıcia, uma extensa˜o simples de C.
I Na˜o sera˜o tratados va´rios aspectos como por exemplo polimorfismo,
visibilidade etc.
I Exemplo de hierarquia das classes:
Figura
C´ırculo Retaˆngulo
Quadrado
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 314
Objetos (cont.)
c l a s s F i g u r a {
f l o a t posx , posy ;
/∗ na˜o e x i s t e c o n s t r u t o r ∗/
f l o a t Area ( ) { } ;
void Desenhar ( ) { } ;
f l o a t T r a n s l a d a r ( f l o a t dx , dy ) {
t h i s . posx += dx ;
t h i s . posy += dy ;
}
} /∗ F i g u r a ∗/
posx posy
0
1
2
3
(Classe pai)
Area (Figura)
Desenhar (Figura)
Transladar (Figura)
Todos os objetos de uma classe apontam para a mesma tabela de
me´todos. Pode haver mais informac¸o˜es. Neste exemplo, todas as func¸o˜es
foram transformadas em me´todos.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 315
Objetos (cont.)
c l a s s R et an gu l o e x t e n d s F i g u r a {
f l o a t a l t , l a r g ;
R et an g u l o ( f l o a t a , f l o a t l ) {
t h i s . a l t = a ;
t h i s . l a r g = l ;
t h i s . posx = 0 . 0 ;
t h i s . posy = 0 . 0 ;
}
f l o a t Area ( ) {
return a l t ∗ l a r g ;
}
void Desenhar ( ) { . . . } ;
R et an g u l o G i r a r 9 0 ( ) {
return new R e ta ng u l o ( t h i s . l a r g , t h i s . a l t ) ;
}
} /∗ R et an g u l o ∗/
posx posy alt larg
4
0
1
2
3
Classe Figura
Area (Retangulo)
Desenhar (Retangulo)
Transladar (Figura)
Girar90 (Retangulo)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 316
Objetos (cont.)
c l a s s Quadrado e x t e n d s R et a ng u l o {
Quadrado ( f l o a t l ) {
s u p e r ( l , l ) ;
}
} /∗ R et an g u l o ∗/
posx posy alt larg
4
0
1
2
3
Classe Retaˆngulo
Area (Retangulo)
Desenhar (Retangulo)
Transladar (Figura)
Girar90 (Retangulo)
Somente o construtor e´ diferente da classe Retangulo.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 317
Objetos (cont.)
c l a s s C i r c u l o e x t e n d s F i g u r a {
f l o a t r a i o ;
C i r c u l o ( f l o a t r ) {
t h i s . posx = 0 . 0 ;
t h i s . posy = 0 . 0 ;
t h i s . r a i o = r ;
}
f l o a t Area ( ) {
return PI∗ s q r ( r a i o ) ;
}
void Desenhar ( ) { . . . } ;
void D u p l i c a r ( ) {
t h i s . r a i o = 2 . 0∗ t h i s . r a i o ;
}
} /∗ R et an g u l o ∗/
posx posy raio
4
0
1
2
3
Classe Figura
Area (Circulo)
Desenhar (Circulo)
Transladar (Figura)
Duplicar (Circulo)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 318
Objetos (cont.)
Representac¸a˜o de todas as classes:
0
1
2
3
(Classe pai)
Area (Figura)
Desenhar (Figura)
Transladar (Figura)
4
0
1
2
3
Area (Retangulo)
Desenhar (Retangulo)
Transladar (Figura)
Girar90 (Retangulo)
4
0
1
2
3
Area (Retangulo)
Desenhar (Retangulo)
Transladar (Figura)
Girar90 (Retangulo)
4
0
1
2
3
Area (Circulo)
Desenhar (Circulo)
Transladar (Figura)
Duplicar (Circulo)
Figura
Retangulo
Quadrado
Circulo
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 319
Objetos (cont.)
Exemplo de uso dos objetos:
i n t main ( ) {
F i g u r a f = new C i r c u l o ( 1 0 . 0 ) ;
R et a n gu l o r =
new R e t a ng u lo ( 1 0 . 0 , 2 0 . 0 ) ;
Quadrado q = new Quadrado ( 5 0 . 0 ) ;
C i r c u l o c = new C i r c u l o ( 3 0 . 0 ) ;
p r i n t f ( ”%f \n” , f . Area ( ) ) ;
p r i n t f ( ”%f \n” , r . Area ( ) ) ;
c . Desenhar ( ) ;
f = q ;
f . T r a n s l a d a r ( 5 . 0 , 8 . 0 ) ;
f . Desenhar ( ) ;
p r i n t f ( ”%f \n” , f . Area ( ) ) ;
/∗ comandos i n v a´ l i d o s ∗/
f . D u p l i c a r ( ) ;
f . G i r a r 9 0 ( ) ;
c . G i r a r 9 0 ( ) ;
c = r ;
q = f ;
} /∗ main ∗/
Os comandos inva´lidos seriam detectados pelo compilador.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Abstrac¸a˜o de Dados e Objetos 320
Algoritmos de ordenac¸a˜o
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 321
Generalidades
I Ordenac¸a˜o interna e externa
I Ordenac¸a˜o o´tima por comparac¸o˜es: O(n log n)
I Algoritmos por comparac¸a˜o:
I transposic¸a˜o (bubblesort, quicksort)
I inserc¸a˜o (inserc¸a˜o simples, shellsort)
I selec¸a˜o (selec¸a˜o simples, heapsort)
I intercalac¸a˜o (iterativo, recursivo)
I Outros algoritmos: distribuic¸a˜o (radix sort)
I Ordenac¸a˜o esta´vel: mante´m a ordem relativa dos registros de com
chaves iguais.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 322
Ordenac¸a˜o o´tima por comparac¸o˜es
A´rvore de decisa˜o para ordenar treˆs elementos x1, x2 e x3:
x1 ≤ x2
x2 ≤ x3
x1, x2, x3 x1 ≤ x3
x1, x3, x2 x3, x1, x2
x2 ≤ x3
x1 ≤ x3
x2, x1, x3 x2, x3, x1
x3, x2, x1
V F
V F
V F
V F
V F
I A a´rvore tem 3! = 6 folhas (permutac¸o˜es de 3 elementos).
I A altura da a´rvore e´ 3.
I Portanto, o nu´mero m´ınimo de comparac¸o˜es, no pior caso, e´ 3.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 323
Ordenac¸a˜o o´tima por comparac¸o˜es (cont.)
Caso geral de n elementos:
I A a´rvore de decisa˜o devera´ ter n! folhas (nu´mero de permutac¸o˜es de
n elementos).
I Uma a´rvore de altura h tem no ma´ximo 2h folhas.
I Deve-se ter, portanto: 2h ≥ n!
=⇒ h ≥ dlog2(n!)e
Pela aproximac¸a˜o de Stirling:
dlog2(n!)e = n log2 n− n/(ln 2) +
log2 n
2
+ O(1)
Para valores grandes de n, o primeiro termo e´ dominante:
dlog2(n!)e ≈ n log2 n
I O nu´mero m´ınimo de comparac¸o˜es, no pior caso, e´ O(n log2 n).
I Portanto, na˜o existe nenhum algoritmo de ordenac¸a˜o mais eficiente
que utiliza apenas comparac¸o˜es de elementos.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 324
Algoritmos: declarac¸o˜es comuns
typedef s t r u c t Vetor {
i n t n ;
i n t dados [ 1 ] ;
} Vetor , ∗ApVetor ;
vo id t r o c a ( i n t ∗x , i n t ∗y ) {
i n t t = ∗x ;
∗x = ∗y ;
∗y = t ;
} /∗ t r o c a ∗/
I Os algoritmos de ordenac¸a˜o sera˜o apresentados como func¸o˜es em
linguagem C que ordenam um vetor de dados que faz parte de uma
estrutura denominada Vetor.
I Nesta declarac¸a˜o, n denota o tamanho verdadeiro do vetor dados que
dependera´ do paraˆmetro passado a` func¸a˜o malloc quando o vetor for
alocado.
I Va´rios algoritmos fazem trocas de valores entre elementos do vetor
indicadas por chamadas da func¸a˜o troca.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 325
Algoritmo bubble sort
d
0 n-1
⇐= ij =⇒
vo id b u b b l e S o r t ( ApVetor v ) {
/∗Exemplo de t r a n s p o s i c¸ a˜ o ∗/
i n t n = v−>n , i , j ;
i n t ∗d = ( v−>dados ) ;
f o r ( i=n−1; i >0; i−−)
f o r ( j =0; j< i ; j ++)
i f ( d [ j ]>d [ j +1])
t r o c a (&d [ j ] ,& d [ j + 1 ] ) ;
} /∗ b u b b l e S o r t ∗/
I Os elementos entre i+ 1 e n−1 ja´ esta˜o ordenados.
I Os elementos d[j] (abaixo de i) sa˜o “empurrados” se necessa´ro; o
maior deles acaba em seu lugar final.
I Verifica-se facilmente
que o nu´mero de comparac¸o˜es executado por
este algoritmo e´ sempre (n2−n)/2 (da ordem de O(n2)).
I E´ um algoritmo esta´vel.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 326
Inserc¸a˜o simples
d
0 n-1
i =⇒
t
vo id i n s e r c a o ( ApVetor v ) {
i n t n = v−>n , i , j , t ;
i n t ∗d = ( v−>dados ) ;
f o r ( i =0; i<n−1; i ++) {
t = d [ i +1] ; j = i ;
whi le ( ( j>=0)&&(t<d [ j ] ) ) {
d [ j +1] = d [ j ] ; j−−;
}
d [ j +1] = t ;
}
} /∗ i n s e r c a o ∗/
I Os elementos entre 0 e i ja´ esta˜o ordenados.
I Os elementos menores do que d[i+1] sa˜o “empurrados” a` direita e
d[i+1] inserido no seu lugar.
I No pior caso, O(n2) comparac¸o˜es; no melhor caso, O(n).
I Um bom algoritmo se os dados ja´ esta˜o parcialmente ordenados.
I E´ um algoritmo esta´vel.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 327
Selec¸a˜o simples
d
0 n-1
i =⇒
p
vo id s e l e c a o ( ApVetor v ) {
i n t n = v−>n , i , j , p ;
i n t ∗d = ( v−>dados ) ;
f o r ( i =0; i<n−1; i ++) {
p = i ;
f o r ( j=i +1; j<n ; j ++)
i f ( d [ j ]<d [ p ] )
p = j ;
t r o c a (&d [ i ] ,& d [ p ] ) ;
}
} /∗ s e l e c a o ∗/
I Os elementos entre 0 e i−1 ja´ esta˜o ordenados.
I O elemento m´ınimo entre as posic¸o˜es i e n−1 (d[p]) troca de lugar
com o elemento d[i].
I O nu´mero de comparac¸o˜es e´ sempre da ordem de O(n2).
I E´ um algoritmo esta´vel.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 328
Algoritmo Quicksort
I Quicksort foi idealizado por C. A. R. Hoare em 1962.
I E´ um algoritmo recursivo que ordena segmentos do vetor dado.
I A ordenac¸a˜o do vetor inteiro e´ realizada atrave´s da chamada de uma
func¸a˜o auxiliar com argumentos que cobrem o vetor:
vo id q u i c k S o r t ( ApVetor v ) {
q u i c k S o r t A u x ( v , 0 , ( v−>n )−1);
} /∗ q u i c k S o r t ∗/
I A func¸a˜o auxiliar quickSortAux implementa de fato o algoritmo.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 329
Algoritmo Quicksort (cont.)
vo id q u i c k S o r t A u x ( ApVetor v , i n t esq , i n t d i r ) {
/∗ supo˜e esq<=d i r ∗/
i n t ∗d = ( v−>dados ) ;
i n t i = esq , j = d i r ;
i n t p i v o t = d [ ( i n t ) ( ( esq+d i r ) / 2 ) ] ;
/∗ p a r t i c i o n a ∗/
do {
whi le ( d [ i ]< p i v o t ) i ++;
whi le ( d [ j ]> p i v o t ) j−−;
i f ( i<=j ) {
t r o c a (&d [ i ] ,& d [ j ] ) ;
i ++; j−−;
}
} whi le ( i<=j ) ;
/∗ ordena ∗/
i f ( esq<j ) q u i c k S o r t A u x ( v , esq , j ) ;
i f ( d i r> i ) q u i c k S o r t A u x ( v , i , d i r ) ;
} /∗ q u i c k S o r t A u x ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 330
Algoritmo Quicksort (cont.)
do {
w h i l e ( d [ i ]<p i v o t ) i ++;
w h i l e ( d [ j ]>p i v o t ) j−−;
i f ( i<=j ) {
t r o c a (&d [ i ] ,& d [ j ] ) ;
i ++; j−−;
}
} w h i l e ( i<=j ) ;
i f ( esq<j ) q u i c k S o r t A u x ( v , esq , j ) ;
i f ( d i r>i ) q u i c k S o r t A u x ( v , i , d i r ) ;
I In´ıcio do particionamento:
d
0 n-1esq dir
i =⇒ ⇐= j
p (pivot)
I Situac¸a˜o gene´rica apo´s uma troca:
d
0 n-1esq diri j
≤p ≥p≥p ≤p
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 331
Algoritmo Quicksort (cont.)
do {
w h i l e ( d [ i ]<p i v o t ) i ++;
w h i l e ( d [ j ]>p i v o t ) j−−;
i f ( i<=j ) {
t r o c a (&d [ i ] ,& d [ j ] ) ;
i ++; j−−;
}
} w h i l e ( i<=j ) ;
i f ( esq<j ) q u i c k S o r t A u x ( v , esq , j ) ;
i f ( d i r>i ) q u i c k S o r t A u x ( v , i , d i r ) ;
I Situac¸a˜o apo´s uma troca:
d
0 n-1esq diri j
≤p ≥p≥p ≤p
I Situac¸a˜o quando termina o particionamento:
d
0 n-1esq dirij
≤p ≥p
Pode haver apenas um ou nenhum elemento entre j e i. Se houver,
ele e´ necessariamente igual ao pivoˆ e esta´ na sua posic¸a˜o final.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 332
Algoritmo Quicksort (cont.)
do {
w h i l e ( d [ i ]<p i v o t ) i ++;
w h i l e ( d [ j ]>p i v o t ) j−−;
i f ( i<=j ) {
t r o c a (&d [ i ] ,& d [ j ] ) ;
i ++; j−−;
}
} w h i l e ( i<=j ) ;
i f ( esq<j ) q u i c k S o r t A u x ( v , esq , j ) ;
i f ( d i r>i ) q u i c k S o r t A u x ( v , i , d i r ) ;
I Situac¸a˜o quando termina o particionamento:
d
0 n-1esq dirij
≤p ≥p
I Situac¸a˜o apo´s as chamadas recursivas – o segmento esta´ ordenado:
d
0 n-1esq dir
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 333
Algoritmo Quicksort (cont.)
I Escolha do pivoˆ:
I em princ´ıpio, o algoritmo funciona com qualquer valor do pivoˆ
I o ideal seria um pivoˆ que particiona o segmento em duas partes de
comprimentos iguais
I algumas implementac¸o˜es utilizam a me´dia de alguns poucos elementos
I na implementac¸a˜o aqui exibida foi usado o valor do elemento do meio
I Eficieˆncia:
I no pior caso o algoritmo realiza da ordem de O(n2) operac¸o˜es
I em me´dia e no melhor caso sa˜o O(n log n) operac¸o˜es
I na pra´tica sa˜o quase sempre O(n log n) operac¸o˜es
I e´ o algoritmo de ordenac¸a˜o interna mais utilizado e faz parte das
bibliotecas de va´rias linguagens (por exemplo, qsort em C)
I Estabilidade:
I sob a forma apresentada, o algoritmo na˜o e´ esta´vel
I exerc´ıcios:
I exibir um exemplo que demonstra a falta de estabilidade
I modificar o algoritmo para que seja esta´vel
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 334
Algoritmo Quicksort (cont.)
Exemplo de execuc¸a˜o do Quicksort:
(< e > delimitam o segmento corrente; ∗ marca o pivoˆ)
Vetor original:
07 49 73 58 30 72 44 78 23 09 40 65 92 42 87 03 27 29 40 12
------------------------------------------------------------------------------------------------------
Pivot: 09
< * >
07 03 73 58 30 72 44 78 23 09 40 65 92 42 87 49 27 29 40 12
i j
07 03 09 58 30 72 44 78 23 73 40 65 92 42 87 49 27 29 40 12
i j
07 03 09 58 30 72 44 78 23 73 40 65 92 42 87 49 27 29 40 12
j i
Pivot: 03
< * >
03 07 09 58 30 72 44 78 23 73 40 65 92 42 87 49 27 29 40 12
j i
Pivot: 07
<* >
03 07 09 58 30 72 44 78 23 73 40 65 92 42 87 49 27 29 40 12
j i
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 335
Algoritmo Quicksort (cont.)
Pivot: 65
< * >
03 07 09 58 30 12 44 78 23 73 40 65 92 42 87 49 27 29 40 72
i j
03 07 09 58 30 12 44 40 23 73 40 65 92 42 87 49 27 29 78 72
i j
03 07 09 58 30 12 44 40 23 29 40 65 92 42 87 49 27 73 78 72
i j
03 07 09 58 30 12 44 40 23 29 40 27 92 42 87 49 65 73 78 72
i j
03 07 09 58 30 12 44 40 23 29 40 27 49 42 87 92 65 73 78 72
i j
03 07 09 58 30 12 44 40 23 29 40 27 49 42 87 92 65 73 78 72
j i
Pivot: 23
< * >
03 07 09 23 30 12 44 40 58 29 40 27 49 42 87 92 65 73 78 72
i j
03 07 09 23 12 30 44 40 58 29 40 27 49 42 87 92 65 73 78 72
j i
Pivot: 23
<* >
03 07 09 12 23 30 44 40 58 29 40 27 49 42 87 92 65 73 78 72
j i
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 336
Algoritmo Quicksort (cont.)
Pivot: 29
< * >
03 07 09 12 23 27 44 40 58 29 40 30 49 42 87 92 65 73 78 72
i j
03 07 09 12 23 27 29 40 58 44 40 30 49 42 87 92 65 73 78 72
i j
03 07 09 12 23 27 29 40 58 44 40 30 49 42 87 92 65 73 78 72
j i
Pivot: 27
<* >
03 07 09 12 23 27 29 40 58 44 40 30 49 42 87 92 65 73 78 72
j i
Pivot: 40
< * >
03 07 09 12 23 27 29 30 58 44 40 40 49 42 87 92 65 73 78 72
i j
03 07 09 12 23 27 29 30 40 44 58 40 49 42 87 92 65 73 78 72
i=j
03 07 09 12
23 27 29 30 40 44 58 40 49 42 87 92 65 73 78 72
j i
Pivot: 30
<* >
03 07 09 12 23 27 29 30 40 44 58 40 49 42 87 92 65 73 78 72
j i
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 337
Algoritmo Quicksort (cont.)
Pivot: 40
< * >
03 07 09 12 23 27 29 30 40 40 58 44 49 42 87 92 65 73 78 72
i=j
03 07 09 12 23 27 29 30 40 40 58 44 49 42 87 92 65 73 78 72
j i
Pivot: 44
< * >
03 07 09 12 23 27 29 30 40 40 42 44 49 58 87 92 65 73 78 72
i j
03 07 09 12 23 27 29 30 40 40 42 44 49 58 87 92 65 73 78 72
j i
Pivot: 49
<* >
03 07 09 12 23 27 29 30 40 40 42 44 49 58 87 92 65 73 78 72
j i
Pivot: 65
< * >
03 07 09 12 23 27 29 30 40 40 42 44 49 58 65 92 87 73 78 72
i=j
03 07 09 12 23 27 29 30 40 40 42 44 49 58 65 92 87 73 78 72
j i
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 338
Algoritmo Quicksort (cont.)
Pivot: 73
< * >
03 07 09 12 23 27 29 30 40 40 42 44 49 58 65 72 87 73 78 92
i j
03 07 09 12 23 27 29 30 40 40 42 44 49 58 65 72 73 87 78 92
j i
Pivot: 72
<* >
03 07 09 12 23 27 29 30 40 40 42 44 49 58 65 72 73 87 78 92
j i
Pivot: 78
< * >
03 07 09 12 23 27 29 30 40 40 42 44 49 58 65 72 73 78 87 92
j i
Pivot: 87
<* >
03 07 09 12 23 27 29 30 40 40 42 44 49 58 65 72 73 78 87 92
j i
------------------------------------------------------------------------------------------------------
Resultado:
03 07 09 12 23 27 29 30 40 40 42 44 49 58 65 72 73 78 87 92
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 339
Intercalac¸a˜o iterativa (Mergesort)
I O algoritmo de intercalac¸a˜o iterativa foi provavelmente um dos
primeiros algoritmos de ordenac¸a˜o interna propostos: John von
Neumann (1945).
I O algoritmo consiste em va´rias passagens pelo vetor, intercalando
segmentos consecutivos de tamanhos 1, 2, 4, 8, ..., ate´ completar o
vetor.
I Utiliza um vetor auxiliar; os dois vetores sa˜o usados alternadamente
para guardar os resultados da intercalac¸a˜o.
I Se necessa´rio, ha´ um passo adicional para copiar os resultados do
vetor auxiliar para o original.
I O nu´mero de comparac¸o˜es deste algoritmo e´ da ordem de O(n log n)
(o´timo).
I O algoritmo e´ esta´vel.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 340
Intercalac¸a˜o iterativa (cont.)
v→d ...
0 n-1
w→d ...
v→d ...
w→d ...
v→d ...
• • •
Quando n na˜o e´ uma poteˆncia de 2, os u´ltimos segmentos de cada esta´gio
podem ficar mais curtos do que os outros.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 341
Intercalac¸a˜o iterativa (cont.)
vo id i n t e r c a l a I t e r a t i v o ( ApVetor v ) {
/∗ Ordena de 2 em 2 , de 4 em 4 , . . . , por i n t e r c a l a c¸ a˜ o ∗/
i n t n = v−>n ;
i n t td = 1 ; /∗ 1 , 2 , 4 , . . . ∗/
i n t esq , d i r , l d ;
i n t tamanho = s i z e o f ( Vetor )+ s i z e o f ( i n t )∗ ( n−1);
Boolean par = f a l s e ;
ApVetor w = ( ApVetor ) m a l l o c ( tamanho ) ;
w−>n = v−>n ;
(continua)
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 342
Intercalac¸a˜o iterativa (cont.)
whi le ( td<n ) {
esq = 0 ; par = ! par ;
do {
d i r = esq+td ; l d = d i r+td ;
i f ( d i r>=n ) { /∗ l a d o d i r e i t o v a z i o ∗/
d i r = n ; l d = n−1;
} e l s e i f ( ld>n )
l d = n ;
i f ( par ) i n t e r c a l a I t e r a t i v o A u x ( v , w, esq , d i r , l d ) ;
e l s e i n t e r c a l a I t e r a t i v o A u x (w, v , esq , d i r , l d ) ;
esq = d i r+td ;
} whi le ( esq<n ) ;
td = 2∗ td ;
}
i f ( par ) memcpy ( v , w, tamanho ) ;
f r e e (w ) ;
} /∗ i n t e r c a l a I t e r a t i v o ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 343
Intercalac¸a˜o iterativa (cont.)
vo id i n t e r c a l a I t e r a t i v o A u x ( ApVetor v , ApVetor w,
i n t esq , i n t d i r , i n t l d ) {
/∗ I n t e r c a l a v . dados [ esq : d i r −1] e
v . dados [ d i r : ld −1] em w . dados [ esq : ld −1] ∗/
i n t ∗dv = ( v−>dados ) , ∗dw = (w−>dados ) ;
i n t i = esq , j = d i r , k= esq ;
whi le ( ( i<d i r )&&( j<l d ) ) {
i f ( dv [ i ]<=dv [ j ] ) {
dw [ k ] = dv [ i ] ; i ++;
} e l s e {
dw [ k ] = dv [ j ] ; j ++;
}
k++;
}
whi le ( i<d i r ) { dw [ k ] = dv [ i ] ; i ++; k++; }
whi le ( j<l d ) { dw [ k ] = dv [ j ] ; j ++; k++; }
} /∗ i n t e r c a l a I t e r a t i v o A u x ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 344
Intercalac¸a˜o iterativa (cont.)
Exemplo de execuc¸a˜o:
Vetor original:
07 49 73 58 30 72 44 78 23 09 40 65 92 42 87 03 27 29 40 12
----------------------------------------------------------------------------------------------------
td=1:
| 07 49 | 58 73 | 30 72 | 44 78 | 09 23 | 40 65 | 42 92 | 03 87 | 27 29 | 12 40 |
td=2:
| 07 49 58 73 | 30 44 72 78 | 09 23 40 65 | 03 42 87 92 | 12 27 29 40 |
td=4:
| 07 30 44 49 58 72 73 78 | 03 09 23 40 42 65 87 92 | 12 27 29 40 |
td=8:
| 03 07 09 23 30 40 42 44 49 58 65 72 73 78 87 92 | 12 27 29 40 |
td=16:
| 03 07 09 12 23 27 29 30 40 40 42 44 49 58 65 72 73 78 87 92 |
----------------------------------------------------------------------------------------------------
Resultado:
03 07 09 12 23 27 29 30 40 40 42 44 49 58 65 72 73 78 87 92
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 345
Intercalac¸a˜o recursiva
I Passos do algoritmo:
I quebrar o vetor v dado em dois vetores v1 e v2, de tamanhos
aproximadamente iguais
I se o tamanho de v1 e´ maior que 1, ordena´-lo recursivamente
I se o tamanho de v2 e´ maior que 1, ordena´-lo recursivamente
I intercalar os vetores v1 e v2, deixando o resultado no vetor v original
I E´ fa´cil verificar que o nu´mero de comparac¸o˜es e´ da ordem de
O(n log n) (o´timo).
I Se implementado corretamente, o algoritmo e´ esta´vel.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 346
Intercalac¸a˜o recursiva (cont.)
v→d
0 n-1
v1→d v2→d
q
u
eb
ra
v1→d v2→d
rec
rec
v→d
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 347
Intercalac¸a˜o recursiva (cont.)
vo id i n t e r c a l a R e c u r s i v o ( ApVetor v ) {
i n t n = v−>n ;
i f ( n>1) {
i n t ∗dv = v−>dados ; ApVetor v1 , v2 ;
i n t i , nv1 = ( i n t ) ( n / 2 ) , nv2 = n−nv1 ;
v1 = ( ApVetor ) m a l l o c ( s i z e o f ( Vetor )+ s i z e o f ( i n t )∗ ( nv1 −1)) ;
v2 = ( ApVetor ) m a l l o c ( s i z e o f ( Vetor )+ s i z e o f ( i n t )∗ ( nv2 −1)) ;
v1−>n = nv1 ; v2−>n = nv2 ;
f o r ( i =0; i<nv1 ; i ++) ( v1−>dados ) [ i ] = dv [ i ] ;
f o r ( i =0; i<nv2 ; i ++) ( v2−>dados ) [ i ] = dv [ i+nv1 ] ;
i n t e r c a l a R e c u r s i v o ( v1 ) ; i n t e r c a l a R e c u r s i v o ( v2 ) ;
i n t e r c a l a R e c u r s i v o A u x ( v1 , v2 , v ) ;
f r e e ( v1 ) ; f r e e ( v2 ) ;
}
} /∗ i n t e r c a l a R e c u r s i v o ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 348
Intercalac¸a˜o recursiva (cont.)
vo id i n t e r c a l a R e c u r s i v o A u x ( ApVetor u , ApVetor v , ApVetor w) {
/∗ I n t e r c a l a os v e t o r e s u e v , d e i x a n d o o r e s u l t a d o em w . ∗/
i n t i = 0 , j = 0 , k ;
i n t nu = u−>n , nv = v−>n , n = nu+nv ;
i n t ∗du = ( u−>dados ) , ∗dv = ( v−>dados ) ,
∗dw = (w−>dados ) ;
f o r ( k=0; k<n ; k++) {
i f ( ( i<nu)&&( j<nv ) ) {
i f ( du [ i ]<=dv [ j ] ) { dw [ k ] = du [ i ] ; i ++; }
e l s e { dw [ k ] = dv [ j ] ; j ++; }
} e l s e {
i f ( i<nu ) { dw [ k ] = du [ i ] ; i ++; }
e l s e { dw [ k ] = dv [ j ] ; j ++; }
}
}
} /∗ i n t e r c a l a R e c u r s i v o A u x ∗/
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 349
Comparac¸a˜o dos algoritmos de ordenac¸a˜o interna
Tempos em milisegundos:
n Bubble Insercao Selecao Heapsort Quicksort Interc. Interc. Interc.
iter. recur.1 recur.2
-------------------------------------------------------------------------------------------------
16 (2^4) 0.005 0.003 0.003 0.004 0.003 0.005 0.005 0.004
32 (2^5) 0.009 0.004 0.007 0.004 0.005 0.005 0.010 0.006
64 (2^6) 0.031 0.009 0.016 0.009 0.009 0.014 0.021 0.010
128 (2^7) 0.106 0.030 0.050 0.017 0.016 0.016 0.053 0.018
256 (2^8) 0.404 0.106 0.179 0.039 0.035 0.033 0.107 0.046
512 (2^9) 1.685 0.450 0.674 0.085 0.074 0.072 0.218 0.083
1024 (2^10) 5.969 1.336 2.079 0.151 0.124 0.130 0.371 0.144
2048 (2^11) 21.301 5.282 8.136 0.322 0.268 0.279 0.805 0.302
4096 (2^12) 84.809 21.273 32.121 0.703 0.573 0.604 1.646 0.654
8192 (2^13) 338.462 84.498 127.803 1.510 1.233 1.290 3.570 1.404
16384 (2^14) 1351.672 340.743 514.325 3.279 2.605 2.721 7.442 2.968
32768 (2^15) 5390.648 1366.402 2054.017 7.133 5.520 5.769 15.563 6.189
65536 (2^16) 21565.843 5450.148 8213.796 15.489 11.546 12.192 32.772 13.167
131072 (2^17) 89281.419 21772.341 32872.943 33.404 24.359 26.042 68.350 27.769
I A u´ltima coluna corresponde a uma implementac¸a˜o otimizada do
algoritmo de intercalac¸a˜o recursivo que evita alocac¸a˜o e liberac¸a˜o de
espac¸o em cada chamada.
I Desafio: programar esta versa˜o.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 350
Ordenac¸a˜o externa: intercalac¸a˜o balanceada mu´ltipla
Passos do algoritmo, dado um arquivo f :
I i = 1
I Enquanto ha´ dados em f :
I Leia o ma´ximo nu´mero de registros de f que cabem na memo´ria num
vetor v.
I Ordene v usando um dos algoritmos de ordenac¸a˜o internos (por
exemplo, quicksort).
I Escreva o conteu´do de v em arquivo fi.
I i = i+ 1
I Fac¸a a intercalac¸a˜o mu´ltipla dos arquivos f1, f2, f3, ... .
Obs.: Se o nu´mero nf de arquivos fi e´ razoavelmente grande (mais que 5 a
10), pode ser usada uma fila de prioridades de tamanho nf .
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 351
Ordenac¸a˜o digital ou por distribuic¸a˜o (radix sort)
I O algoritmo baseia-se em procedimentos que eram utilizados para
ordenar carto˜es perfurados com ma´quinas classificadoras.
I A chave de cada registro de informac¸a˜o e´ tratada como uma cadeia
de caracteres (ou um nu´mero numa base conveniente b) de
comprimento m.
I Os registros sa˜o distribu´ıdos em b sequeˆncias, conforme o u´ltimo
caractere da chave (mantendo a ordem relativa original).
I As b sequeˆncias sa˜o (conceitualmente) concatenadas em ordem
crescente do caractere usado na distribuic¸a˜o.
I Os dois passos anteriores sa˜o repetidos para o penu´ltimo, o
antepenu´ltimo, etc, caractere da chave.
I Apo´s m distribuic¸o˜es, o vetor estara´ ordenado.
I O nu´mero de operac¸o˜es e´ no m´ınimo da ordem de O(nm),
dependendo da implementac¸a˜o.
I O algoritmo e´ esta´vel.
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 352
Ordenac¸a˜o digital (cont.)
Exemplo (m=2):
Vetor original:
07 49 73 58 30 72 44 78 23 09 40 65 92 42 87 03 27 29 40 12
Distribuic¸~ao pelo u´ltimo dı´gito:
0: 1: 2: 3: 4: 5: 6: 7: 8: 9:
30 40 40 | | 72 92 42 12 | 73 23 03 | 44 | 65 | | 07 87 27 | 58 78 | 49 09 29
Distribuic¸~ao pelo penu´ltimo dı´gito:
0: 1: 2: 3: 4: 5: 6: 7: 8: 9:
03 07 09 | 12 | 23 27 29 | 30 | 40 40 42 44 49 | 58 | 65 | 72 73 78 | 87 | 92
Resultado:
03 07 09 12 23 27 29 30 40 40 42 44 49 58 65 72 73 78 87 92
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o Algoritmos de ordenac¸a˜o 353
FIM
c©2011 T. Kowaltowski Estruturas de Dados e Te´cnicas de Programac¸a˜o FIM 354
	Introdução
	Bibliografia
	Noções de Análise de Algoritmos
	Execução de programas
	Estruturas ligadas
	Estruturas lineares
	Aplicações de pilhas
	Exemplos de recursão
	Exemplos de retrocesso
	Eliminação da recursão
	Recursão mútua: Análise sintática
	Árvores binárias
	Árvores binárias de busca
	Árvores do tipo B
	Filas de prioridade
	Árvores gerais
	Árvores digitais
	Listas generalizadas
	Espalhamento
	Compressão de textos
	Gerenciamento de memória
	Abstração de Dados e Objetos
	Algoritmos de ordenação
	FIM