ED I - Heap Hashing

AVL
Arvora binária normal, porém tem graus em cada nó, que devem estar sempre entre -1 e 1
Balancear Árvore (Metalinguagem)
Verifica se x (valor inserido) está na árvore
Se sim, encerra
Se não,
Insere o valor x no local correto na árvore binária
Verifica se surgiu algum nó desregulado
Se sim,
Faça rebalanceamento
Encerra.
Se não, Encerra.
HEAP
(1)
(2)
(3)

valor de cada nó não é menor que os valores armazenados em cada um dos filhos árvore perfeitamente balanceada e as folhas no ultimo nível estão à esquerda na hora de remover, remove-se da direita para a esquerda. Fila de prioridades
•
Lista não ordenada – não exige esforço na inserção, mas exigirá na remoção e alteração, já que terá que procurar o elemento.
•
Lista ordenada – facilita remoção, mas dificulta inserção e alteração.
•
Arvore binária – facilita remoção, inserção e alteração, mas é muito sofisticada para implementar fila de prioridades
•
Heap – implementação útil por que as operações são otimizadas. Inserção O(n), remoção (1), alteração
O(n) e construção O(n logn)

HASHING
Métodos
Divisão inteira : H(x) = resto(X / M)
Enlaçamento: divide a chave em várias partes homogêneas de tamanho fixo. Enlaçamento deslocado soma estas partes. No enlaçamento limite, coloca-se em certa ordem, como um papel dobrado. Dobra: separa os dígitos e vai somando os extremos, até que essa soma seja menor que o tamanho da tabela
Meio-quadrado: calcula-se o quadrado da chave e pega uma parte do meio do numero.
Extração: Se pega parte da chave pra calcular endereço. Podem-se combinar dígitos a fim de obter uma chave eficiente.
Transformação da raiz: Escolhemos uma base, então convertemos a chave para ela. Depois dividimos pelo tamanho da tabela, e pegamos o resto dessa divisão.
Alfanumérica: soma os valores ASCII dos caracteres. Podemos utilizar também deslocamento de bits, onde a posição do caractere na palavra será responsável por um deslocamento x, que vai de 0 a N.