Algoritmos e Estruturas de Dados

Prévia do material em texto

PDF gerado usando o pacote de ferramentas em código aberto mwlib. Veja http://code.pediapress.com/ para mais informações.
PDF generated at: Fri, 06 Dec 2013 10:29:45 UTC
Algoritmos e Estruturas de
Dados
Conteúdo
Páginas
Objetivo 1
O que é um Algoritmo? 1
Para que servem os algoritmos? 2
Sintaxe 2
Recursividade 4
Algoritmos de Ordenação 5
Selection e Insertion 9
O que são estruturas de dados? 13
Abstração de Dados 14
Vetores e Matrizes 15
Estruturas 21
Listas 22
Pilhas 23
Filas 26
Lista encadeada 27
Tabela de Hash 29
Árvore 31
Árvores Binárias 33
Árvores AVL 35
Árvores Rubro-Negras 37
Árvores B 39
Estruturas para classes de equivalência 42
Referências
Fontes e Editores da Página 44
Fontes, Licenças e Editores da Imagem 45
Licenças das páginas
Licença 46
Objetivo 1
Objetivo
Este wikilivro tem a pretensão de tratar com aprofundamento sobre estruturas de dados e suas aplicações em
algoritmos computacionais.
Esta página é somente um esboço.
Ampliando-a você ajudará a melhorar o Wikilivros.
O que é um Algoritmo?
1.1 O que é um Algoritmo?
Algoritmo
Um algoritmo é uma sequência finita e não ambígua de instruções computáveis para solucionar um problema.
Um algoritmo consiste em uma expressão textual das etapas da resolução de algum problema, seja ele computacional
ou não. Um exemplo clássico de algoritmo não-computacional é uma receita de bolo. Outros exemplos são
instruções de montagem de um brinquedo ou equipamento, instruções para ir de um lugar a outro e receitas médicas.
Imagine a fabricação de um bolo como sendo o problema. A receita desse bolo seria o algoritmo. Os ingredientes
seriam os dados de entrada. Os recipientes utilizados para fazer o bolo são as variáveis envolvidas no processo. O
"modo de fazer" consiste na descrição dos passos a serem utilizados para obter a solução do problema.
Em computação, podemos definir um algoritmo como sendo uma forma genérica de se representar procedimentos
computacionais que, quando executados, levam à solução de uma classe de problemas de natureza semelhante.
Esta página é um esboço de informática. Ampliando-a você ajudará a melhorar o Wikilivros.
Para que servem os algoritmos? 2
Para que servem os algoritmos?
Os algoritmos são soluções para problemas computacionais, isto é, problemas que podem ser resolvidos utilizando
um ou mais computadores. Nesse sentido, as soluções de problemas computacionais são apresentadas por meio de
algoritmos, que servem para estruturar ou ordenar determinadas etapas de um processo.
Esta página é um esboço de informática. Ampliando-a você ajudará a melhorar o Wikilivros.
Sintaxe
1.3 Sintaxe
Para facilitar o entendimento dos algoritmos e, conseqüentemente, sua tradução para as diversas linguagens de
programação existentes atualmente, adotaremos uma sintaxe de descrição padrão.
Nossa sintaxe será baseada na linguagem Pascal.
• Hierarquias - As hierarquias serão denotadas pelas identações entre as linhas. Ou seja, terão a mesma ordem
hierárquica todas as instruções que estiverem a uma mesma distância da margem esquerda da tela.
• Variáveis - Não serão declaradas variáveis ou mesmo tipos de variáveis. Todas as variáveis utilizadas aparecerão
ao longo do código e serão representadas por conjuntos de letras e números.
•• ponteiros
Ponteiros receberão uma representação diferenciada, para destacá-los das variáveis comuns:
^pt - variável do tipo ponteiro (armazena um endereço de memória).
[^pt] - acesso ao conteúdo no endereço que ^pt armazena.
$var - endereço da variável var.
•• Operadores
•• atribuição
var <- 12
•• matemáticos
OPERAÇÃO OPERADOR
adição +
subtração -
multiplicação *
divisão /
módulo MOD
quociente DIV
•• lógicos
OPERAÇÃO OPERADOR
e (and) E
ou (or) OU
Sintaxe 3
não (not) ~
•• relacionais
OPERAÇÃO OPERADOR
maior >
maior ou igual >=
menor <
menor ou igual <=
igual =
diferente ~=
• Condicionais (ou blocos de seleção) - As possíveis formas de uma estrutura condicional serão:
SE (...) ENTÃO
 (...)
SENÃO SE (...) ENTÃO
 (...)
SENÃO
 (...)
SELECIONE (...) DENTRE
 [valores]:
 (...)
 SAIA
• Laços - A estrutura dos laços de repetição serão:
ENQUANTO (...) FAÇA
 (...)
PARA var <- 1,2,...,20 FAÇA
 (...)
FAÇA
 (...)
ATÉ (...)
•• Valores de retorno
Sempre que um algoritmo especificar um campo SAÍDA em sua definição (ver a seguir), em seu corpo deverá ocorrer
ao menos uma instrução RETORNA. Os algoritmos definirão os valores a serem retornados como a seguir:
RETORNE a
Estrutura dos Algoritmos
Sempre que um novo algoritmo seguir, será da seguinte forma:
ALGORITMO: NomeAlgoritmo(i, nome, ^pt)
ENTRADA: inteiro i, frase nome
[SAÍDA: quantidade de letras de nome]
[REQUISITOS: nome deve iniciar por caractere alfabético]
--------------------------------------------------------
Sintaxe 4
 (instruções)
Os campos entre colchetes são utilizados somente quando necessário.
Recursividade
Recursão é um método de programação no qual uma função pode chamar a si mesma. O termo é usado de maneira
mais geral para descrever o processo de repetição de um objeto de um jeito similar ao que já fora mostrado. Muitos
problemas em computação tem a propriedade de que cada instância sua contém uma instância menor do mesmo
problema.
A chamada à função proveniente de um meio externo a ela é denominada chamada externa e cada uma das
chamadas internas a si mesma é denominada chamada recursiva.
Um método comum de simplificação é dividir o problema em subproblemas do mesmo tipo. Como técnica de
programação, este método é conhecido como dividir e conquistar e é a chave para a construção de muitos algoritmos
importantes, bem como uma parte fundamental da programação dinâmica.
A recursão na programação é bem exemplificada quando uma função é definida em termos de si mesma. Um
exemplo da aplicação da recursão são os parsers (analisadores gramaticais) para linguagens de programação. Uma
grande vantagem da recursão é que um conjunto infinito de sentenças possíveis, designs ou outros dados podem ser
definidos, analisados ou produzidos por um programa de computador finito.
Relações de recorrência são equações que definem uma ou mais seqüências recursivamente. Alguns tipos específicos
de relações de recorrência podem ser “resolvidos” para que se obtenha uma definição não-recursiva.
Um exemplo clássico de recursão é a definição do cálculo do fatorial de um número, dada aqui no algoritmo a
seguir:
ALGORITMO: Fatorial(n) 
ENTRADA: inteiro n
SAÍDA: fatorial de n
REQUISITOS: n >= 0
SE n <= 1
 RETORNE 1
SENÃO
 RETORNE n * Fatorial(n-1)
A função chama a si mesma recursivamente em uma versão menor da entrada (n - 1) e multiplica o resultado da
chamada por n, até que alcance o caso base, de modo análogo à definição matemática de fatorial.
Como pode-se notar pela primeira condição, todo processo recursivo necessita de uma condição de parada para
evitar um loop infinito. Neste caso, quando a função fatorial atinge o valor menor ou igual a 1 ele passa a retornar o
valor de volta para a função.
No entanto, a recursão não é sempre a melhor opção. Como pode-se ver na questão acima, um laço comum resolve o
problema iterativamente. Desta forma, quando o problema é pequeno tente resolvê-lo diretamente e utilizar a
recursão apenas quando o problema for grande, consumindo tempo demais em um laço.
Recursividade 5
Resumo
• Uma recursão em computação é uma função que chama a si mesma.
• Para evitar um loop infinito é necessário estabelecer uma condição de parada.
Bibliografia
•• Recursividade na Wikipédia
• Recursão e algoritmos recursivos-Paulo Feofiloff[1]
Referências
[1] http:/ / www. ime. usp. br/ ~pf/ algoritmos/ aulas/ recu. html
Algoritmos de Ordenação
Ordenação é o ato de se colocar os elementos de uma sequência de informações, ou dados, em uma relação de
ordem predefinida. O termo técnico em inglês para ordenação é sorting, cuja tradução literal é "classificação".
Dado uma seqüencia de n dados:
O problema de ordenação é uma permutação dessa seqüencia:
tal que:
para alguma relação de ordem.
Algumas ordens são facilmente definidas. Por exemplo, a ordem numérica, ou a ordem alfabética—crescentes ou
decrescentes. Contudo, existem ordens, especialmente de dados compostos, que podem ser não triviais de se
estabelecer.
Um algoritmo que ordena uma conjunto, geralmente representada num vetor, é chamado de algoritmo de ordenação.
Algoritmo de ordenação em ciência da computação é um algoritmo que coloca os elementos de uma dada
sequência em uma certa ordem—em outras palavras, efetua sua ordenação completa ou parcial. As ordens mais
usadas são a numérica e a lexicográfica.Existem várias razões para se ordenar uma sequência. Uma delas é a
possibilidade se acessar seus dados de modo mais eficiente.
Entre os mais importantes, podemos citar bubble sort (ou ordenação por flutuação), heap sort (ou ordenação por
heap), insertion sort (ou ordenação por inserção), merge sort (ou ordenação por mistura) e o quicksort. Existem
diversos outros, que o aluno pode com dedicação pesquisar por si. Para estudo no entanto nos concentraremos nos
principais : Selection Sort, Bubble Sort e Quicksort.
Algoritmos de Ordenação 6
Natureza dos Dados
Para melhor escolha de um método de ordenação é preciso saber sobre a natureza dos dados que serão processados.
Entre elas destacam-se duas: Tempo de acesso a um elemento e a possibilidade de acesso direto a um elemento.
O tempo de acesso a um elemento é a complexidade necessária para acessar um elemento em uma estrutura;
1 Ex: Uma estante de livros com seu títulos bem visíveis.
A possibilidade de acesso direto é a capacidade ou impossibilidade de acessar um elemento diretamente na estrutura.
1 Ex: Uma pilha de livros dentro de uma caixa, onde precisamos tirar um a um para saber qual a sua
natureza.
Para classificarmos estes dois ambientes de atuação, costumamos utilizar o meio em que está armazenado os dados.
Em termos computacionais utiliza-se a designação Ordenação Interna, quando queremos ordenar informações em
memória. E Ordenação Externa, quando queremos ordenar informações em arquivo.
Selection Sort (Ordenação por Seleção)
O Selection Sort utiliza um o conceito de "selecionar o elemento mais apto". Ele seleciona o menor ou maior valor
do vetor p.ex. e passa para a primeira (ou última posição dependendo da ordem requerida), depois o segundo menor
para a segunda posição e assim sucessivamente com (n-1) elementos restantes até os dois últimos.
Teste de Mesa de Selection Sort
Vetor inicial:
4 3 1 2
Primeira passagem: Posição 0- compara 4 com 3.Como 3 é menor que 4 este é fixado como mínimo, compara 3 com
1. Como este é menor do que 3 é fixado como mínimo.Compara 1 com 2. Como continua sendo menor, é fixado. Ao
chegar ao final do vetor, como 1 é o menor elemento em comparação com o 4, eles trocam de posição.
1 3 4 2
Segunda Passagem: Posição 1- como já temos 1 como o menor elemento do vetor, passamos para a posição 1.
Comparamos 3 com 4.Como é menor, 3 continua como mínimo.Compara com 2. Como 2 é menor este é fixado
como mínimo.Ao chegar ao final do vetor, como 2 é o menor elemento em comparação com o 3, eles trocam de
posição.
1 2 4 3
Terceira Passagem: Posição 2- pegamos o elemento da posição 2 (4) e comparamos com o 3. Como 3 é o último
elemento do vetor e é menor do que 4 , trocamos as posições.Como os dois elementos são os últimos do vetor, o
Selection Sort encerra-se.
1 2 3 4
Algoritmos de Ordenação 7
Algoritmo do Selection Sort
O algoritmo normalmente é implementado por duas repetições iterando sobre a estrutura em questão. Um exemplo
de algoritmo é:
para i=0 até n-1
mínimo=i
para j=i+1 até N
se vetor[j]<vetor[mínimo]
mínimo=j
auxiliar=vetor[i]
vetor[i]=vetor[mínimo]
vetor[mínimo]=auxiliar
Bubble Sort (Ordenação Bolha)
O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais
simples. A idéia é comparar dois elementos e trocá-los de posição, até que os elementos de maior valor sejam
levados para o final do vetor. O processo continua até a ordenação total do vetor lembrando a forma como as bolhas
em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.
A complexidade desse algoritmo é de ordem quadrática (O(n²)). Por isso, ele não é recomendado para programas que
precisem de velocidade e operem com quantidade elevada de dados. Também é necessária uma condição de parada,
geralmente uma flag ou variável que armazena se houve troca ou não na passagem. Se uma passagem chega ao seu
final sem troca a ordenação cessa.
Teste de Mesa
Vetor inicial:
4 2 5 1
Primeira Passagem: compara 4 com 2. 4 maior que 2.Mudam de posição.
2 4 5 1
Segunda Passagem: compara 4 com 5. 4 menor que 5.Permanece.
2 4 5 1
Terceira passagem: compara 5 com 1. 1 menor que 5.Mudam de posição.
2 4 1 5
Quarta passagem: compara 2 com 4. 2 menor que 4.Permanece.
2 4 1 5
Quinta passagem: compara 4 com 1. 1 menor que 4.Mudam de posição.
2 1 4 5
Sexta passagem: compara 4 com 5. 4 menor que 5.Permanece.
Algoritmos de Ordenação 8
2 1 4 5
Sétima passagem: compara 2 com 1. 1 menor que 2.Trocam de posição.
1 2 4 5
Oitava passagem: compara 2 com 4. 2 menor do que 4.Permanece.
1 2 4 5
Nona passagem: compara 4 com 5. 4 menor do que 5. Permanece.
1 2 4 5
Décima passagem: não há mudanças. Sai do laço.
1 2 4 5
Algoritmo Bubble Sort
O algoritmo pode ser descrito em pseudo-código como segue abaixo. V é um VETOR de elementos que podem ser
comparados e n é o tamanho desse vetor.
BUBBLESORT (V[], n) 1 houveTroca <- verdade # uma variável de controle
2 enquanto houveTroca for verdade faça
3 houveTroca <- falso
4 para i de 1 até n-1 faça
5 se V[i] vem depois de V[i + 1]
6 então troque V[i] e V[i + 1] de lugar e
7 houveTroca <- verdade
Quicksort (Ordenação Rápida)
O quicksort (Ordenação Rápida) é um método de ordenação baseado no conceito de dividir-e-conquistar.
Inicialmente ele seleciona um elemento o qual é chamado de pivô, depois remove este pivô e particiona os elementos
restantes em duas sequências, uma com os valores menores do que o pivô e outras com valores maiores.
Resumo
• Algoritmo de ordenação é uma implementação em uma linguagem de programação para ordenar um conjunto de
dados.
•• Existem diversos tipos de algoritmos de ordenação. Os principais são Selection Sort, Bubble Sort e Quicksort.
Algoritmos de Ordenação 9
Ligações externas
• Sorting Algorithm na Wikipédia em inglês [1]
Esta página é somente um esboço.
Ampliando-a você ajudará a melhorar o Wikilivros.
Referências
[1] http:/ / en. wikipedia. org/ wiki/ Sorting_algorithm
Selection e Insertion
Insertion
Implementações
Pseudocódigo
Segue uma versão simples do pseudocódigo do algoritmo, com vetores começando em zero:
 INSERTION_SORT(A, size) 
 for j ←2 to size do 
 key ← A[ j] 
 i ← j –1 
 while i > 0 and A[i] > key do 
 A[i+1] ← A[i] 
 i ← i –1 
 A[i+1] ← key 
xHarbour
Function SortInsertion( aList )
 Local nLoop1 := 0
 Local nLoop2 := 0
 Local nIndex := 0
 For nLoop1 := 1 To Len( aList )
 nLoop2 := nLoop1
 nIndex := aList[ nLoop1 ]
 While nLoop2 > 1 .And. aList[ nLoop2 - 1 ] > nIndex
 aList[ nLoop2 ] := aList[ nLoop2 - 1 ]
 nLoop2 --
 EndDo
 aList[nLoop2 ] := nIndex
 Next
Return NIL
Selection e Insertion 10
Java
 public static Integer[] insertionSort(Integer[] array) {
 for (int i = 1; i < array.length; i++) {
 int a = array[i];
 int j;
 for (j = i - 1; j >= 0 && array[j] > a; j--)
 array[j + 1] = array[j];
 array[j] = a;
 }
 return array;
 }
Visual Basic
 Private Sub Ordenacao(Numeros() As Integer)
 Dim i As Long
 Dim j As Long
 Dim iMin As Long
 Dim iMax As Long
 Dim varSwap As Variant
 iMin = LBound(Numeros) + 1
 iMax = UBound(Numeros)
 For i = iMin To iMax
 varSwap = Numeros(i)
 For j = i To iMin Step -1
 If varSwap < Numeros(j - 1) Then Numeros(j) = Numeros(j - 1) Else Exit For
 Next j
 Numeros(j) = varSwap
 Next i
End Sub
'Code By Kalandar
C
void insertionSort(int *primeiro, int *ultimo)
{
 int aInserir, *posAIncio + 1, *posAtual;
 for (; posAInsir <= ulmo; ++posAInserir)
 {
 aInserir = *posAInserir;
 posAtual = posArir - 1;
 while (Atual >= priro && *posAtual > aerir )
 {
 *(posAtu+1) = *posAtual;
 --posal;
 }
 *(posl+1) = aInserir;
 }
}
Selection e Insertion 11
Outra versão em C:
void insertionSort(int v[], int n)
{
 int i, j, chave;
 
 for(j=1; j<n; j++) 
 {
 chave = v[j];
 i = j-1;
 while(i >= 0 && v[i] > chave)
 {
 v[i+1] = v[i];
 i--;
 } 
 v[i+1] = chave;
 }
}
Pascal
procedure InsertionSort(var a:vetor; n:integer; var NC, NT: integer);
var j,o:integer; {variaveis auxiliares}
begin
for j:=2 to n do
 begin
o:=j-1;
 while (a[j]<a[o]) and (i>1) do
 begin
 inc(NT);
 troca(a[j],a[o]);
 j:=i-1;
 o:=o-1;
 inc(NC);
 end;
 end;
end;
Python
def inssort(v):
 for j in range(1, len(v)):
 key = v[j]
 i = j - 1
 while a[i] > key and i >= 0:
 a[i+1] = a[i]
 i -= 1
 v[i+1] = key
Selection e Insertion 12
Haskell
import Data.List (insert)
insertsort :: Ord a => [a] -> [a]
insertsort = foldr insert []
C#
 static int[] ordernar(int[] A)
 { 
 int i, j, index;
 for (i = 1; i < A.Length; i++)
 {
 index = A[i];
 j = i;
 while ((j > 0) && (A[j - 1] > index))
 {
 A[j] = A[j - 1];
 j = j - 1;
 }
 A[j] = index;
 }
 return A;
 }
PHP
/**
 * @author Nissius Guilet Ribas
 * @copyright 2009
 *
 * Correção, no while, não é j>=0 e sim j>0;
 */
