Estrutura de Dados

UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE
CENTRO DE ENSINO SUPERIOR DO SERIDÓ
DEPARTAMENTO DE CIÊNCIAS EXATAS E APLICADAS
PROGRAMA DE GRADUAÇÃO EM SISTEMAS DE INFORMAÇÃO

MARCELO AUGUSTO

RELATÓRIO DE ESTRUTURA DE DADOS

Caicó – RN
2014

Sumário
Lista encadeada................................................................................................................. 2
Árvore binária ................................................................................................................... 3
Árvore Balanceada (ou AVL)........................................................................................... 4
Tabela Hash ...................................................................................................................... 5

1

Lista encadeada
Organizam de forma linear e dinâmica, tanto no pior quanto no médio caso. Dinâmico por que as listas crescem e decrescem à medida que o programa precisa.

2

Árvore binária
A operação de busca em uma árvore binária é igual ao número de nós existentes no caminho desde a raiz da árvore até o nó procurado. Em uma árvore binária genérica, no pior caso, esse nó se encontra a uma distância O(n). Conclui-se então que a complexidade de busca corresponde à altura da árvore. No médio caso, em que uma árvore pode possuir altura mínima, que é o caso de uma árvore binária completa, o tempo de busca é O(log n).

3

Árvore Balanceada (ou AVL)
As operações de busca, inserção e remoção de elementos possuem complexidade O(log
n) (onde n é o número de elementos da árvore).
Uma árvore está balanceada quando, para cada nó da árvore, a diferença entre as alturas das sub-árvores não é maior do que um.

4

Tabela Hash
A função Hash é responsável pela distribuição das informações pela tabela. Ela é utilizada para associar cada dado à uma posição da tabela.
Na tabela hash implementada com lista encadeada para tratamento de colisão, a operação de inserção gasta tempo