Estruturas de Dados

Ordenação
 Ordenação (Sorting)
●
Em diversas aplicações devemos ordenar os
dados para operar de forma mais eficiente
●
Duas Abordagens:
– Inserir os elementos respeitando a ordenação
(Ordenação por Construção)
– Aplicar um algoritmo de ordenação em um
conjunto já criado
●
Os algoritmos de ordenação devem ser
eficientes em termos de tempo e espaço
 Ordenação de Vetores
●
Entrada: vetor com os elementos a serem
ordenados
●
Saída: o mesmo vetor com os seus elementos
na ordem especificada
●
Ordenação: pode ser aplicada a qualquer
dado com ordem bem definida
– Vetor com dados simples (int, float, etc)

Entrada: 4 2 5 1
+ = Saída: 1 2 4 5
Relação de Ordem: >
 Ordenação de Vetores (Cont.)
●
Ordenação: pode ser aplicada a qualquer
dado com ordem bem definida
– Vetor com dados complexos (structs)
●
Chave da ordenação escolhida entre os
campos
●
Em geral, ineficiente pois toda a estrutura
deve ser trocada
– Vetor de ponteiros para dados complexos
●
Troca da Ordem dos Elementos = Troca
de ponteiros
 Algoritmos de Ordenação
●
Algoritmos Iterativos de Ordenação:
– Ordenação Bolha (Bubble Sort)
– Ordenação por Inserção (Insertion Sort)
– etc.
●
Algoritmos Recursivos de Ordenação
(Abordagem Dividir para Conquistar):
– Ordenação Rápida (Quick Sort)
– Ordenação por Intercalação (Merge Sort)
– etc.
 Ordenação Bolha (Bubble Sort)
A idéia geral da ordenação bolha é colocar os
elementos "maiores" nos seus lugares corretos
4 2 5 1 1 2 4 5
Quando dois elementos estão fora de ordem, troque-os de posição
até que o i-ésimo elemento de maior valor do vetor seja levado para
as posições finais do vetor
Maior Elemento 2o. Maior Elemento 3o. Maior Elemento
4 2 5 1 2 4 1 5 2 1 4 5
2 4 5 1 2 4 1 5 1 2 4 5
2 4 5 1 2 1 4 5
2 4 1 5
 Ordenação Bolha
void bolha(int n, int *v){
int i, j, temp;
for(i=n-1; i>0; i--)
for(j=0; j<i; j++)
if(v[j]> v[j+1]){
temp = v[j]; // Troca
v[j] = v[j+1];
v[j+1] = temp;
}
}
i=3 i=2 i=1
j=0 4 2 5 1 2 4 1 5 2 1 4 5
j=1 2 4 5 1 2 4 1 5 1 2 4 5
j=2 2 4 5 1 2 1 4 5
2 4 1 5
 Ordenação Bolha (Versão II)
Quando o vetor já está ordenado em alguma passagem
void bolha(int n, int *v){
int i, j, temp, troca;
for(i=n-1; i>0; i--){
troca = 0;
for(j=0; j<i; j++)
if(v[j]> v[j+1]){
temp = v[j]; // Troca
v[j] = v[j+1];
v[j+1] = temp;
troca = 1;
}
if(troca==0)
return;
}
}
Ordenação Bolha pelo campo IRA
#include<stdio.h>
typedef struct aluno{
char nome[81];
float ira;
} Aluno;
#define MAX 10000
void inicializa(int n, Aluno **alunos);
void imprime(int n, Aluno **alunos, int i);
void bolhaIRA(int n, Aluno **alunos);
void imprime_todos(int n, Aluno **alunos);
void atualiza(int n, Aluno **alunos, int i);
void exclui(int n, Aluno **alunos, int i);
int main (void){
Aluno* alunos[MAX]; int i;
inicializa(MAX,alunos);
for(i=0;i<MAX;i++)
atualiza(MAX,alunos,i);
bolhaIRA(MAX,alunos);
imprime_todos(MAX,alunos);
for(i=0;i<MAX;i++)
exclui(MAX,alunos,i);
return 0; }
Ordenação Bolha pelo campo IRA
void bolhaIRA(int n, Aluno **alunos){
int i, j;
int troca = 0;
Aluno *tempAluno;
for(i=n-1; i>0; i--){
troca = 0;
for(j=0; j<i; j++)
if(alunos[j]->ira > alunos[j+1]->ira){
tempAluno = alunos[j];
alunos[j] = alunos[j+1];
alunos[j+1] = tempAluno;
troca = 1;
}
if(troca==0)
return;
}
}
 Complexidade
●
A complexidade de um algoritmo pode ser medida
pelo esforço computacional
– Número de Comparações, Atribuições etc.
●
No caso da ordenação do método bolha, a
complexidade pode ser estimada pelo número de
comparações (semelhante ao número de trocas)
– Na primeira passada: n-1 comparações
– Na segunda passada: n-2 comparações
– ...
●
T = (n-1)+ (n-2)+...+1 = n*(n-1)/2
●
O Algoritmo é no pior caso de Ordem Quadrática
O(n2) e no melhor caso Linear O(n)
●
Na prática, a ordenação bolha não é utilizada
Ordenação Rápida (Quick Sort)
●
Escolha um elemento arbitrário x, o pivô
●
Rearrume o vetor de tal forma que x fique na
posição correta v[i]
– x deve ocupar a posição i do vetor sse
todos os elementos v[0], … v[i-1] são menores que x e
todos os elementos v[i+1], …, v[n-1] são maiores que x