ini_set('max_execution_time','600');
function microtime_float()
{
 list($usec, $sec) = explode(" ", microtime());
 return ((float)$usec + (float)$sec);
}
for ($gera = 0; $gera <=20000; $gera++){
 $array[$gera] = rand(0, 10000);
}
$time_start = microtime_float();
for($i = 1; $i < count($array); $i++){
 $copiado = $array[$i];
Selection e Insertion 13
 $j = $i;
 while (($j > 0 ) && ($copiado < $array[$j-1])){
 $array[$j] = $array[$j-1];
 $j--;
 }
 $array[$j] = $copiado; 
}
$time_end = microtime_float();
//Mostra o tempo que levou para ordenar
echo $time = $time_end - $time_start;
//Exibe a ordenação
print_r ($array);
O que são estruturas de dados?
Estruturas de dados (Data Structures) é o nome dado a organização de dados e algoritmos de forma coerente e
racional de modo a otimizar o seu uso. De acordo com o modo como um conjunto de dados são organizados e como
as operações que são efetuadas sobre estes dados pode-se solucionar de forma simples problemas extremamente
complexos.
Existem diversos modelos de estruturas de dados, e novos modelos são criados constantemente pois acompanham
também a evolução dos algoritmos e das linguagens de programação. Neste livro iremos abordar as estruturas
clássicas, as quais podem ser utilizadas com sucesso na maioria dos casos.
É um dos temas fundamentais da ciência da computação, utilizado nas mais variadas áreas e para as mais variadas
finalidades. No entanto para começarmos a entender o conceito devemos, antes entender o conceito de algoritmos,
pois algoritmos manipulam dados.
Dados quando estão organizados de uma forma coerente representam uma estrutura de dados. Escolher uma estrutura
de dados ideal pode tornar-se um problema difícil para uma determinada solução. As pesquisas e estudos das
estruturas de dados estão em constante desenvolvimento, apesar disso, existem estruturas que têm se mostrado
padrão, ou seja, são clássicas.
Estruturas de dados possuem características básica, no entanto finalidades bastante diversas. Podem ser
implementadas usando vetores (estático) ou ponteiro (dinâmico).
Abstração de Dados 14
Abstração de Dados
Processos
Um processo é uma sequência ordenada de procedimentos (ou operações) realizadas sobre dados imputados na
máquina computacional de modo a gerar uma solução desejada.
Abstração de Dados
Abstração de dados lida com a representação conceitual dos dados de modo a se implementar algoritmos que
possibilitem a solução mais prática dos problemas apresentados.
Tipos de Dados
A unidade de informação mais básica de uma máquina computacional elétrica é o bit, representado simbolicamente
pelo estado um e zero (estados ligado e desligado). Os bits são agrupados e combinados de forma a representar uma
grande variedade de informação. Devido as dificuldades de se operar e manipular dados a nível de bit (linguagem de
máquina) foram desenvolvidas as linguagens de programação através do qual podemos operar e representar uma
grande quantidade de dados de uma forma mais prática. Estes dados são agrupados em tipos sobre as quais
realizamos uma série de funções de acordo com modelos matemáticos para atingir uma solução.
No entanto em toda e qualquer implementação devemos :
•• Reconhecer as limitações da implementação;
•• Analisar as diversas implementações que podem ser realizadas com os mesmos tipos de dados;
•• Dentre estas escolher a mais adequada para resolver um problema específico;
•• Entender o espaço de armazenamento utilizado e o tempo de execução.
Vetores e Matrizes 15
Vetores e Matrizes
Vetor (Array)
Em computação um Vetor (Array) ou Arranjo é o nome de uma matriz unidimensional considerada a mais simples
das estruturas de dados. Geralmente é constituída por dados do mesmo tipo (homogêneos)e tamanho que são
agrupados continuamente na memória e acessados por sua posição (indíce - geralmente um número inteiro) dentro
do vetor. Na sua inicialização determina-se o seu tamanho que geralmente não se modifica mesmo que utilizemos
menos elementos.
Abaixo temos o exemplo de um vetor. Os valores internos seriam os dados alocados no vetor, enquanto seu tamanho
é dado pelo número de casas disponíveis (no caso 8) e o índice representa a posição do dado no vetor ( por exemplo
podemos definir que 0 tem o índice 1, 2 tem índice 2, 8 tem índice 3 e assim sucessivamente).
0 2 8 9 10 11 15 18
•• Declaração e inicialização de um vetor
A declaração de um vetor em português estruturado pode ser da seguinte forma:
 Nome_Vetor:vetor[tamanho]tipo
Assim temos como exemplo de declarações:
 VECTOR:vetor [10] numérico
 MEDIA: vetor [3] numérico
Tomemos o primeiro exemplo (inteirovector [10]) onde declaramos que estamos criando um vetor para números
chamado de VECTOR com dez posições. Desta forma o computador entende que deve alocar 10 espaços para 10
números inteiros no computador que serão inseridos conforme especificado pelo programa . Por exemplo, vamos
construir dois laços de repetição:
 VECTOR:vetor [10] numérico
 INDICE:numérico
 INDICE<-0
 para INDICE de 0 até VECTOR<9 passo 1 faça
 exibe Escreva um número 
 recebe VECTOR [INDICE]
 fecha_para
 para INDICE de 0 até VECTOR<9 passo 1 faça
 exibeVECTOR [INDICE]
 recebe VECTOR [INDICE]
 fecha_para
Conforme vimos, o primeiro laço para vai entender que ao entrar índice<-0 , quando o usuário digitar o primeiro
valor será alocado este valor em vector[índice].Quando chegar ao final do para ele fará o teste. Se o índice continuar
menor do que 10 ele entra no laço e recebe o segundo valor, chegando ao final do laço e fazendo novamente o
processo até obter os dez valores quando sai do laço.
No segundo laço acessamos estes dados e exibimos na tela aplicando o mesmo príncipio do primeiro laço.
Vetores e Matrizes 16
Operações com Vetores
Podemos trabalhar com vetores numéricos, executando operações sobre eles da mesma forma como executaríamos
com variáveis numéricas comuns. Devemos assumir que ao declararmos um determinado vetor[índice], com um
índice específico, estamos fazendo referência a um número.
Matrizes
Matrizes são arranjos ordenados que ao contrário dos vetores podem ter n dimensões, sendo que estas dimensões
lhes dão o nome n-dimensional . Uma matriz de duas dimensões será chamada bi-dimensional, uma de três
dimensões tri-dimensional e assim consecutivamente. Funciona praticamente da mesma forma que um vetor exceto
que utilizaremos o número n de índices para acessar um dado que queremos. Para efeitos de estudo por enquanto nos
limitaremos somente às matrizes bidimensionais (duas dimensões linha X colunas). Assim se possuimos uma matriz
bidimensional de duas linhas e duas colunas:
3 4
5 6
Consideramos que para acessarmos o valor 3, localizamos o índice por sua linha (1) e coluna (1) , deste modo seu
índice é (1,1). O valor quatro por exemplo será (1, 2).
•• Declaração e inicialização de um matriz
A declaração de uma matriz em português estruturado pode ser da seguinte forma:
tipo Nome_Matriz
[tamanho_linha][tamanho_coluna]
Assim temos como exemplo de declarações:
 inteiro matriz [10][10] 
 real media [3][3]
Em uma matriz como o inteiro matriz que criamos acima é criado espaço para 100 elementos (10x10).Criaremos
abaixo um algoritmo em que o usuário digita 100 elementos e estes aparecem na tela.
inteiro matriz [10][10]
inteiro i , j (i será o índice linha e j o índice
coluna)
para (início: i=0 fim i<10
alteraçãoi+1 )
para
(início:
j=0 fim
j<10
alteraçãoj+1
)
exibe
Escreva
um
número
Vetores e Matrizes 17
recebe
matriz
[i][j]
fecha_para
fecha_para
para (início: i=0 fim i<10
alteraçãoi+1 )
para
(início:
j=0 fim
j<10
alteraçãoj+1
)
exibe Estes são os números
digitados:
exibe matriz [i][j]
fecha_para
fecha_para
Operações com matrizes
Soma e subtração entre matrizes
inteiro matriz_A [2][2]
inteiro matriz_B [2][2]
inteiro matriz_soma [2][2]
para (início: i=0 fim i<2
alteraçãoi+1 )
para
(início:
j=0 fim
j<10
alteraçãoj+1
)
matriz_soma[i][j]=
matriz_A
[i][j]+
matriz_B
[i][j]
fim_para
fim_para
Vetores e Matrizes 18
Multiplicação por um escalar
inteiro escalar
inteiro matriz_A [2][2]
inteiro matriz_multiplicação [2][2]
para (início: i=0 fim i<2
alteraçãoi+1 )
para
(início:
j=0 fim
j<2
alteraçãoj+1
)
matriz_multiplicação[i][j]=
escalar *
matriz_A
[i][j]
fim_para
fim_para
Multiplicação entre matrizes
inteiro matriz_A [2][2]
inteiro matriz_B [2][2]
inteiro matriz_multiplicacao [2][2]
para (início: i=0 fim i<2
alteraçãoi+1 )
para
(início:
j=0 fim
j<2
alteraçãoj+1
)
para
(início:
k=0
fim
k<2
alteraçãok+1
)
matriz_multiplicacao[i][j]=
matriz_multiplicacao
[i][j]+
matriz_A
[i][k]*matriz_B[k][j]
fim_para
Vetores e Matrizes 19
fim_para
Calcular a diagonal e a transposta
inteiro matriz_A [2][2]
inteiro diagonal=0
para (início: i=0 fim i<2
alteraçãoi+1 )
para
(início:
j=0 fim
j<10
alteraçãoj+1
)
se
(i=j)
diagonal=
diagonal+
matriz_A
[i][j]
fim_se
fim_para
fim_para
inteiro matriz_A [2][2]
inteiro inversa=0
inteiro maximo=2
para (início: i=0 fim i<2
alteraçãoi+1 )
para
(início:
j=0 fim
j<2
alteraçãoj+1
)
se
(i+j=(maximo*2)-1)
inversa=
inversa
+
matriz_A
[i][j]
fim_se
fim_para
fim_para
Vetores e Matrizes 20
Resumo
1. include<stdio.h>
2. include<stdlib.h>
1.1. define t 3
int main(){
 int mat[t][t], i, j;
 for(i = 0; i<t; i++){
 for(j = 0; j<t; j++){
 printf("Digite o elemento mat[%d][%d]", i, j);
 scanf("%d", &mat[i][j]);
 }
 }
 for(i = 0; i<t; i++){
 for(j=0; j<t; j++){
 printf("mat[%d][%d] = %d, ", i, j, mat[i][j]);
 }
 printf("\n");
 }
system("pause");
 return 0;
}
Bibliografia
Esta página é somente um esboço.
Ampliando-a você ajudará a melhorar o Wikilivros.
Estruturas 21
Estruturas
Uma estrutura ou registro é o nome dado a alocação de uma ou mais váriaveis de tipos diferentes agrupadas sob
um único nome. Estruturas constituem um importante recurso para organizar os dados de um programa já que trata
um grupo de valores como uma única variável.
Sua sintaxe básica é:
 Nome da estrutura: estrutura 
 {declaração das variáveis}
 fim_estrutura
Ao criarmos um registro, criamos um tipo especial de dado que armazena dentro de si todas as variáveis declaradas
pelo programador. Ao ser chamado pelo usuário, o registro aloca na memória o espaço necessário para aceitação de
todas estas variáveis.
Para escrever ou ler as variáveis armazenadas em uma estrutura, basta apenas especificarmos o nome da estrutura,
seguido de ponto e a variável interna que desejamos acessar.
 Nome da estrutura.nome da variável interna
Exemplo de uso de estrutura
 início
 FUNCIONARIO: estrutura
 CÓDIGO: numérico
 NOME: literal
 SALARIO: numérico
 fim_estrutura
 FUNCIONARIO.SALARIO<-0.00
 escreva "Digite a matrícula do funcionário : "
 leia FUNCIONARIO.MATRICULA
 escreva "Digite o nome do funcionário : "
 leia FUNCIONARIO.NOME
 escreva "Digite o salário do funcionário : "
 leia FUNCIONARIO.SALARIO
 escreva "O funcionário", FUNCIONARIO.MATRICULA "chamado",FUNCIONARIO.NOME "recebe",
 FUNCIONARIO.SALARIO 
 fim
Estruturas 22
Classes como estruturas
As linguagens com orientação a objetos possuem recursos para criar classes, e elas podem funcionar como estruturas
contendo variáveis não-estáticas.
Esta página é somente um esboço.
Ampliando-a você ajudará a melhorar o Wikilivros.
Listas
Um exemplo de uma lista- uma simples lista
ligada com três valores inteiros
Lista é definido como uma implementação de um tipo de dado abstrato
(ADT), formalizando o conceito de uma coleção ordenada de
entidades.Uma lista trata-se de uma série finita de dados, cuja principal
propriedade baseia-se na posição relativa dos elementos dispostos
linearmente. Uma lista tem as seguintes propriedades:
•• se a lista é vazia ; n=0 senão:
•• a1 é o primeiro elemento da lista (cabeça);
•• an é o último elementoda lista;
• ak é um elemento entre a1 e an (1<k<n).
Diversas operações podem ser realizadas sobre uma lista como :
•• Acessar um elemento qualquer da lista;
•• Inserir um elemento em uma posição especificada da lista;
•• Excluir um elemento em uma posição especificada da lista;
•• Combinar duas listas em uma;
•• Particionar uma lista em duas;
•• Ordenar elementos de uma lista;
•• e outras.
Casos especiais de listas
Conforme o modo como uma lista é estruturada, e como esta é manipulada, podemos nos referir a ela de forma mais
específica.
Pilha
Pilha é um modelo de lista onde as operações de inserção, remoção e acesso aos dados são feitos em um único
extremo. Por isto este modelo é também chamado de LIFO (Last In - First Out).
Filas
Fila é um modelo de lista onde a operação de inserção é efetuada por um extremo e a remoção pelo outro extremo.
Por isto este modelo é também chamado de FIFO (First In - First Out).
Pilhas 23
Pilhas
Uma representação simplificada de uma Pilha
Pilha ou stack é um tipo especial de lista linear em que todas as
operações de inserção e remoção são realizadas pela mesma
extremidade chamada topo.
Os elementos são removidos na ordem do programa inversa
daquela em que foram inseridos de modo que o último elemento
que entra é sempre o primeiro ser executado , por isto este tipo de
estrutura é chamada LIFO (Last In - First Out).
O exemplo mais prático que costuma utilizar-se para entender o
processo de pilha é como uma pilha de livros ou pilha de pratos,
no qual ao se colocar diversos elementos uns sobre os outros, se
quisermos pegar o livro mais abaixo deveremos tirar todos os
livros que estiverem sobre ele."
Operações sobre pilhas
Uma pilha geralmente suporta 4 operações básicas:
• TOP: acessa-se o elemento posicionado no topo da pilha;
• PUSH: insere um novo elemento no topo da lista;
• POP: remove o elemento do topo da lista.
• PULL:altera o elememto posicionado no topo da pilha;
As pilhas são úteis quando queremos armazenar temporariamente uma informação que vamos usar logo depois. Se
tivermos uma pilha p e um elemento x qualquer, a operação PUSH (p,x) acrescenta o elemento x no topo da pilha e
aumenta-lhe o tamanho. Já a operação POP(P) remove o elemento que está no topo da pilha fazendo com que esta
diminua. Já a operação TOP não altera o tamanho da estrutura , pois simplesmente visita o topo da pilha retornado
uma cópia do elemento que encontra-se no seu topo.
Visualização do comportamento de uma pilha
Na tabela abaixo é descrito o comportamento de uma pilha. A primeira coluna descreve qual operação é efetuada
sobre uma pilha que inicia vazia, a segunda coluna descreve os elementos da pilha e como estão organizados
(estando o "topo" à direita), visualização descreve o elemento visitado quando utilizado o TOP e a quarta coluna
mostra a quantidade de elementos na pilha.
Operação Pilha Visualização Tamanho da Pilha
PUSH (P,1) 1 1
PUSH (P,2) 1,2 2
TOP 1,2 2 2
PUSH (P,3) 1,2,3 3
POP (P) 1,2 2
POP (P) 1 1
POP (P) 0
Pilhas 24
Operações auxiliares
Ao implementar uma pilha dentro do computador a quantidade de memória alocada funciona como um dos fatores
limitantes da pilha. Assim são necessárias mais três operações para manipular corretamente a estrutura.
• INIT: inicia a pilha como "Vazia"
• IS_EMPTY: verifica se a pilha está "Vazia"
• IS_FULL: verifica se a pilha está "cheia"
Toda vez que criamos uma estrutura de pilha, esta deve ser inicializada para garantir que não haja nenhuma "sujeira"
no local onde esteja montada. Para verificar se uma pilha P está vazia, devemos usar uma função Is_Empty(P) que
retorna verdadeiro se uma pilha estiver vazia. A função Is_Full (P) é utilizada para verificar se a pilha está cheia,
retornando verdadeiro caso não haja espaço para armazenar mais elementos.
Is_Full não é o contrário de Is_Empty. Quando Is_Empty retorna falso, não siginifica no entanto que ela esteja cheia.
Do mesmo modo se uma função Is_Full retorna falso não significa que a pilha esteja vazia.
Pseudo-código de uma pilha
 record Nodo {
 data //informação a ser armazenada no nodo
 próximo // referência ao próximo nodo; null para o último nodo
 }
 record Stack {
 Node stackPointer // ponteiro para o nodo do topo; valor null para uma pilha vazia
 }
 function push(Stack stack, Element element) { // insere elemento em uma pilha
 new(newNode) // Allocate memory to hold new node
 newNode.data := element
 newNode.next := stack.stackPointer
 stack.stackPointer := newNode
 }
 function pop(Stack stack) { // retira o elemento do topo e retorna o nodo do topo agora
 node := stack.stackPointer
 stack.stackPointer := node.next
 element := node.data 
 return element
 }
 function top(Stack stack) { // retorna o nodo no topo
 return stack.stackPointer.data
 }
 function length(Stack stack) { // retorna a quantidade de nodos na pilha
 length := 0
 node := stack.stackPointer
 while node not null {
 length := length + 1
 node := node.next
 }
Pilhas 25
 return length
 }
Aplicações de Pilhas
Pilhas são utilizados em diversas aplicações em Ciência da Computação. Um dos mais salientes casos é a análise de
expressões e sintaxe. Calculadores que utilizam a Notação Polonesa Reversa utilizam pilha para expressar seus
valores, podendo ser representadas de forma prefixa, posfixa ou infixa. Conversões de uma forma de expressão para
outras também necessitam de pilhas. Muitos compiladores utilizam pilhas para análise sintática de expressões,
blocos de programas e afins.
Exemplo de uso de pilha em Notação Polonesa Reversa
Por exemplo: ((1 + 2) * 4) + 3 em notação pós-fixa
1 2 + 4 * 3 +
Utilizando uma pilha consideramos:
•• empilhar quando encontrar um operando;
•• sacar dois operandos e achar o valor quando encontrar uma operação.
•• empilhar o resultado.
Entrada Operação Pilha
1 push operando 1
2 push operando 1, 2
+ adicionar 3
4 Push operando 3, 4
* multiplicar 12
3 push operando 12, 3
+ adicionar 15
O resultado final 15 estará no topo da pilha no fim do cálculo.
Bibliografia
• Stack program in c++ [1]
• Stack Machines - the new wave [2]
• Bounding stack depth [3]
• Libsafe - Protecting Critical Elements of Stacks [4]
• Stack Size Analysis for Interrupt-driven Programs [5] (322 KB)
• Stack Implementation ( Graphical & Text Mode) [6] C Language implementation of Stack
• Pointers to stack visualizations [7]
Pilhas 26
Referências
[1] http:/ / 24bytes. com/ stack. html
[2] http:/ / www. ece. cmu. edu/ ~koopman/ stack_computers/ index. html
[3] http:/ / www. cs. utah. edu/ ~regehr/ stacktool
[4] http:/ / research. avayalabs. com/ project/ libsafe/
[5] http:/ / www. cs. ucla. edu/ ~palsberg/ paper/ sas03. pdf
[6] http:/ / www. mycplus. com/ utilitiesdetail. asp?iPro=1
[7] http:/ / web-cat. cs. vt. edu/ AlgovizWiki/ Stacks
Filas
Fila, também chamado de FIFO (acrônimo do inglês First In, First Out , primeiro a entrar, primeiro a sair) é o nome
dado a estrutura de dados em que ocorrem inserção de dados em um extremo e sua saída por outro, obedecendo
assim "a ordem de chegada" como se fosse uma fila comum de pessoas. A implementação pode realizar-se com
ajuda de vetores, assim como através do uso de ponteiros. Se a fila é implementada com o uso de vetores, o número
máximo de elementos armazenados deve ser estabelecido no código do programa antes da compilação (fila estática)
ou durante sua execução (fila pseudo-estática).
Operações básicas
As filas tem duas operações básicas:
• Enqueue: inserir um elemento no final da fila.
• Dequeue: remover um elemento do começo da fila.
Esta página é somente um esboço.
Ampliando-a você ajudará a melhorar o Wikilivros.Lista encadeada 27
Lista encadeada
Diagrama conceitual de uma lista ligada.
Lista ligada ou Lista encadeada é uma estrutura de
dados linear e dinâmica. Ela é composta por uma
sequência de nodos ou células que contém seus dados e
também uma ou duas referências ("links") que apontam
para o nodo anterior ou posterior. Há diversos modelos
de lista ligadas como lista-encadeada simples, listas
duplamente ligadas e listas encadeadas circulares.
Para se "ter" uma lista ligada, basta guardar seu primeiro elemento, e seu último elemento aponta para uma célula
nula. O esquema a seguir representa uma lista ligada com 5 elementos:
Célula 1 ---> Célula 2 ---> Célula 3 ---> Célula 4 ---> Célula 5 ---> (Nulo)
Para manipularmos estas listas nomeadamente: inserir dados ou remover dados temos que ter sempre em atenção em
ter um ponteiro que aponte para o 1º elemento e outro que aponte para o fim, isto porque se queremos inserir ou
apagar dados que estão no inicio ou no fim da lista então a operação é rápidamente executada caso seja um nó que
esteja no meio da lista pois terá que haver uma procura até encontrar a posição desejada.
Tipos de listas encadeadas
Lista encadeada simples
Uma lista encadeada simples é aquela que contém apenas um link por nodo. Este link aponta para o próximo nodo da
lista, ou para um valor nulo (vazio) quando se trata do nodo final.
Lista encadeada simples com três valores inteiros.
Lista duplamente encadeadas
Listas duplamente encadeadas ou lista de duas vias, são um modelo mais sofisticado das listas simples: cada nodo
possui dois ponteiros - um que aponta para o nodo anterior (ou null se é o primeiro valor ou a lista está vazia) e outro
que aponta para o próximo nodo (ou null se é o último nodo ou a lista está vazia).
Um exemplo de uma lista duplamente encadeada
Lista encadeada 28
Listas encadeadas circulares
Na lista encadeada circular, o primeiro e o último nodo são ligados entre si. Nas listas circulares simples, há apenas
um link que aponta para o próximo nodo; enquanto nas listas circulares duplas há dois links em cada nodo que
apontam para o elemento anterior e para o posterior.
Um exemplo de uma lista circular simples
Pseudo-código de listas encadeadas
Lista encadeada simples
 record Node {
 data // O dado a ser armazenado no nodo
 next // Referência ao próximo nodo; null se for o último nodo
 }
 record List {
 Node firstNode // ponteiro para o primeiro nodo da lista; null para uma lista 
 vazia
 }
