PLEASE SHOW HOW TO IMPLEMENT THE DELETION FUNCTION SAMPLE

( PLEASE SHOW HOW TO IMPLEMENT THE DELETION FUNCTION )

SAMPLE OUTPUT:

Instead of using a linked list to resolve collisions, as in separate chaining, use a binary search tree. That is, create a hash table that is an array of trees. You could use H(X) = X % arraysize as the hash function in your hash table implementation. The arraySize needs to be an input parameter from users. Your solution should support the basic hash table inserting, searching, and displaying functions. To display a small tree-based hash table, you could use an in-order traversal of each tree. The advantage of a tree over a linked list is that it can be searched in O(logN) instead of O(N) time. Checking 15 items takes a maximum of 15 comparisons in a list but only 4 in a tree. Duplicates can present problems in both trees and hash tables, so add some code that prevents a duplicate key from being inserted in the hash table. To shorten the listing for this program, you can forget about deletion, which for trees requires a lot of code. [ten bonus points will be given to those who implement the deletion function.]

Solution

import java.util.Scanner;
class BinaryNode
{
   BinaryNode lchild, rchild;
    int data;
    public BinaryNode(int d)
    {
        data = d;
        lchild = null;
        rchild = null;
    }
}

class HashTableusingBinaryTree
{
    private BinaryNode[] t;
    private int size ;

    public HashTableusingBinaryTree(int tableSize)
    {
        t = new BinaryNode[ nextPosition(tableSize) ];
        size = 0;
    }
    public boolean isEmpty()
    {
        return size == 0;
    }
    public void Empty()
    {
        int l = t.length;
        t = new BinaryNode[l];
        size = 0;
    }

    public int sizeofht()
    {
        return size;
    }
    public void insert(int val)
    {
        size++;
        int pos = myhashtable(val);      
        BinaryNode head = t[pos];
        head = insert(head, val);
        t[pos] = head;      
    }
    private BinaryNode insert(BinaryNode node, int data)
    {
        if (node == null)
            node = new BinaryNode(data);
        else
        {
            if (data <= node.data)
                node.lchild = insert(node.lchild, data);
            else
                node.rchild = insert(node.rchild, data);
        }
        return node;
    }
  
    public void remove(int val)
    {
        int pos = myhashtable(val);      
        BinaryNode head = t[pos];
        try
        {
           head = delete(head, val);  
            size--;
        }
        catch (Exception e)
        {
            System.out.println(\"\ Element not present\ \");      
        }      
        t[pos] = head;      
    }
  
    private BinaryNode delete(BinaryNode head, int k)
    {
       BinaryNode a, b, n;
        if (head.data == k)
        {
           BinaryNode lt, rt;
            lt = head.lchild;
            rt = head.rchild;
            if (lt == null && rt == null)
                return null;
            else if (lt == null)
            {
                a = rt;
                return a;
            }
            else if (rt == null)
            {
                a = lt;
                return a;
            }
            else
            {
                b = rt;
                a = rt;
                while (a.lchild != null)
                    a = a.lchild;
                a.lchild = lt;
                return b;
            }
        }
        if (k < head.data)
        {
            n = delete(head.lchild, k);
            head.lchild = n;
        }
        else
        {
            n = delete(head.rchild, k);
            head.rchild = n;           
        }
        return head;
    }

    private int myhashtable(Integer x )
    {
        int hashVal = x.hashCode( );
        hashVal %= t.length;
        if (hashVal < 0)
            hashVal += t.length;
        return hashVal;
    }

    private static int nextPosition( int r )
    {
        if (r % 2 == 0)
            r++;
        for ( ; !isnext( r ); r += 2);

        return r;
    }
    private static boolean isnext( int r )
    {
        if (r == 2 || r == 3)
            return true;
        if (r == 1 || r % 2 == 0)
            return false;
        for (int i = 3; i * i <= r; i += 2)
            if (r % i == 0)
                return false;
        return true;
    }
  
    public void displayhashtable ()
    {
        System.out.println();
        for (int i = 0; i < t.length; i++)
        {
            System.out.print ( i + \": \");          
            inorder(t[i]);
            System.out.println();
        }
    }
  
    private void inorder(BinaryNode r)
    {
        if (r != null)
        {
            inorder(r.lchild);
            System.out.print(r.data +\" \");
            inorder(r.rchild);
        }
    }   
}

public class hashtable
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        System.out.println(\"Enter size of hash table\");
         HashTableusingBinaryTree ht = new HashTableusingBinaryTree(sc.nextInt() );

        char ch;
        String choice=\"null\" ;
      
        do   
        {
           System.out.println(\"Enter first letter of insert,delete,cleare,empty,getsize,\");
           System.out.println(\"\ \");

            choice = sc.next();          
            switch (choice)
            {
            case \"i\" :
                System.out.println(\"Enter integer element to insert into hash table \ \");
                ht.insert( sc.nextInt() );
                break;                        
            case \"d\" :               
                System.out.println(\"Enter integer element to delete from hash table \ \");
                ht.remove( sc.nextInt() );
                break;                      
            case \"c\":
               ht.Empty();
                System.out.println(\"Cleared the hash table\ \");
                break;
            case \"g\" :
                System.out.println(\"Size of hash table is = \"+ ht.sizeofht() );
                break;
            case \"f\" :
               System.out.println(\"Enter integer element to find in hash table \ \");
                int val2=( sc.nextInt() );
                if(ht.equals(val2))
                       {
                   System.out.println(\"Element found\");
                       }
                else
                {
                   System.out.println(\"Element not found\");
                }
                break;     
              
                      
            case \"e\":
                System.out.println(\"Check hash table empty or not = \"+ ht.isEmpty() );
            case \"s\":
               ht.displayhashtable();
                break;      
            default :
                System.out.println(\"You entered undefined choice... \ \");
                break;  
            }
      
        } while (true);
    }
}