●
Chame recursivamente o algoritmo para
ordenar os (sub-)vetores v[0], … v[i-1] e v[i+1],
…, v[n-1]
●
Continue até que os vetores que devem ser
ordenados tenham 0 ou 1 elemento
 Ordenação Rápida (Quick Sort)
a=1
Rearrumação do vetor para o pivô de x=v[0] 4 2 5 1 b=3
do início para o final, compare x com v[1], a=2
v[2],… até encontrar v[a]>x 4 2 5 1 b=3
a=2
do final para o início, compare x com v[n-1], 4 2 5 1 b=3
v[n-2] … até encontrar v[b]<=x
a=3
troque v[a] e v[b] 4 2 1 5 b=2

continue para o final a partir de v[a+1] e para a=3

o início a partir de v[b-1]. Termine quando
4 2 1 5 b=2
os pontos de busca se encontram (b<a) 2<3

a posição correta de x=v[0] é a posição b e

v[0] e v[b] são trocados a=3
1 2 4 5 b=2
 Ordenação Rápida (Quick Sort)
a=1 Rearrumação do vetor para o pivô de x=v[0]
25 48 37 12 57 86 33 92 b=7
do início para o final, compare x com v[1],
a=1 v[2],… até encontrar v[a]>x
25 48 37 12 57 86 33 92 b=7
... do final para o início, compare x com v[n-1],
v[n-2] … até encontrar v[b]<=x
a=1
25 48 37 12 57 86 33 92 b=3 troque v[a] e v[b]
a=2
25 12 37 48 57 86 33 92 b=2 continue para o final a partir de v[a+1] e para
o início a partir de v[b-1]. Termine quando
a=2 os pontos de busca se encontram (b<a)
25 12 37 48 57 86 33 92 b=1
a posição correta de x=v[0] é a posição b e
a=2 v[0] e v[b] são trocados
12 25 37 48 57 86 33 92 b=1
Ordena Ordena
12 25 37 48 57 86 33 92
 Ordenação Rápida (Quick Sort)
void rapida(int n, int *v){ a=1
if(n>1){ 4 2 5 1 b=3
int x = v[0];
int a =1; int b = n-1; a=2
while(1){ 4 2 5 1 b=3
while(a<n && v[a] <=x) a++;
a=2
while(v[b]>x) b--;
if(a<b){
4 2 5 1 b=3
int temp = v[a];
a=3
v[a] = v[b];
v[b] = temp;
4 2 1 5 b=2
a++;b--;
a=3
}else
break;
4 2 1 5 b=2
} 2>3
v[0] = v[b];
v[b] = x; 1 2 4 5
rapida(b,v);
rapida(n-a,&v[a]);
} 1 2 4 5
}
 Complexidade
da Ordenação Rápida
Esforço computacional:
●
melhor caso:
– pivô representa o valor mediano do conjunto dos
elementos do vetor
– após mover o pivô em sua posição, restarão dois sub-
vetores para serem ordenados, ambos com o número
de elementos reduzido à metade, em relação ao vetor
original
– algoritmo é O(n log(n))
●
pior caso:
– pivô é o maior elemento e algoritmo recai em
ordenação bolha
●
caso médio:
– algoritmo é O(n log(n))
 Resumo
●
Ordenação Bolha (Bubble Sort)
– quando dois elementos estão fora de ordem, troque-os de
posição até que o i-ésimo elemento de maior valor do
vetor seja levado para as posições finais do vetor
– continue o processo até que todo o vetor esteja ordenado
– Complexidade no Pior Caso O(n2). Não é usado na prática

●
Ordenação Rápida (Quick sort)
– coloque um elemento arbitrário x, o pivô, em sua posição k
– chame recursivamente o algoritmo para ordenar os
(sub-)vetores v[0], … v[k-1] e v[k+1], …, v[n-1]
– continue até que os vetores que devem ser ordenados
tenham 0 ou 1 elemento
– Complexidade no Caso Médio O(n log(n)), porém no Pior
Caso O(n2)
 Referência
Introdução a Estruturas de Dados, Waldemar Celes,
Renato Cerqueira e José Lucas Rangel, Editora Campus,
2004.
Estruturas de Dados

Mergesort
 Mergesort
●
Algoritmo baseado na estratégia dividir para
conquistar, assim como o quicksort

●
Complexidade: O(n log n)

●
Requer memória adicional - O(n)
 Mergesort

O(log n)

Como o número de operações em cada nível da árvore é

O(n), o método Mergesort tem complexidade O(n log n)
 Mergesort

●
Fonte: [Link]
 Mergesort
void mergeSort(int *v, int n) {
mergeSort_ordena(v, 0, n-1);
}

void mergeSort_ordena(int *v, int esq, int dir) {

if (esq == dir)
return;
int meio = (esq + dir) / 2;
mergeSort_ordena(v, esq, meio);
mergeSort_ordena(v, meio+1, dir);
mergeSort_intercala(v, esq, meio, dir);
return;
}
●
Fonte: slides do Prof. Túlio Toffolo:
[Link]
14._mergesort.pdf
 Mergesort