Atravessar uma lista simples é fácil iniciando pelo primeiro nodo e seguindo cada next até o fim.
 node := list.firstNode
 while node not null {
 node := node.next
 }
Tabela de Hash 29
Tabela de Hash
Em ciência da computação a tabela hash (de hashing, no inglês), também conhecida por tabela de espalhamento, é
uma estrutura de dados especial, que associa chaves de pesquisa (hash) a valores. Seu objetivo é, a partir de uma
chave simples, fazer uma busca rápida e obter o valor desejado. É algumas vezes traduzida como tabela de
escrutínio.
Complexidade e usos comuns
Tabelas hash são tipicamente utilizadas para implementar vetores associativos, sets e cache|caches. São tipicamente
usadas para indexação de grandes volumes de informação (como bases de dados). A implementação típica busca
uma função hash que seja de complexidade O(1), não importando o número de registros na tabela (desconsiderando
colisões). O ganho com relação a outras estruturas associativas (como um vetor simples) passa a ser maior conforme
a quantidade de dados aumenta. Outros exemplos de uso das tabelas hash são as tabelas de transposição em jogos de
xadrez para computador até mesmo em serviços de DHCP.
A função de espalhamento
A função de espalhamento ou função hash é a responsável por gerar um índice a partir de determinada chave. Caso a
função seja mal escolhida, toda a tabela terá um mau desempenho.
O ideal para a função de espalhamento é que sejam sempre fornecidos índices únicos para as chaves de entrada. A
função perfeita seria a que, para quaisquer entradas A e B, sendo A diferente de B, fornecesse saídas diferentes.
Quando as entradas A e B são diferentes e, passando pela função de espalhamento, geram a mesma saída, acontece o
que chamamos de colisão.
Na prática, funções de espalhamento perfeitas ou quase perfeitas são encontradas apenas onde a colisão é intolerável
(por exemplo, nas funções hash da criptografia), ou quando conhecemos previamente o conteúdo da tabela
armazenada). Nas tabelas hash comuns a colisão é apenas indesejável, diminuindo o desempenho do sistema. Muitos
programas funcionam sem que seu responsável suspeite que a função de espalhamento seja ruim e esteja
atrapalhando o desempenho.
Por causa das colisões, muitas tabelas hash são aliadas com alguma outra estrutura de dados, tal como uma lista
encadeada ou até mesmo com árvore AVL|árvores balanceadas. Em outras oportunidades a colisão é solucionada
dentro da própria tabela.
Exemplo de função de espalhamento e colisão
Imagine que seja necessário utilizar uma tabela hash para otimizarmos uma busca de nomes de uma lista telefônica
(dado o nome, temos que obter o endereço e o telefone). Nesse caso, poderíamos armazenar toda a lista telefônica em
um vetor e criar uma função de espalhamento que funcionasse de acordo com o seguinte critério:
 Para cada nome começado com a letra A, retornar 0
 Para cada nome começado com a letra B, retornar 1
 ...
 Para cada nome começado com a letra Z, retornar 25
O exemplo anterior poderia ser implementado, em Linguagem de programação C|C, da seguinte forma:
 int hashExemplo(char * chave)
 {
 return (chave[0]-65);
Tabela de Hash 30
 }
Agora inserimos alguns nomes em nossa lista telefônica:
José da Silva; Rua das Almas, 35; Telefone (11) 888-9999
Ricardo Souza; Rua dos Coqueiros, 54; Telefone (11) 222-4444
Orlando Nogueira; Rua das Oliveiras, 125; Telefone (11) 444-5555
Agora inserimos mais um nome:
Renato Porto; Rua dos Elefantes, 687; Telefone (11) 333-5555
Como se pode notar, a função de exemplo causaria muitas colisões. Se inserirmos um outro nome começado com a
letra R, teremos uma outra colisão na letra R. Se inserirmos "João Siqueira", a entrada estaria em conflito com o
"José da Silva".
Resolvendo colisões
Um bom método de resolução de colisões é essencial, não importando a qualidade da função de espalhamento.
Considere um exemplo derivado do paradoxo|paradoxo do aniversário: mesmo que considerarmos que a função irá
selecionar índices aleatórios uniformemente em um vetor de um milhão de posições, há uma chance de 95% de haver
uma colisão antes de inserirmos 2500 registros.
Há diversos algoritmos de resolução de colisão, mas os mais conhecidos são Encadeamento Separado e
Endereçamento Aberto.
Encadeamento Separado
É a solução mais simples, em que normalmente um registro aponta para uma lista encadeada em que são
armazenados os registros em conflito. A inserção na tabela requer uma busca e inserção dentro da lista encadeada;
uma remoção requer atualizar os índices dentro da lista, como se faria normalmente.
Estruturas de dados alternativas podem ser utilizadas no lugar das listas encadeadas. Por exemplo, se utilizarmos
uma Árvore AVL|árvore balanceada, podemos melhorar o tempo médio de acesso da tabela hash para O(log n) ao
invés de O(n). Mas como as listas de colisão são projetadas para serem curtas, o overhead causado pela manutenção
das árvores pode fazer o desempenho cair.
Apesar disso, as árvores podem ser utilizadas como proteção contra ataques que buscam criar overhead
propositalmente - descobrindo uma forma da função gerar repetidamente o mesmo índice - e derrubar o sistema
(ataques DOS). Nesse caso, uma árvore balanceada ajudaria o sistema a se manter estável, por ser uma estrutura com
grande capacidadede crescimento.
Endereçamento Aberto
No método de Endereçamento Aberto os registros em conflito são armazenados dentro da própria tabela. A resolução
das colisões é realizadas através de buscas padronizadas dentro da própria tabela.
A forma mais simples de fazer a busca é procurar linearmente na tabela até encontrar um registro vazio ou o registro
buscado. Outras formas utilizadas incrementam o índice exponencialmente: caso o registro não seja encontrado na
posição 10, será buscado na posição 100, depois na posição 1000. A inserção tem que seguir o mesmo critério da
busca.
Outra forma mais complexa de implementar o Endereçamento Aberto é criar uma nova função de espalhamento que 
resolva o novo conflito (também chamado de double hashing). Na prática, o que acontece nesse caso é que o vetor 
da tabela é formado por uma seqüência de funções de espalhamento auxiliares, onde a chave de entrada será o valor 
gerado pela função anterior. Esse tipo de implementação pode ser útil em casos muito específicos, com enormes
Tabela de Hash 31
quantidades de dados, mas normalmente o overhead não justifica a experiência.
Indexação Perfeita
Se tivermos uma relação fixa de registros, podemos obter uma função que indexe os itens sem que ocorra nenhuma
colisão, chamada função de espalhamento perfeita. Podemos até mesmo buscar uma função de espalhamento perfeita
mínima, que, além de não causar colisões, preenche todas as posições da tabela. As funções de espalhamento
perfeitas fazem o acesso aos dados ser O(1) no pior caso.
Existem métodos que atualizam a função de espalhamento de acordo com a entrada, de forma que nunca ocorra
colisão. O inconveniente dessa técnica é que a própria atualização da função de espalhamento causa overhead do
sistema.
Problemas e comparações com outras estruturas
Apesar das tabelas hash terem em média tempo constante de busca, o tempo gasto no desenvolvimento é
significativo. Avaliar uma boa função de espalhamento é um trabalho duro e profundamente relacionado à estatística.
Na maioria dos casos soluções mais simples como uma lista encadeada devem ser levados em consideração.
Os dados na memória ficam aleatoriamente distribuídos, o que também causa overhead no sistema. Além disso, e
mais importante, o tempo gasto na depuração e remoção de erros é maior do que nas árvore AVL, que também
podem ser levadas em conta para solução do mesmo tipo de problema.
Árvore
Árvore é uma estrutura de dados que herda as características das topologias em árvore. Conceptualmente diferente
das listas encadeadas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma
hierárquica.
A árvore é composta por um elemento principal chamado raiz, que possui ligações para outros elementos, que são
denominados de galhos ou filhos. Estes galhos levam a outros elementos que também possuem outros galhos. O
elemento que não possui galhos é conhecido como folha ou nó terminal.
O número máximo de galhos em um elemento é chamado ordem da árvore. Uma árvore binária é aquela de ordem 2,
i.e., em que cada elemento possui no máximo 2 galhos.
Uma das operações importantes consiste em percorrer cada elemento da árvore uma única vez. Esse percurso,
também chamado de travessia da árvore, pode ser feito em pré-ordem (os filhos de um nó são processados após o
nó) ou em pós-ordem (os filhos são processados antes do nó). Em árvores binárias é possível ainda fazer uma
traversia em-ordem, em que se processa o filho à esquerda, o nó, e finalmente o filho à direita.
O algoritmo abaixo descreve uma travessia pré-ordem:
PercursoPreordem(nó): 
 Processa nó
 Para cada filho de nó (se houver)
 Executa recursivamente PercursoPreordem(filho) 
