Hash Table Tree - Tabela Hash com colisao Arvore Binaria em Java

HashTableTree.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");
  }
}