void mergeSort_intercala(int *v, int esq, int meio, int dir){
int i, j, k;
int a_tam = meio-esq+1;
int b_tam = dir-meio;
int *a = (int*) malloc(sizeof(int) * a_tam);
int *b = (int*) malloc(sizeof(int) * b_tam);

for (i = 0; i < a_tam; i++) a[i] = v[i+esq];

for (i = 0; i < b_tam; i++) b[i] = v[i+meio+1];

for (i = 0, j = 0, k = esq; k <= dir; k++) {

if (i == a_tam) v[k] = b[j++];
else if (j == b_tam) v[k] = a[i++];
else if (a[i].chave < b[j].chave) v[k] = a[i++];
else v[k] = b[j++];
}
free(a); free(b); Fonte: slides do Prof. Túlio Toffolo:
●

[Link]
} edia/uploads/2013-1/bcc202/slides/
14._mergesort.pdf
Estruturas de Dados

Heapsort
 Heapsort
●
A estrutura de dados heap é um objeto
arranjo que pode ser visto como uma árvore
binária praticamente completa. Cada nó da
árvore corresponde a um elemento do
arranjo que armazena o valor no nó.

●
A árvore está completamente preenchida em
todos os níveis, exceto talvez no nível mais
baixo, que é preenchido a partir da esquerda
até certo ponto.
 Heapsort
●
Um arranjo A que representa um heap é um
objeto com dois atributos: comprimento[A],
que é o número de elementos do arranjo e
tamanho-do-heap[A], o número de elementos
no heap armazenado dentro do arranjo A.
●
Ou seja, embora A[1..comprimento[A]] possa
conter números válidos, nenhum elemento além
de A[tamanho-do-heap[A]] onde tamanho-do-
heap[A] ≤ comprimento[A], é um elemento do
heap.
 Heapsort
●
A raiz da árvore é A[1] e, dado o índice i de um
nó, os índices de seu pai PARENT(i), do filho
da esquerda LEFT(i) e do filho da direita
RIGHT(i) podem ser calculados de modo
simples:
●
Parent(i)
return i
●
Left(i) Right(i)
return 2i return 2i + 1
 Heapsort

16
16 14 10 8 7 9 3 2 4 1

14 10

8 7 9 3

2 4 1

Um heap máximo visto como uma árvore binária e um arranjo.

 Heapsort
●
Na maioria dos computadores, o
procedimento LEFT pode calcular 2i em uma
única instrução, simplesmente deslocando a
representação binária de i uma posição de
bit para a esquerda.

●
De modo semelhante, o procedimento right
pode calcular rapidamente 2i+1 deslocando
a representação binária de i uma posição de
bit para a esquerda e inserindo 1 como valor
de bit de baixa ordem.
 Heapsort
●
O procedimento PARENT pode calcular i/2
deslocando i uma posição de bit para a
direita.

●
Existem dois tipos de heaps binários: heaps
máximos e heaps mínimos. Em ambos os
tipos, os valores nos nós satisfazem a uma
propriedade de heap, cujos detalhes
específicos dependem do tipo de heap.
 Heapsort
●
Em um heap máximo, a propriedade de heap
máximo é que para todo nó i diferente da raiz

A[PARENT(i)] ≥ A[i] isto é, o valor de um nó

é no máximo o valor de seu pai.

●
Um heap mínimo é organizado de modo
oposto; a propriedade de heap mínimo é
que, para todo nó i diferente da raiz
A[PARENT(i)] ≤ A[i] o menor elemento em
um heap mínimo está na raiz.
 Heapsort
●
Visualizando um heap como uma árvore, definimos a
altura de um nó em um heap como o número de arestas
no caminho descendente simples mais longo desde o nó
até uma folha, e definimos a altura do heap como a
altura de sua raiz.
●
Tendo em vista que um heap de n elementos é baseado
em uma árvore binária completa, sua altura é O(lg n)
 MAX-HEAPIFY

Max-Heapify(A,i)
l ← Left(i)
r ← Right(i)
if l≤tamanho-do-heap[A] e A[l]>A[i]
then maior←l
else maior←i
if r≤tamanho-do-heap[A] e A[r]>A[maior]
then maior←r
if maior≠i
then trocar A[i]↔A[maior]
MAX-HEAPIFY(A,maior)
 Manutenção da propriedade
de heap
●
MAX-HEAPIFY é uma sub-rotina importante para a
manipulação de heaps máximos. Suas entradas são um
arranjo A e um índice i para o arranjo. Quando MAX-
HEAPIFY é chamado, supomos que as árvores binárias
com raízes em LEFT(i) e RIGHT(i) são heaps máximos,
mas que A[i] pode ser menor que seus filhos, violando
assim a propriedade de heap máximo. A função de MAX-
HEAPIFY é deixar que o valor em A[i] flutue para baixo
no heap máximo, de tal forma que a subárvore com raiz
no índice i se torne um heap máximo.
 MAX-HEAPIFY

16 16

4 10 14 10

14 7 9 3 4 7 9 3

2 8 1 2 8 1
 MAX-HEAPIFY

16
Em cada passo, o maior entre os
elementos A[i], A[LEFT], A[RIGHT]
é determinado e seu índice é
14 10 armazenado em maior.

8 7 9 3

2 4 1
 Construção de um Heap
●
Podemos usar o procedimento MAX-
HEAPIFY de baixo para cima, a fim de
converter um arranjo A[1..n], onde n=
comprimento[A] em um heap máximo.

BUILD-MAX-HEAP(A)
tamanho-do-heap[A]←comprimento[A]
for i← comprimento[A/2] downto 1
MAX-HEAPIFY(A,i)
 BUILD-MAX-HEAP
4 1 3 2 16 9 10 14 8 7

4
4

1 3
1 3

2 16 9 10
2 16 9 10

14 8 7
14 8 7
 BUILD-MAX-HEAP
4 4

1 3 1 10
3

14
2 16 9 10 14
2 16 9 10
3

14
2 8 7 14
2 8 7
 BUILD-MAX-HEAP

16
4

14
1 10
3
16
1 10
3

2
8 16
7 9 10
3
14
2 16
7 9 10
3

2 8
4 7
1
14
2 8 7
1
 Heap-Sort
O algoritmo heapsort começa usando
BUILD-MAX-HEAP para construir um heap
no arranjo de entrada A[1..n], onde n =
comprimento[A].

Tendo em vista que o elemento máximo do

arranjo está armazenado na raiz A[1], ele
pode ser colocado em sua posição final
correta, trocando-se esse elemento por A[n].
 Heap-Sort
HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i← comprimento[A] downto 2
trocar A[1]↔A[i]
tamanho-do-heap[A]←tamanho-do-heap[A]-1
MAX-HEAPIFY(A,1)
 Heap-Sort
16 14

14
1 10
3 1
8 10
3

2
8 16
7 9 10
3 2
4 16
7 9 10
3

2 8
4 7
1 2 8
1 16
 Heap-Sort

10 9

1
8 3
9 1
8 3

2
4 16
7 9
1 10
3 2
4 16
7 9
1 10
2

2 14 16 10 14 16
 Heap-Sort

7
8

1
4 3
1
7 3

2
1 16
2 8 9
2
4 16
2 9
1 9

10 14 16
10 14 16
 Heap-Sort
3
4

1
2 3
1
1
2 3

2
4 16
7 8 9
2
1 16
7 8 9

10 14 16
10 14 16
 Heap-Sort

1
2

1
2 3
1 3

2
4 16
7 8 9
2
4 16
7 8 9

10 14 16
10 14 16

1 2 3 4 7 8 9 10 14 16
Slides baseados no livro Algoritmos, Teoria e Prática,
de Cormen, T.H; Leiserson, C. E.; Rivest, R. L. e Stein,
C.
Estruturas de Dados

Filas de Prioridades
 Filas de Prioridades
●
O heapsort é um algoritmo excelente, mas
uma boa implementação de quicksort
normalmente o supera na prática.

●
Não obstante, a estrutura de dados de heap
pode ser empregada como uma fila de
prioridades eficiente.

●
Como ocorre no caso dos heaps, existem
dois tipos de filas de prioridades: máxima e
mínima.
 Filas de Prioridades
Uma fila de prioridades é uma estrutura de
dados para manutenção de um conjunto S de
elementos, cada qual com um valor associado
chamado chave. Uma fila de prioridade
máxima admite as operações a seguir:
●
INSERT(S,x)
●
MAXIMUM(S)
●
EXTRACT-MAX(S) remove e retorna o
elemento de S com a maior chave
●
INCREASE-KEY(S,x,k) aumenta o valor da
chave do elemento x para o novo valor k.
 Filas de Prioridades
HEAP-MAXIMUM(A)
return A[1]

HEAP-EXTRACT-MAX(A)
if tamanho-do-heap[A]<1
then erro 'heap underflow'
max←A[1]
A[1]←A[tamanho-do-heap[A]]
tamanho-do-heap[A]←tamanho-do-heap[A]-1
MAX-HEAPIFY(A,1)
return max
 Filas de Prioridades
HEAP-INCREASE-KEY(A,i,chave)
if chave < A[i]
then erro 'nova chave é menor que chave atual'
A[i]←chave
while i>1 e A[PARENT(i)]<A[i]
troca A[i]↔A[PARENT(i)]
i←PARENT(i)
 HEAP-INCREASE-KEY
16
16

14 10
14 10

8 7 9 3
8 7 9 3

2 15 1
2 4 1
 HEAP-INCREASE-KEY
16
16

15 10
14 10

14 7 9 3
15 7 9 3

2 8 1
2 8 1
 HEAP-INCREASE-KEY
O procedimento HEAP-INCREASE-KEY implementa a
operação INCREASE-KEY. O elemento da fila de
prioridades cuja chave deve ser aumentada é
identificado por um índice i no arranjo.

Primeiro, o procedimento atualiza a chave do elemento

A[i] para seu novo valor. Em seguida como o aumento
da chave de A[i] pode violar a propriedade de heap
máximo, o procedimento percorre um caminho desde
esse nó em direção à raiz, até encontrar um lugar
apropriado.
 MAX-HEAP-INSERT

MAX-HEAP-INSERT(A,chave)
tamanho-do-heap[A]←tamanho-do-heap[A] + 1
A[tamanho-do-heap[A]]←-∞
HEAP-INCREASE-KEY(A,tamanho-do-heap[A], chave)
 MAX-HEAP-INSERT
O procedimento MAX-HEAP-INSERT implementa
a operação INSERT. Ele toma como uma entrada
a chave do novo elemento a ser inserido no heap
máximo A. Primeiro, o procedimento expande o
heap máximo, adicionando à árvore uma nova
folha cuja chave é -∞. Em seguida, ele chama
HEAP-INCREASE-KEY para definir a chave
desse novo nó com seu valor correto e manter a
propriedade do heap máximo.
 MAX-HEAP-INSERT
O tempo de execução de MAX-HEAP-INSERT
sobre um heap de n elementos é O(lg n).

Em resumo, um heap pode admitir qualquer

operação de fila de prioridades em um conjunto de
tamanho n no tempo O(lg n).
Slides baseados no livro Algoritmos, Teoria e Prática,
de Cormen, T.H; Leiserson, C. E.; Rivest, R. L. e Stein,
C.
Tabelas de Dispersão
Estruturas de Dados
Tabelas de Dispersão
 Até o momento estudamos algoritmos de
busca com esforço computacional O(log n)
 Estudaremos agora estruturas de dados
conhecidas como tabelas de dispersão (hash
tables), que, se bem projetadas, podem ser
usadas para buscar um elemento em ordem
constante: O(1).
 O preço pago por essa eficiência é um maior
uso da memória.
Um exemplo
 Armazenar os dados referentes aos alunos
de uma disciplina.
 Cada aluno é identificado pelo seu número
de matrícula, que contém 7 dígitos. Ex:
9711234.
 Para permitir o acesso a qualquer aluno em
ordem constante, podemos usar o número
de matrícula do aluno como índice de um
vetor – vet. Assim, acessamos os dados do
aluno pela indexação do vetor – vet[mat].
Um exemplo
 O problema é que, nesse caso, o preço pago
para ter esse acesso rápido é muito grande.
 Vamos considerar que a informação
associada a cada aluno seja representada
pela estrutura abaixo:
struct aluno{
int mat;
char nome[81];
char email[41];
char turma;
};
typedef struct aluno Aluno;
Um exemplo
 Como a matrícula é composta por sete dígitos, o
vetor tem 10.000.000 elementos!
 Se cada estrutura ocupar 127 bytes, teremos
gasto [Link] bytes, ou seja, acima de 1
GB.
 Como na prática, cada turma tem 50 alunos,
precisamos de apenas 6.350 (127*50) bytes.
 Podemos amenizar o problema com um vetor de
ponteiros em vez de um vetor de estruturas.
 Apesar de menor, esse gasto de memória ainda é
proibitivo.
Ideia Central
 A ideia central por trás de uma tabela de
dispersão é identificar, na chave de busca, quais
são as partes significativas.
◦ Ex: 97 1 1234
 Dessa maneira, podemos usar um número de
matrícula parcial, de acordo com a dimensão que
queremos dar a nossa tabela (ou nosso vetor).
◦ Ex: Aluno* tab[100];
 Para acessar o nome de um aluno, podemos usar
como índice da tabela apenas os dois últimos
digitos da matrícula.
◦ Ex. vet[mat%100]->nome.
Ideia Central
 Dessa forma, o uso de memória excedente é
pequeno, e o acesso a um determinado aluno, a
partir do número de matrícula, continua
imediato.
 O problema é que provavelmente existirão dois
ou mais alunos da turma que apresentarão os
mesmos últimos dois dígitos no número de
matrícula.
 Dizemos que há uma colisão, pois alunos
diferentes são mapeados para o mesmo índice da
tabela.
 É preciso tratar o problema da colisão.
Ideia Central
 Existem diferentes métodos para tratar as
colisões em tabelas de dispersão.
 Vale salientar que não há como eliminar a
ocorrência de colisões.
 A meta é minimizar as colisões e usar um
método com o qual, mesmo com colisões,
saibamos identificar cada elemento da tabela
individualmente.
Função de dispersão
 A função de dispersão (função de hash) mapeia uma
chave de busca em um índice da tabela.
 No caso apresentado, adotamos como função de hash
a utilização dos dois últimos dígitos do número de
matrícula.
int hash (int mat){
return (mat%100);
}
 Podemos generalizar essa função para tabelas de
dispersão de dimensão N.
int hash (int mat){
return (mat%N);
}
Função de dispersão
 Uma função de hash deve, sempre que possível,
apresentar as seguintes propriedades:
◦ Ser eficientemente avaliada.
◦ Espalhar bem as chaves de busca.
 Além disso, para minimizar o número de colisões, a
dimensão da tabela deve guardar uma folga em
relação ao número de elementos efetivamente
armazenados.
◦ Como regra empírica, não devemos permitir uma taxa de
ocupação maior que 75%
◦ Uma taxa de 50% costuma trazer bons resultados
◦ Taxa menor que 25% pode representar gasto excessivo
de memória.
Tratamento de Colisão
 Existem diversas estratégias para tratar eventuais
colisões que surgem quando duas ou mais chaves de
busca são mapeadas para um mesmo índice da tabela
de hash.
 Em todas as estratégias, a tabela de dispersão em si é
representada por um vetor de ponteiros para a
estrutura que representa a informação a ser
armazenada, no caso Aluno. Podemos definir um tipo
que representa a tabela por:
#define N 127
Typedef Aluno* Hash[N]
Uso da posição consecutiva
livre
 Nesse estratégia, se a função de dispersão mapeia a
chave de busca para um índice já ocupado,
procuramos o próximo (usando incremento
circular) índice livre da tabela para armazenar o
novo elemento.
 Vale lembrar que uma tabela de dispersão nunca
terá todos os elementos preenchidos (já
mencionamos que uma ocupação acima de 75%
eleva o número de colisões, o que descaracteriza a
ideia central da estrutura).
 Portanto, podemos garantir que sempre existirá