Outra operação, utilizada nas árvores de pesquisa é a travessia da raiz até uma das folhas. Essa operação tem um 
custo computacional proporcional ao número de níveis da árvore. O pior caso é a travessia de todos os elementos até 
a folha de nível mais baixo. A árvore balanceada, em que todas as folhas possuem o mesmo nível (com exceção de 
uma delas, que pode estar um nível acima) apresenta o melhor pior caso possível, para um certo número de nós. O 
pior pior caso apresenta-se na árvore degenerada em que cada nó possui exatamente um filho, e a árvore tem o
Árvore 32
mesmo número de níveis que de nós, assemelhando-se a uma lista ligada.
Topologia em árvore
Diagrama conceptual de uma topologia em árvore. Cada número é um nó.
Um configuração em árvore ou topologia
em árvore é uma caracterização física de
um objecto (ou seus componentes), que,
pela sua configuração, se assemelha a uma
árvore, no sentido em que as suas
ramificações tendem a convergir para uma
raíz, ou uma origem (por exemplo, árvore
genealógica).
Introduz-se, portanto, a noção de raíz e
descendência.
Em informática é vulgarmente utilizada
como topologia, ao lado de outras como
topologia em anel ou topologia em estrela.
Em programação são largamente utilizadas como estruturas de dados para resolver problemas complexos, como
indexação, por exemplo.
Nós de uma árvore
Por definição, uma árvore é constituída por nós. Um árvore vazia (sem nós) é também uma árvore.
Um nó de uma árvore é o elemento unitário da árvore. Deste nó podem derivar (descender) outros nós, designados
de nós-filho, sendo o nó actual o nó-pai.
O grau de uma árvore é o número máximo de descendentes encontrado, para cada um dos nós. Se todos os nós
derivam (no máximo) outros 2 nós, então estaremos perante uma árvore binária.
Esta página é somente um esboço.
Ampliando-a você ajudará a melhorar o Wikilivros.
Árvores Binárias 33
Árvores Binárias
Exemplo de árvore binária
Árvore binária é uma estrutura de dados caracterizada por:
•• Ou não tem elemento algum (árvore vazia).
•• Ou tem um elemento distinto, denominado raiz, com dois
apontamentos para duas estruturas diferentes, denominadas
sub-árvore esquerda e sub-árvore direita.
Perceba que a definição é recursiva e, devido a isso, muitas
operações sobre árvores binárias utilizam recursão. É o tipo de
árvore mais utilizado na computação. A principal utilização de
árvores binárias são as árvores de busca.
Definições para árvores binárias
Os nós de uma árvore binária possuem graus zero, um ou dois. Um nó de grau zero é denominado folha.
Uma árvore binária é considerada estritamente binária se cada nó da árvore possui grau zero ou dois.
A profundidade de um nó é a distância deste nó até a raiz. Um conjunto de nós com a mesma profundidade é
denominado nível da árvore. A maior profundidade de um nó, é a altura da árvore.
Uma árvore é dita completa se todas as folhas da árvore estão no mesmo nível da árvore.
Definições em teoria dos grafos
Em teoria dos grafos, uma árvore binária é definida como um grafo acíclico, conexo, dirigido e que cada nó não tem
grau maior que 3. Assim sendo, só existe um caminho entre dois nós distintos.
E cada ramo da árvore é um vértice dirigido, sem peso, que parte do pai e vai o filho.
Percursos em árvore
Existem três tipos de percursos: Percurso em InOrdem, PreOrdem e PosOrdem.
InOrdem
O algoritmo desse percurso é:
emOrdem(Struct No *n){
 if(n!=null){
 emOrdem(n->esq);
 visita(n);
 emOrdem(n->dir);
 }
}
Para a árvore acima, o percurso seria: 2, 7, 5, 6, 11, 2, 5, 4 e 9.
Árvores Binárias 34
PreOrdem
O algoritmo desse percurso é:
preOrdem(Struct No *n){
 if(n!=null){
 visita(n);
 preOrdem(n->esq);
 preOrdem(n->dir);
 }
}
Para a árvore acima, o percurso seria: 2, 7, 2, 6, 5, 11, 5, 9 e 4.
PosOrdem
O algoritmo desse percurso é:
posOrdem(Struct No *n){
 if(n!=null){
 posOrdem(n->esq);
 posOrdem(n->dir);
 visita(n);
 }
}
Para a árvore acima, o percurso seria: 2, 5, 11, 6, 7, 4, 9, 5 e 2.
Transformação de uma árvore n-ária
Uma árvore n-ária qualquer (árvore cujos nós possuem graus menoresou iguais a n) podem ser representados por
uma árvore binária. Um exemplo dessa transformação pode ser vista em [1]
Métodos para representação de árvores binárias
Uma das maneiras mais simples de representar árvores binárias em linguagens de programação é por meio de
arranjos unidimensionais (vetores). Dado um nó de índice i qualquer, os seus filhos terão índices 2i + 1 e 2i + 2 e o
seu pai terá índice piso((i - 1)/2). Essa implementação é utilizada para representar árvores completas ou quase
completas. Heaps, que são árvores binárias quase completas são implementadas na forma de um vetor de uma
maneira bastante eficiente.
Apesar da simplicidade, essa representação requer uma grande quantidade de memória contígua para o
armazenamento de árvores grandes, o crescimento desta é difícil de implementar e manter e pode haver grande
quantidade de desperdício de memória.
Árvores Binárias 35
Em uma linguagem que possua suporte a estruturas e referências (por exemplo Pascal e C), as árvores são
implementadas a partir de nós, com um, ou mais, campos para a(s) informação(ões) principal(is) e dois campos
apontadores especiais, denominados esquerda e direita, que fazem referência às sub-árvores esquerda e direita,
respectivamente. Algumas vezes, há um apontador para o pai. Em um nó do tipo folha, os campos apontadores
possuem valores especiais (nil em Pascal e NULL em C).
Referências
[1] http:/ / en. wikipedia. org/ wiki/ Image:Nary_to_binary_tree_conversion. png
Árvores AVL
Uma árvore não-AVL
Árvore AVL (ou árvore balanceada pela altura)é
uma árvore de busca binária auto-balanceada. Em tal
árvore, a altura de dois nós folha difere no máximo em
uma unidade. As operações de busca, inserção e
eliminação de elementos possuem complexidade
(no qual é o número de elementos da
árvore). Inserções e eliminações podem também
requerer o rebalanceamento da árvore, exigindo uma ou
mais rotações.
O nome AVL vem de seus criadores Georgii Adelson
Velsky e Yevgeniy Landis ,cuja primeira referência
encontra-se no documento "Algoritmos para
organização da informação" de 1962.
Características
Balanceamento
Uma árvore AVL é dita balanceada quando a diferença entre as alturas das sub-árvores não é maior do que um. Caso
a árvore não estiver balanceada é necessário seu balanceamento através da rotação simples ou rotação
Árvores AVL 36
Mesma árvore após balanceamento por altura, agora uma árvore
AVL
dupla. O balanceamento é requerido para as operações
de adição e exclusão de elementos. Para definir o
balanceamento é utilizado um fator específico para nós.
O fator de balanceamento de um nó é dado pelo seu
peso em relação a sua sub-árvore. Um nó com fator
balanceado pode conter 1, 0, ou -1 em seu fator. Um nó
com fator de balanceamento -2 ou 2 é considerado um
árvore não-AVL e requer um balanceamento por
rotação ou dupla-rotação.
Operações
Inserção
Inserção em uma árvore AVL deve ser dada pela inserção do nodo seguida de uma verificação na propriedade do
fator de balanceamento. Caso não obedeça a essa propriedade, deve-se fazer uma rotação conveniente.
Remoção
A remoção deve ser dada por uma rotação em torno do nodo a ser removido, a fim de torná-lo folha para que então
possa ser removido. Em alguns casos, após a remoção são necessárias rotações para ajustar o fator de balanceamento.
Pesquisa
O número de comparações para localizar um elemento em AVL é aproximadamente 1.44 log2 n no pior caso.
Rotação
A operação básica em uma árvore AVL geralmente envolve os mesmos algoritmos de uma árvore de busca binária
desbalanceada. A rotação na árvore AVL ocorre devido ao seu desbalanceamento, uma rotação simples ocorre
quando um nó está desbalanceado e seu filho estiver no mesmo sentido da inclinação. Uma rotação-dupla ocorre
quando um nó estiver desbalanceado e seu filho estiver inclinado no sentido inverso ao pai.
Rotação à esquerda
Em uma árvore binária, basta empurrar o nodo N para baixo e para a esquerda. O filho à direita de N o substitui, e o
filho à esquerda do filho à direita vem a ser o novo filho à direita de N. Segue pseudocódigo:
Seja Y o filho à direita de X Troque X por Y Torne o filho à esquerda de Y o
filho à direita de X.
Rotação à direita
Em uma árvore binária basta empurrar o nodo N para baixo e para a direita. O filho à esquerda de N o substitui, e o
filho à direita do filho à esquerda vem a ser o novo filho à esquerda de N. Segue pseudocódigo:
Seja Y o filho à esquerda de X Troque X por Y Torne o filho à direita de Y o
filho à esquerda de X. É interessante observar que as rotações duplas nada mais são que duas rotações
simples seguidas, independentes se à direita ou à esquerda.
Árvores AVL 37
Bibliografia
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second
Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7.
Ligações externas
• Applet de uma Árvore AVL [1]
• Mais um applet de Árvore AVL [2]
• Árvores AVL no National Institute of Standarts and Technology [3]
Referências
[1] http:/ / www. csi. uottawa. ca/ ~stan/ csi2514/ applets/ avl/ BT. html
[2] http:/ / webpages. ull. es/ users/ jriera/ Docencia/ AVL/ AVL%20tree%20applet. htm
[3] http:/ / www. nist. gov/ dads/ HTML/ avltree. html
Árvores Rubro-Negras
Visualização de uma árvore rubro-negra
Árvore rubro-negra (Red-Black tree)
é uma estrutura de dados de
programação criada em 1972 com o
nome de árvores binárias simétricas.
Como as árvores binárias comuns às
rubro-negras possuem um conjunto de
operações (inserção, remoção, busca),
porém são geralmente mais eficientes
devido ao fato da rubro-negra estar
sempre balanceada. Este
balanceamento se dá justamente pela
característica que dá nome a árvore,
que vem de um bit extra em cada nodo que determina se esta é "vermelha" ou "preta" dentro do conjunto de regras
que rege a árvore. Além desde bit, cada nodo também conta com os campos dados do nodo, filho esquerdo do nodo,
filho direito do nodo e pai do nodo.
Regras da rubro-negra
Uma árvore rubro-negra estará sempre balanceada pois segue o seguinte conjunto de regras:
•• cada nodo da árvore possui um valor
•• a cada novo nodo inserido na árvore obedecerá o esquema de menor para o lado esquerdo e maior para o lado
direito.
•• a cada nodo é associado uma cor: vermelha ou preta.
•• o nodo raiz é sempre preto.
•• nodos vermelhos que não sejam folhas possuem apenas filhos pretos.
•• todos os caminhos a partir da raiz até qualquer folha passa pelo mesmo número de nodos pretos.
A cada vez que uma operação é realizada na árvore, testa-se este conjunto de propriedades e são efetuadas rotações e
ajuste de cores até que a árvore satisfaça todas estas regras.
Árvores Rubro-Negras 38
Rotações
Uma rotação é uma operação realizada na árvore para garantir seu balanceamento. Na rubro-negra pode ser feita a
direita e a esquerda, onde são alterados os nodos rotacionados.
Inserções
Ao inserir-se um elemento em uma árvore rubro-negra, esta é comparada com os elementos e alocada em sua
posição conforme a regra 2. Ao inserir um elemento ele é sempre da cor vermelha (exceto se for o nodo raiz). A
seguir a árvore analisa se o antecessor da folha. Se este for vermelho será necessário alterar as cores para garantir a
regra 6.
Remoções
Existem dois tipos de remoção em uma árvore:
Remoção efetiva
Com as operações de rotação e alteração de cor, remove-se o nodo e estabelece-se as propriedades da árvore.
Remoção preguiçosa
Esta remoção marca um nó como removido, mas efetivamente não o retira. Sendo desta maneira nenhuma alteração
é efetuada na árvore, porém são necessários novos mecanismos de busca e inserção para que reconheçam o nó como
"ausente".
Bibliografia
• Mathworld: Red-Black Tree [1]
• San Diego State University: CS 660: Red-Black tree notes [2], por Roger Whitney
• Thomas H. Cormen,Charles E. Leiserson, Ronald L. Rivest, e Clifford Stein. Introduction to Algorithms, Second
Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Chapter 13: Red-Black Trees, pp. 273–301.
Ligações externas
Demos
• Red/Black Tree Demonstration [3], um demo interativo em Java
• Red-Black Tree Animation [4]
• aiSee: Visualization of a Sorting Algorithm [5], uma animação em gif (200 Kb)
• Red-Black Tree Demonstration [6],um demo em Java criado por David M. Howard
• AVL Tree Applet [2]
Árvores Rubro-Negras 39
Implementações
• Efficient implementation of Red-Black Trees [7]
• RBT: A SmallEiffel Red-Black Tree Library [8]
• libredblack: A C Red-Black Tree Library [9]
• Red-Black Tree C Code [10]
• Red-Black Tree Java implementation in java.util.TreeMap [11]
• DragonFlyBSD VM subsystems utilize Red-Black trees [12]
Referências
[1] http:/ / mathworld. wolfram. com/ Red-BlackTree. html
[2] http:/ / www. eli. sdsu. edu/ courses/ fall95/ cs660/ notes/ RedBlackTree/ RedBlack. html#RTFToC2
[3] http:/ / www. ececs. uc. edu/ ~franco/ C321/ html/ RedBlack/ redblack. html
[4] http:/ / www. ibr. cs. tu-bs. de/ lehre/ ss98/ audii/ applets/ BST/ RedBlackTree-Example. html
[5] http:/ / www. aisee. com/ anim/ maple. htm
[6] http:/ / web. archive. org/ 20060210122840/ geocities. com/ dmh2000/ articles/ code/ red-blacktree. html
[7] http:/ / eternallyconfuzzled. com/ tuts/ redblack. html
[8] http:/ / efsa. sourceforge. net/ archive/ durian/ red_black_tree. htm
[9] http:/ / libredblack. sourceforge. net/
[10] http:/ / web. mit. edu/ ~emin/ www/ source_code/ red_black_tree/ index. html
[11] http:/ / www. javaresearch. org/ source/ jdk142/ java/ util/ TreeMap. java. html
[12] http:/ / dragonflybsd. org
Árvores B
Exemplo de Árvore B
Árvore B ou B-Tree são estruturas de dados
muito utilizadas em banco de dados e
sistema de arquivos.
Para inserir ou remover variáveis de um nó,
o nó não poderá ultrapassar sua ordem e
nem ser menor que sua ordem dividida por
dois. Árvores B não precisam ser
rebalanceadas como são freqüentemente as
árvores de busca binária com Árvore AVL.
Árvores B têm vantagens substanciais em
relação a outros tipos de implementações quanto ao tempo de acesso e pesquisa aos nós.
O criador das árvores B, Rudolf Bayer, não definiu claramente de onde veio o B das árvores B. Ao que parece, o B
vem de balanceamento onde todos os nós da árvore estão em um mesmo nível. Também é possível que o B tenha
vindo de seu sobrenome Bayer, ou ainda do nome da empresa onde trabalhava Boeing, no Boeing Scientific
Research Labs.
Introdução
O estudo das diferentes estruturas de dados vistas anteriormente foi realizado supondo um custo de acesso aos dados
uniforme e da mesma ordem de grandeza que as demais operações. Porém, na prática, isso nem sempre é o caso. Em
sistemas computacionais atuais, a memória é organizada hierarquicamente, sendo o custo de acesso inversamente
proporcional ao custo financeiro. Por ordem decrescente de velocidade de acesso (e por ordem crescente de custo
financeiro), temos: registros internos do processador, memória cache, memória principal (RAM), memória
secundária (disco rígido), memória externa (mídia ótica, fitas).
Árvores B 40
Um exemplo é quando é preciso representar e manipular através de buscas, inserções e remoções, uma quantidade de
dados tal que a capacidade da memória principal disponível não é suficiente. Neste caso, por razões econômicas (o
custo de expansão da memória principal) ou tecnológicas (o maior tamanho de memória principal que o sistema
operacional pode gerenciar), torna-se necessário recorrer a memória secundário para armazenar parte dos dados.
Historicamente, o tempo de acesso a memória secundária (discos ou fitas) sempre foi muito superior ao de acesso a
memória principal. Nas tecnologias atuais, o fator relacionando esses dois tempos torna entre e : o tempo
de um acesso em memória secundária é equivalente ao tempo de execução de 10.000 a 100.000 instruções. Em geral,
os sistemas gerenciadores de bancos de dados devem operar vários usuários em paralelo. Supondo uma média de 50
usuários concorrentes, e um tempo médio de acesso ao disco de 10ms, o número médio de acessos que um usuário
pode fazer é de 2 por segundo.
Por exemplo, supõe que você deve elaborar um sistema de gerenciamento de um banco de dados que tem cerca de
25.000.000 (vinte-e-cinco milhões) de registros. Cada registro tem um tamanho de 1kB e uma chave de 4 bytes
(supondo a existência de uma relação de ordem entre as chaves). A quantidade total de memória necessária é de 25
GB (vinte-e-cinco gigabytes). Se for usada uma árvore binária balanceada, por exemplo uma árvore rubro-negra, os
números médio e máximo de acessos à memória secundária numa busca seria 48 ( )$. Os
tempos médios e máximos de busca seriam portanto 12s e 24s. Em certas aplicações, esses números podem não ser
aceitáveis.
As árvores B são um tipo de árvores de busca que foram projetadas para minimizar o número de acessos à memória
secundária. Como o número de acessos à memória secundária depende diretamente da altura da árvore, as árvores B
foram projetadas para ter uma altura inferior às árvores rubro-negras ou AVL, para um dado número de chaves. Para
manter o número de registros armazenados e, ao mesmo tempo, diminuir a altura, uma solução é aumentar o grau de
ramificação da árvore (o número máximo de filhos que um nó pode ter). Assim árvores B são árvores de busca que
possuem um grau de ramificação geralmente muito maior que 2. Além disso, a cada nó de uma árvore B são
associados mais de um registro de dados: se o grau de ramificação de um nó for , este pode armazenar até 
registros. A figura abaixo mostra um exemplo de árvore B, com grau de ramificação dos nós de até 4.
Em geral o grau de ramificação de uma árvore B é determinado pelas características físicas da memória secundária
empregada, pois memórias secundárias usualmente têm uma unidade atômica de leitura/escrita. Para armazenar uma
árvore B, cada nó da árvore será armazenado numa unidade de memória secundária. Por exemplo, supondo que a
unidade tem uma capacidade de 4kB e que seu endereço seja codificado sobre 4 bytes. O maior grau de ramificação
possível neste caso é denotado e é tal que: , ou seja .
Esse grau de ramificação é muito perto do das árvores balanceadas. A altura do árvore B correspondente não será
significativamente inferior a altura que teria uma árvore binária correspondente.
Uma alternativa é, no lugar de armazenar o registro inteiro no nó da árvore B, colocar a chave e uma referência a um
unidade de disco que contem essa informação. Em nosso exemplo, o tamanho de uma referência é 4 bytes. Supondo
que o tamanho da chave seja também de 4 bytes, o grau de ramificação é tal que:
, ou seja .
Neste caso, cada nó armazena 341 chaves com a referência ao registro correspondente. A raiz pode ter até 342 filhos
e 116964 netos. A capacidade desta árvore B é referências.
Supondo que a raiz sempre fica em memória principal, são necessários, no máximo, dois acessos a memória
secundária para achar uma chave, e de um terceiro acesso para ler o registro correspondente. Utilizando os
parâmetros da discussão acima, o tempo de espera do usuário devido as transações com a memória secundária cai
para 1,5s (a comparar com as estimativas de até 24s com uma implementação por árvores rubro-negra).
Árvores B 41
Estrutura do nó
Nós em árvores B, também denominado páginas, geralmente são representados por um conjunto de elementos
apontando para seus filhos. Alguns autores consideram a ordem de uma árvore B como sendo a quantidade de
registros que a página pode suportar. Outros consideram a ordem como a quantidade de campos apontadores. Todo
nó da árvore tem um mínimo de registros definido pela sua ordem, que é a metade da ordem, arredondando-se para
baixo, caso a árvore seja de ordemímpar, exceto a raiz da árvore, que pode ter um mínimo de um registro. Por
exemplo, os nós de uma árvore de ordem 5, podem ter, no mínimo registros, ou seja, dois registros. A
quantidade de filhos que um nó pode ter é sempre a quantidade de registros do nó mais 1 (V+1). Por exemplo, se um
nó tem 4 registros, este nó terá obrigatoriamente 5 apontamentos para os nós filhos.
Algoritmos
Inserção
1.1. Primeiro, pesquise a posição onde este nó será incluído. Então, insira o valor dentro do nó.
2.2. Se nenhum nó ficou errado, acima ou abaixo da ordem div 2, o processo é terminado.
3.3. Se algum nó ficar acima da ordem, dividimos o nó, o valor central do nó dividido sobe para a posição do pai,
continuando assim recursivamente por toda a árvore. Se o nó estourar na raiz, então é criado um novo nó raiz
(podendo ter um único elemento).
Exclusão
1.1. Primeiro, busque um valor a ser excluído. Então, remova-o de dentro de um nó.
2.2. Se nenhum nó teve problema, o processo é terminado.
3.3. Se algum nó estiver errado, então há duas possibilidades:
1.1. Se o nó ao lado do nó errado pode transferir um ou mais de seus nós filho ao nó atual, então o nó atual voltará
ao normal. Após ter atualizado os valores da separação do pai e dos dois filhos, o processo é terminado.
2.2. Se o nó ao lado do nó errado não tem um filho extra porque está no limite mais baixo, então ambos os nós
serão fundidos em um único nó. Continuando até que o nó atual esteja normal.
Exercício
Seja uma árvore B de altura e grau máximo de ramificação . Dar, em função de e , o número
máximo de referências que essa árvore B pode armazenar.
Ligações externas
• Animação de uma simples árvore B [1].
• Applet de uma B-Tree [2]
Esta página é somente um esboço.
Ampliando-a você ajudará a melhorar o Wikilivros.
Árvores B 42
Referências
[1] http:/ / www. cse. ohio-state. edu/ ~bondhugu/ acads/ 234-tree/ index. shtml
[2] http:/ / slady. net/ java/ bt/
Estruturas para classes de equivalência
Estruturas para classes de equivalência
Introdução
Diversos problemas podem ser modelados através do cálculo de classes de equivalência (uma definição formal desse
conceito é apresentada logo em seguida). Um exemplo famoso é aquele de determinar os componentes conexos de
um grafo. Um grafo é um conjunto de vértices que podem ser conectados dois a dois por arestas. Como determinar
se, dado o conjunto das arestas, existe um caminho entre dois vértices? Se considerarmos dois vértices como
equivalentes quando existe um caminho entre os dois, então uma solução desse problema consiste em determinar se
dois vértices fazem parte da mesma classe de equivalência.
Definições
Uma relação binária sobre um domínio é uma relação de equivalência se satisfaz as seguintes
propriedades
1. ( é simétrica);
2. ( é reflexiva);
3. ( é transitiva).
Seja um elemento do domínio, a classe de equivalência de é o conjunto dos
elementos relacionados com .
Objetivo
O cliente do tipo abstrato de dados manipula valores de um determinado domínio que nomeamos D. O objetivo é
definir um tipo abstrato de dados que permita representar e manipular eficientemente classes de equivalência que
evoluem dinamicamente. Inicialmente cada classe de equivalência é constituída por um único elemento do domínio
D, d. O nome de cada classe é d. Queremos operações para unir classes, e determinar o nome da classe de
equivalência de um elemento.
O tipo abstrato de dados possuirá três operações: 1)construtor: cria as classes. 2)Find: determina o nome da classe de
equivalência de um elemento qualquer de D. 3)Uniao: une duas classes de nomes conhecidos.
O construtor cria uma classe de equivalência para cada elemento d distinto de D. Pós-Condição - Cada classe tem
apenas um elemento, d. O nome da classe de d é d.
Find
dado d de D, retorna o nome da classe de d.
Uniao
Dadas duas classes de nomes d1 e d2, realiza a união das duas classes de equivalência, adotando d1 ou d2
como nome da nova classe. As classes unidas deixam de existir.
Estruturas para classes de equivalência 43
Apresentação das soluções
Os algoritmos e estruturas de dados que provêm implementação eficientes desse tipo abstrato de dados são
conhecidos como algoritmos Union-Find (União-Busca), pelo tipo de operações que são providas. Outros nomes
encontrados são disjoint sets (conjuntos disjuntos) e dynamic equivalence relations (relações de equivalência
dinâmicas).
Existe basicamente duas estruturas de dados para implementar o tipo abstrato União-Busca: a baseada em listas, e a
baseada em árvores. A estrutura de dados linear, baseada em listas encadeadas, é mais apropriada para aplicações
onde o número de operações de união é pequeno com relação ao número de aplicações de busca. Em contrapartida, a
estrutura de dados ramificada, baseada em árvores, é mais eficiente quando o número de união é proporcionalmente
mais elevado que o número de buscas. A estrutura de dados baseada em árvores é fácil de implementar como um
vetor, sendo adotada por muitos autores. Além disso permite realizar as operações prasticamente em tempo
constante.
Fontes e Editores da Página 44
Fontes e Editores da Página
Objetivo  Fonte: http://pt.wikibooks.org/w/index.php?oldid=213130  Contribuidores: Atoj, Helder.wiki, 1 edições anónimas
O que é um Algoritmo?  Fonte: http://pt.wikibooks.org/w/index.php?oldid=249470  Contribuidores: Helder.wiki, Jorge Morais, 6 edições anónimas
Para que servem os algoritmos?  Fonte: http://pt.wikibooks.org/w/index.php?oldid=233099  Contribuidores: Jorge Morais, 3 edições anónimas
Sintaxe  Fonte: http://pt.wikibooks.org/w/index.php?oldid=213132  Contribuidores: Araruna, Helder.wiki, Jorge Morais, 3 edições anónimas
Recursividade  Fonte: http://pt.wikibooks.org/w/index.php?oldid=213131  Contribuidores: Araruna, Helder.wiki, Jorge Morais, Marcos Antônio Nunes de Moura, Master, 1 edições anónimas
Algoritmos de Ordenação  Fonte: http://pt.wikibooks.org/w/index.php?oldid=203734  Contribuidores: Master, 2 edições anónimas
Selection e Insertion  Fonte: http://pt.wikibooks.org/w/index.php?oldid=203747  Contribuidores: Giro720
O que são estruturas de dados?  Fonte: http://pt.wikibooks.org/w/index.php?oldid=112198  Contribuidores: Helder.wiki, Jorge Morais, Master, 2 edições anónimas
Abstração de Dados  Fonte: http://pt.wikibooks.org/w/index.php?oldid=211064  Contribuidores: Master, 1 edições anónimas
Vetores e Matrizes  Fonte: http://pt.wikibooks.org/w/index.php?oldid=260285  Contribuidores: Abacaxi, Helder.wiki, Infroger, Jorge Morais, LUISKISKIS, Master, Raylton P. Sousa, 16
edições anónimas
Estruturas  Fonte: http://pt.wikibooks.org/w/index.php?oldid=203740  Contribuidores: Master
Listas  Fonte: http://pt.wikibooks.org/w/index.php?oldid=254393  Contribuidores: Abacaxi, Master, RenatoResende, 1 edições anónimas
Pilhas  Fonte: http://pt.wikibooks.org/w/index.php?oldid=250754  Contribuidores: Abacaxi, Master, 7 edições anónimas
Filas  Fonte: http://pt.wikibooks.org/w/index.php?oldid=238486  Contribuidores: Master, 1 edições anónimas
Lista encadeada  Fonte: http://pt.wikibooks.org/w/index.php?oldid=235378  Contribuidores: Master, 2 edições anónimas
Tabela de Hash  Fonte: http://pt.wikibooks.org/w/index.php?oldid=203748  Contribuidores: Master
Árvore  Fonte: http://pt.wikibooks.org/w/index.php?oldid=225705  Contribuidores: Helder.wiki, Master, 2 edições anónimas
Árvores Binárias  Fonte: http://pt.wikibooks.org/w/index.php?oldid=248681  Contribuidores: Master, 2 edições anónimas
Árvores AVL  Fonte: http://pt.wikibooks.org/w/index.php?oldid=203736  Contribuidores: Master
Árvores Rubro-Negras  Fonte: http://pt.wikibooks.org/w/index.php?oldid=263992  Contribuidores: Master, Rotlink, 1 edições anónimas
Árvores B  Fonte: http://pt.wikibooks.org/w/index.php?oldid=245364  Contribuidores: Abacaxi, Master
Estruturas para classes de equivalência  Fonte: http://pt.wikibooks.org/w/index.php?oldid=248709