Please enable JavaScript.
Coggle requires JavaScript to display documents.
Estrutura de dados: árvores de busca (Tabelas HASH (os dois métodos de…
Estrutura de dados: árvores de busca
Introdução
necessidade: desenvolver algoritmos eficientes na tarefa de recuperar informações a partir de grande quantidade de dados.
ex. consulta de passagens aéreas e consulta de dados pessoais em bases governamentais.
registros, cada registro possui uma chave para ser usada na pesquisa.
grande quantidade de métodos de busca; a escolha do método depende: 1) da quantidade de dados e 2) arquivo sujeito a inserções e remoções frequentes/arquivo estável.
Árvores binárias de busca sem balanceamento
Árvore binária
nó raiz
duas sub-árvores (esquerda e direita do nó raiz)
cada nó tem no máximo duas sub-árvores
Árvore binária de pesquisa
todo nó interno (não raiz nem folha) contém um registro
propriedade: todos os registros com chaves menores estão na sub-árvore esquerda e todos os registros com chaves maiores estão na sub-árvore direita.
Algoritmo para encontrar o registro que contem a chave de busca passada como parâmetro em reg:
compare a chave de busca com a chave do registro que está na raiz.
Se é menor, vá para a subárvore esquerda.
Se é maior, vá para a subárvore direita.
repita o processo recursivamente até que a chave seja encontrada ou então um nó folha seja atingido
se a pesquisa tiver sucesso, então o registro contendo a chave passada em reg é retornado
melhor caso: C(n)=O(1); pior caso: C(n)=O(n); caso médio: C(n)=O(log n)
Árvores binárias de busca com balanceamento
a árvore completamente balanceada minimiza o tempo médio de pesquisa
entretanto, o custo para manter a árvore completamente balanceada após cada inserção é muito alta
uma forma de contornar esse problema é procurar uma solução intermediária que possa manter a árvore "quase balanceada"
Árvores rubro-negra
I. um nó é vermelho ou preto
II. a raiz é preta
III. todas as folhas (ponteiros para NULL) são pretas
IV. ambos os filhos de todos os nós vermelhos são pretos
V. todo caminho de um dado nó para qualquer de seus nós folhas descendentes contem o mesmo número de nós pretos
Essas regras asseguram uma propriedade crítica das árvores rubro-negras: que o caminho mais longo da raiz a qualquer folha não seja mais do que duas vezes o caminho mais curto da raiz a qualquer outra folha naquela árvore
O resultado é que a árvore é aproximadamente balanceada
buscas, inserções e remoções: O(log n) no pior caso
Tabelas HASH
os dois métodos de busca citados até aqui usa o princípio de procurar a informação desejada com base na comparação de suas chaves
métodos de buscas eficientes de busca têm custo O(log n), sendo que é necessário considerar o custo extra de ordenação: O(n log n) para algoritmos eficientes
busca ideal: acessar o elemento procurado de forma direta, sem comparação de chave, ou seja, há um custo de O(1)
representado pelo acesso a um registro de um vetor usando diretamente o índice
por meio de uma função hash os registros são espalhados na tabela
assim, por meio de uma transformação realizada a partir da chave é possível acessar de forma rápida uma determinada posição do "vetor"
na média, essa operação tem custo O(1)
o mais importante nessa estrutura é tratar as possíveis colisões (elementos tentando ocupar a mesma posição na tabela)