uma posição livre na tabela.
Uso da posição consecutiva
livre
Aluno * hsh_busca(Hash tab, int mat)
{
int h=hash(mat);
while (tab[h] !=NULL){
if (tab[h]->mat==mat)
return tab[h];
h=(h+1)%N;
}
return NULL;
}
 Uso da posição consecutiva
livre
Aluno* hsh_insere(Hash tab, int mat, char *n, char *e, char t)
{
int h=hash(mat);
while (tab[h] !=NULL){
if (tab[h]->mat==mat)
break;
h=(h+1)%N;
}
if (tab[h]==NULL){
tab[h]=(Aluno*)malloc(sizeof(Aluno));
tab[h]->mat=mat;
}
strcpy(tab[h]->nome, n);
strcpy(tab[h]->email,e);
tab[h]->turma=t;
return tab[h];
}
 Uso de uma segunda função de
dispersão
 Para evitar a concentração de posições ocupadas na
tabela, essa segunda estratégia faz uma variação na forma
de procurar uma posição livre a fim de armazenar o
elemento que colidiu.
h’(x)= N - 2 - x%(N-2)
em que x representa a chave de busca e N é a dimensão
da tabela.
 Dois cuidados devem ser tomados na escolha dessa
segunda função de dispersão
◦ Ela nunca pode retornar zero.
◦ Segundo, de preferência, ela não deve retornar um número
divisor da dimensão da tabela. (N = nº primo)
Uso de uma segunda função de
dispersão
int hash2(int mat){
return N-2-mat%(N-2);
}

Aluno* hsh_busca(Hash tab, int mat){

int h=hash(mat);
int h2=hash2(mat);
while (tab[h] != NULL){
if (tab[h]->mat==mat)
return tab[h];
h=(h+h2)%N;
}
return NULL;
}
 Uso de listas encadeadas
 Uma estratégia diferente, mas ainda simples, consiste em
fazer com que cada elemento da tabela hash represente um
ponteiro para uma lista encadeada.
 Todos os elementos mapeados para um mesmo índice seriam
armazenados na lista encadeada.
struct aluno{
int mat;
char nome[81];
char turma;
char email[41];
struct aluno* prox;
}
typedef struct aluno Aluno;
Uso de listas encadeadas
Aluno* hsh_busca(Hash tab, int mat)
{
int h=hash(mat);
Aluno* a=tab[h];
while (a!=NULL){
if (a->mat==mat)
return a;
a=a->prox;
}
return NULL;
}
 Uso de listas encadeadas
Aluno* hsh_insere(Hash tab, int mat, char *n, char *e, char t) {
int h=hash(mat);
Aluno* a = tab[h];
while (a !=NULL){
if (a->mat==mat)
break;
a=a->prox; }
if (a==NULL){
a=(Aluno*)malloc(sizeof(Aluno));
a->mat=mat;
a->prox=tab[h];
tab[h]=a;
}
strcpy(a->nome, n);
strcpy(a->email,e);
a->turma=t;
return a;
}
Slides baseados no livro Introdução a Estruturas
de Dados, Waldemar Celes, Renato Cerqueira e
José Lucas Rangel, Editora Campus, 2004.
Árvore B (Parte I)
Estruturas de Dados
Engenharia de Computação

Baseado nos slides da Prof. Dra. Graça Nunes, do ICMC-USP

Problema
 Cenário até então
◦ Acesso a disco é caro (lento)
◦ Pesquisa binária é útil em índices ordenados...
◦ mas com índice grande que não cabe em
memória principal, pesquisa binária exige muitos
acessos a disco
◦ Exemplo: 15 itens podem requerer 4 acessos,
enquanto 1.000 itens podem requerer até 11
acessos
Problema
 Cenário
◦ Manter em disco um índice ordenado para busca
binária tem custo proibitivo
 Inserir ou eliminar, mantendo o arquivo ordenado custa
muito caro.
◦ Necessidade de método com inserção e
eliminação com apenas efeitos locais, isto é, que
não exija a reorganização total do índice
Solução: árvores binárias de
busca?
Solução: árvores binárias de
busca?
 Representação da árvore no
arquivo

 Registros (tam. fixo) são mantidos em arquivo, e ponteiros

(esq e dir) indicam onde estão os registros filhos.
Quais as vantagens de se
utilizar ABB’s?
 Ordem lógica dos registros  ordem física
no arquivo
◦ Ordem lógica: dada por ponteiros esq e dir
◦ Registros não precisam estar fisicamente
ordenados
 Inserção de uma nova chave no arquivo
◦ É necessário saber onde inserir
◦ Busca pelo registro é necessária, mas
reorganização do arquivo não
Inserção da chave LV
 Problema: desbalanceamento
 Inserção das chaves NP MB TM LA UF ND TS NK

Situação
indesejável:
inserção em
ordem
alfabética
 Solução por árvores AVL

 Para todo nó: as alturas de suas duas sub-­árvores

diferem de, no máximo, 1.
Solução por árvores AVL
Solução por árvores AVL
 Árvores binárias de busca balanceadas
garantem eficiência
◦ AVLs
◦ Busca no pior caso
◦ Arvore binária perfeitamente balanceada: altura
da árvore, ou seja, log2(N+1)
 Exemplo: com 1.000.000 chaves
◦ Árvore binária perfeitamente balanceada: busca
em até 20 níveis
Solução por árvores AVL
 Problema
◦ .. Se chaves em memória secundária, ainda
há muitos acessos!
 .. 20 são inaceitáveis!
 .. Até agora...
◦ .. Árvores binárias de busca dispensam
ordenação dos registros
◦ .. Mas número excessivo de acessos ..
Solução por Árvores Binárias
Paginadas (Paged Binary Trees)
 Solução
◦ Paginação
 A busca (seek) por uma posição específica do
disco é muito lenta
 Mas, uma vez na posição, pode se ler uma
grande quantidade de registros sequencialmente
a um custo relativamente pequeno
Solução por Árvores Binárias
Paginadas (Paged Binary Trees)
 Noção de página em sistemas
paginados
◦ Feito o seek, todos os registros de uma
mesma "página" do arquivo são lidos
◦ Esta página pode conter um número
grande de registros
 Se o próximo registro a ser recuperado estiver
na mesma página já lida, evita-­se um novo
acesso ao disco
 Solução por Árvores Binárias
Paginadas (Paged Binary Trees)

8 páginas
filhas

7 registros por página (por seek);; Nível da árvore 2 e ordem 8

= (8+1)*7 registros, se completa
Solução por Árvores Binárias
Paginadas (Paged Binary Trees)
Qualquer um dos 63 registros pode ser acessado em, no
máximo, 2 acessos!
 Solução por Árvores Binárias
Paginadas (Paged Binary Trees)
• Se a árvore é estendida com um nível de paginação
adicional, adicionamos 64 novas páginas
• Podemos encontrar qualquer uma das 511 (64 x 7 + 63) chaves
fazendo apenas 3 seeks

8 páginas
filhas

82 páginas
filhas
Eficiência da árvore paginada

 Mais realisticamente....supondo que

◦ Cada página de uma árvore ocupa 8KB e
armazena 511 chaves
◦ Cada página contém uma árvore completa
perfeitamente balanceada com 9 níveis
(=log2 512)
◦ A árvore de 3 níveis pode armazenar
134.217.727 chaves, ou seja,
(511+(512*511)+(512*512*511))
Eficiência da árvore paginada
 Eficiência na busca
◦ ABB completa, perfeitamente balanceada:
log2 (N+1)
◦ Versão paginada: logk+1 (N+1)
◦ em que N é o número total de chaves, e k é
o número de chaves armazenadas em uma
página
 ABB (perfeitamente balanceada):
log2(134.217.727) = 27 acessos
 Versão paginada : log511+1(134.217.727) = 3
acessos
Solução por Árvores Binárias
Paginadas (Paged Binary Trees)
 Preços a pagar
◦ Menos seeks, mas maior tempo na
transmissão de dados
◦ Necessário manter a organização da
árvore
◦ Pense como seria a construção da árvore
Solução por Árvores Binárias
Paginadas (Paged Binary Trees)
 Preços a pagar
◦ Menos seeks, mas maior tempo na
transmissão de dados
◦ Necessário manter a organização da
árvore
◦ Pense como seria a construção da árvore
Construção Top-­Down de ABB
Paginadas
 Se tivermos todas as chaves a
priori:
◦ Ordenar as chaves e inserir de forma a manter
balanceada (mediana será a raiz, etc.)
 Se a construção for dinâmica ..
chaves são inseridas em ordem
aleatória
◦ Conforme inserimos, podemos manter a ABB
de cada página balanceada (ou seja, uma AVL),
rotacionando-­a conforme necessário
Exemplo
 Assuma:
◦ uma ABB paginada com páginas de até 3
chaves por página
◦ a seguinte sequência de chaves a inserir:

C S DTAM PI B W N G U R K E H O L
JYQZFXV
Exemplo
 Exemplo
 Observe:
◦ A construção top-­down faz com que as primeiras
chaves fiquem na página-­raiz.
◦ No exemplo, C e D (consecutivas e no início do
alfabeto) não são boas escolhas para a raiz, pois
fatalmente fazem a árvore tender à direita.
 E se rotacionássemos as páginas (como
fazemos com os nós)?
◦ Tente formular um algoritmo para isso
 Muito complexo!
 Problemas a resolver
1. Como garantir que as chaves da raiz
sejam boas separadoras, tal que
dividam o conjunto mais ou menos ao
meio?
2. Como evitar agrupamento de certas
chaves (como C, D e S) na página raiz?
3. Como garantir que cada página
contenha um certo número mínimo de
chaves?
A invenção das árvores-­B
 Arvores-­B são uma generalização da
ideia de ABB paginada
◦ Não são binárias
◦ Conteúdo de uma página não é mantido como
uma árvore
◦ A construção é bottom-­up
 Um pouco de história
◦ 1972: Bayer and McGreight publicam o artigo
Organization and Maintenance of Large Ordered
Indexes
◦ 1979: árvores-­B viram praticamente padrão em
sistemas de arquivos de propósito geral
Árvore-­B
 Características
◦ Completamente balanceadas
◦ criação bottom-­up (em disco)
◦ nós folhas  nó raiz
 Inovação
◦ Não é necessário construir a árvore a partir do
nó raiz, como é feito para árvores em
memória principal e para as árvores
anteriores
Construção Bottom-up
 Consequências
◦ Chaves ‘’erradas’’ não são mais alocadas no
nó raiz
 Elimina as questões em aberto de chaves
separadoras e de chaves extremas
 Não é necessário tratar o problema de
desbalanceamento
Árvore B (Parte II)
Estruturas de Dados
Engenharia de Computação

Baseado em materiais do Prof. Gustavo Nonato, do ICMC-USP

Árvore B
• As árvores B são árvores balanceadas
projetadas para trabalhar com dispositivos de
armazenamento secundário como discos
magnéticos.
• Elas visam otimizar as operações de entrada e
saída nos dispositivos. O tempo de acesso às
informações em um disco é prejudicado
principalmente pelo tempo de posicionamento do
braço de leitura.
• Uma vez que o braço esteja posicionado no local
correto, a leitura pode ser feita de forma bastante
rápida. Desta forma, devemos minimizar o
número de acessos ao disco.
 Árvore B
• Diferente das árvores binárias, cada nó em uma
árvore B pode ter muitos filhos, isto é, o grau de
um nó pode ser muito grande.
• Definição: Uma árvore B possui as seguintes
propriedades:
• Todo o nó X possui os seguintes campos:
• n, o número de chaves armazenadas em X;
• as n chaves k1, k2...kn são armazenadas em ordem
crescente;
• folha, que indica se X é uma folha ou um nó
interno.
 Árvore B
• Definição: Uma árvore B possui as seguintes
propriedades:
• Se X é um nó interno então ele possui n+1
ponteiros f1, f2...fn+1 para seus filhos
• Todas as folhas da árvore estão na mesma altura
(que é a altura da árvore).
• Existe um número máximo e mínimo de filhos em
um nó. Este número pode ser descrito em termos
de um inteiro fixo t maior ou igual a 2 chamado
grau mínimo.
• t é a ordem da árvore, embora a definição de
ordem não seja única entre os autores.
 Árvore B
• Definição: Uma árvore B possui as seguintes
propriedades:
• Todo o nó diferente da raiz deve possuir pelo
menos t-1 chaves. Todo o nó interno diferente da
raiz deve possuir pelo menos t filhos. Se a árvore
não é vazia, então a raiz possui pelo menos uma
chave.
• Todo o nó pode conter no máximo 2t - 1 chaves.
Logo um nó interno pode ter no máximo 2t filhos.
Dizemos que um nó é cheio se ele contém 2t - 1
chaves.
Árvore B
Árvore B
• Estrutura de um nó
Árvore B
Árvore t = 2
 Busca em Árvore B
• A busca em uma árvore B é uma função parecida
com a de busca em uma árvore de busca binária,
exceto o fato de que se deve decidir entre vários
caminhos.
• Se a chave não for encontrada no nó em questão,
continua-se a busca nos filhos deste nó, realizando-
se novamente a busca binária.
• Caso o nó não esteja contido na árvore a busca
terminará ao encontrar um ponteiro igual a NULL, ou
de forma equivalente, verificando-se que o nó é uma
folha.
• A busca completa pode ser realizada em tempo
O(lg(t)logt(n)).
Busca em Árvore B
 Inserção em Árvore B
• Para inserir um novo elemento em uma árvore B,
basta localizar o nó folha X onde o novo
elemento deva ser inserido.
• Se o nó X estiver cheio, será necessário realizar
uma subdivisão de nós que consiste em passar o
elemento mediano de X para seu pai e subdividir
X em dois novos nós com t - 1 elementos e
depois inserir a nova chave.
Inserção em Árvore B
 Inserção em Árvore B
• Se o pai de X também estiver cheio, repete-se
recursivamente a subdivisão acima para o pai de
X. No pior caso terá que aumentar a altura da
árvore B para poder inserir o novo elemento.
• Note que diferentemente das árvores binárias, as
árvores B crescem para cima
Inserção em Árvore B
Árvore B
com t=3.
 Remoção em Árvore B
• A remoção de um elemento de uma árvore B pode
ser dividida em dois casos:
1. O elemento que será removido está em uma folha
2. O elemento que será removido está em um nó interno.
• Se o elemento estiver sendo removido de um nó
não-folha, seu sucessor, que deve estar em uma
folha, será movido para a posição eliminada e o
processo de eliminação procede como se o
elemento sucessor fosse removido do nó-folha.
• Quando um elemento for removido de uma folha X
e o número de elementos no nó folha diminui para
menos que t – 1, deve-se reorganizar a árvore B
 Remoção em Árvore B
• Quando um elemento for removido de uma folha X
e o número de elementos no nó folha diminui para
menos que t - 1, deve-se reorganizar a árvore B. A
solução mais simples é analisarmos os irmãos da
direita ou esquerda de X.
• Se um dos irmãos (da direita ou esquerda) de X
possui mais de t - 1 elementos, a chave k do pai
que separa os irmãos pode ser incluída no nó X e
a última ou primeira chave do irmão (última se o
irmão for da esquerda e primeira se o irmão for da
direita) pode ser inserida no pai no lugar de k.
Remoção em Árvore B
 Remoção em Árvore B
• Se os dois irmãos de X contiverem exatamente t -
1 elementos (ocupação mínima), nenhum
elemento poderá ser emprestado. Neste caso, o
nó X e um de seus irmãos são concatenados em
um único nó que também contém a chave
separadora do pai.
Remoção em Árvore B
 Remoção em Árvore B
• Se o pai também contiver apenas t - 1 elementos,
deve-se considerar os irmãos do pai como no
caso anterior e proceder recursivamente.
• No pior caso, quando todos os ancestrais de um
nó e seus irmãos contiverem exatamente t - 1
elementos, uma chave será tomada da raiz e no
caso da raiz possuir apenas um elemento a árvore
B sofrerá uma redução de altura.
Remoção em Árvore B
Árvore B
com t=3.