Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Hash Table Tree - Tabela Hash com colisao Arvore Binaria em Java
/* Criado por: profa. Divani Barbosa Gavinier
Curriculo Lattes: http://lattes.cnpq.br/8503400830635447
divanibarbosa@gmail.com
*/
import java.io.*; // pacote contem classe Scanner
import java.util.*; // pacote contem System.in
import java.lang.*;
class No {
public double item;
public No dir;
public No esq;
}
////////////////////////////////////////////////
class Tree {
private No root, atual; // raiz
boolean flag=true;
public Tree() { root=null; } // inicializa arvore
public void inserir_tree(double v) {
No novo = new No(); // cria um novo Nó
novo.item = v; // atribui o valor recebido ao item de dados do Nó
novo.dir = null;
novo.esq = null;
if (root == null) root = novo;
else { // se nao for a raiz
No atual = root;
No parente;
while(true) {
parente = atual;
if (v <= atual.item) { // ir para esquerda
atual = atual.esq;
if (atual == null) {
parente.esq = novo;
return;
}
} // fim da condição ir a esquerda
else { // ir para direita
atual = atual.dir;
if (atual == null) {
parente.dir = novo;
return;
}
} // fim da condição ir a direita
} // fim do laço while
} // fim do else não raiz
}
public boolean busca_tree(double chave) {
if (root == null) return false; // se arvore vazia
No atual = root; // começa a procurar desde raiz
while (atual.item != chave) { // enquanto nao encontrou
if(chave < atual.item ) atual = atual.esq; // caminha para esquerda
else atual = atual.dir; // caminha para direita
if (atual == null) return false; // encontrou uma folha -> sai
} // fim laço while
return true; // terminou o laço while e chegou aqui é pq encontrou item
}
public void apaga_tree(double v) {
if (root == null) return; // se arvore vazia
No atual = root;
No pai = root;
boolean filho_esq = true;
// ****** Buscando o valor **********
while (atual.item != v) { // enquanto nao encontrou
pai = atual;
if(v < atual.item ) { // caminha para esquerda
atual = atual.esq;
filho_esq = true; // é filho a esquerda? sim
}
else { // caminha para direita
atual = atual.dir;
filho_esq = false; // é filho a esquerda? NAO
}
if (atual == null) return; // encontrou uma folha -> sai
} // fim laço while de busca do valor
// **************************************************************
// se chegou aqui quer dizer que encontrou o valor (v)
// "atual": contem a referencia ao No a ser eliminado
// "pai": contem a referencia para o pai do No a ser eliminado
// "filho_esq": é verdadeiro se atual é filho a esquerda do pai
// **************************************************************
// Se nao possui nenhum filho (é uma folha), elimine-o
if (atual.esq == null && atual.dir == null) {
if (atual == root ) root = null; // se raiz
else if (filho_esq) pai.esq = null; // se for filho a esquerda do pai
else pai.dir = null; // se for filho a direita do pai
}
// Se é pai e nao possui um filho a direita, substitui pela subarvore a direita
else if (atual.dir == null) {
if (atual == root) root = atual.esq; // se raiz
else if (filho_esq) pai.esq = atual.esq; // se for filho a esquerda do pai
else pai.dir = atual.esq; // se for filho a direita do pai
}
// Se é pai e nao possui um filho a esquerda, substitui pela subarvore a esquerda
else if (atual.esq == null) {
if (atual == root) root = atual.dir; // se raiz
else if (filho_esq) pai.esq = atual.dir; // se for filho a esquerda do pai
else pai.dir = atual.dir; // se for filho a direita do pai
}
// Se possui mais de um filho, se for um avô ou outro grau maior de parentesco
else {
No sucessor = no_sucessor(atual);
// Usando sucessor que seria o Nó mais a esquerda da subarvore a direita do No que deseja-se remover
if (atual == root) root = sucessor; // se raiz
else if(filho_esq) pai.esq = sucessor; // se for filho a esquerda do pai
else pai.dir = sucessor; // se for filho a direita do pai
sucessor.esq = atual.esq; // acertando o ponteiro a esquerda do sucessor agora que ele assumiu
// a posição correta na arvore
}
}
// O sucessor é o Nó mais a esquerda da subarvore a direita do No que foi passado como parametro do metodo
public No no_sucessor(No apaga) { // O parametro é a referencia para o No que deseja-se apagar
No paidosucessor = apaga;
No sucessor = apaga;
No atual = apaga.dir; // vai para a subarvore a direita
while (atual != null) { // enquanto nao chegar no Nó mais a esquerda
paidosucessor = sucessor;
sucessor = atual;
atual = atual.esq; // caminha para a esquerda
}
// *********************************************************************************
// quando sair do while "sucessor" será o Nó mais a esquerda da subarvore a direita
// "paidosucessor" será o o pai de sucessor e "apaga" o Nó que deverá ser eliminado
// *********************************************************************************
if (sucessor != apaga.dir) { // se sucessor nao é o filho a direita do Nó que deverá ser eliminado
paidosucessor.esq = sucessor.dir; // pai herda os filhos do sucessor que sempre serão a direita
// lembrando que o sucessor nunca poderá ter filhos a esquerda, pois, ele sempre será o
// Nó mais a esquerda da subarvore a direita do Nó apaga.
// lembrando também que sucessor sempre será o filho a esquerda do pai
sucessor.dir = apaga.dir; // guardando o ponteiro a direita do sucessor para
// quando ele assumir a posição correta na arvore
}
return sucessor;
}
public void imprime_tree() { inOrder(root); }
private void inOrder(No atual) { // imprime em ordem (in Order)
if (atual != null) {
inOrder(atual.esq);
System.out.print(atual.item + " -> ");
inOrder(atual.dir);
}
}
}
////////////////////////////////////////////////
class HashTree {
private Tree[] tab;
private int TAM_MAX;
public HashTree(int tam) {
tab = new Tree[tam];
TAM_MAX = tam;
for(int i=0; i<tam; i++) // inicializando
tab[i] = null;
}
private int funcaohash(double chave) {
int v = (int) chave;
return ( Math.abs(v) % TAM_MAX );
}
public void insere(double item) {
int pos = funcaohash(item);
if ( tab[pos]==null ) tab[pos] = new Tree();
tab[pos].inserir_tree(item);
}
public void apaga(double chave) {
int pos = busca(chave);
if (pos != -1) tab[pos].apaga_tree(chave);
else System.out.println("\n Item nao encontrado");
}
public void imprime() {
for (int i=0; i<TAM_MAX; i++) {
System.out.print("\n HASH[" + i + "] -> ");
if ( tab[i]!=null ) tab[i].imprime_tree();
System.out.print("null");
}
}
public int busca(double chave) {
for (int i=0; i<TAM_MAX; i++)
if ( tab[i]!=null )
if ( tab[i].busca_tree(chave) ) return i;
return -1;
}
}
//////////////////////////////////////////////////////
class HashTableTree {
public static void main(String[] args) {
HashTree tab = new HashTree(7);
Scanner le = new Scanner(System.in);
double item;
System.out.println("\n******************************************************************************");
System.out.println("Tabela HASH com tratamento de colisoes Arvore Binaria (7 itens reais - double)");
System.out.println("******************************************************************************");
System.out.println(" Inserindo 10 elementos ");
for (int i=0; i<10; i++){
System.out.print(" Inserindo elemento " + (i+1) );
System.out.print(" - Forneca valor real: ");
item = le.nextDouble();
tab.insere(item);
}
System.out.print("\n Imprimindo conteudo");
tab.imprime();
while(true) {
System.out.print("\n\n>> Forneca o item que deseja apagar (-1 sai): ");
item = le.nextDouble();
if (item == -1) break;
tab.apaga(item);
tab.imprime();
}
System.out.println("\n");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment