RBT.java

 #RED BLACK TREE
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Random;
import java.util.Date;

class ConsoleReader
{
    public ConsoleReader(InputStream inStream)
    {
       reader = new BufferedReader
           (new InputStreamReader(inStream));
        }
        public int readInt()
        {
          String inputString = readLine();
       int n = Integer.parseInt(inputString);
       return n;
    }

    public String readLine()
    {
       String inputLine = "";
        try {
            inputLine=reader.readLine();
        }
        catch (IOException e) {
            System.out.println(e);
            System.exit(1);
        }
        return inputLine;
    }
  private BufferedReader reader;
}
class Node
  {
    String color;
    Node left;
    Node parent;
    Node right;
    int value;
    public Node(int value,String color)
    {
      this.value = value;
      this.color=color;
     }
    public Node()
    {
    this.color="Black";
    }
  }
public class RedBlackTree
{
 public static void main(String[] args)
    {
     ConsoleReader console=new ConsoleReader(System.in);
         int root_inp;
     int num;

     System.out.println("Please enter the number of input integers you give :");
         num=console.readInt();
     System.out.println("Please enter the root of binary tree :");

     root_inp=console.readInt();
         Node root = new Node(root_inp,"Black");

         Date d1=new Date();
         long buildTimeS=d1.getTime();
         System.out.println("Building Red Black Tree with root  "+root_inp+"   Please wait......");
         root=build(num,root);
         Date d2=new Date();
     long buildTimeE=d2.getTime();
     long sTimeS=d2.getTime();

         search(num,root,false);
     Date d3=new Date();
         long sTimeE=d3.getTime();
         search(num,root,true);
         Date d4=new Date();
         long spTimeE=d4.getTime();
     System.out.println("Red Black tree with number of input : " +num+"  and initial root :  "+root_inp);
     System.out.println("log(num) :  "+(Math.log(num)/2.303));

         System.out.println(" Time taken in building the Red Black tree is :  "+(buildTimeE-buildTimeS));
     System.out.println("Time taken in searching :  "+(sTimeE-sTimeS));
         System.out.println("Time taken in searching and finding predecessor is:"+(spTimeE-sTimeE));

    }
 public static Node build(int num,Node root)
  {
     Random generator = new Random();
      ConsoleReader console=new ConsoleReader(System.in);

    int node;
           int i = num;
      System.out.println("What do you want 1:Give all input manually 2:Give input through random number generator. Enter 1 or 2 ?");
      int opt=console.readInt();
      if(opt==1){
          System.out.println("Please enter the numbers press enter after each number : \n");
          for (i=1;i<(num+1);i++)
          {
              System.out.println("\n "+i +": ");
              node=console.readInt();
              System.out.println("read: " +node);
              insert(root,node);
          }
      }//end if
else {

    for (i=1;i<(num+1);i++)
        {
             node = generator.nextInt( 65536 );
             root=insert(root,node);
            }
}
    return root;
  }
 public static Node insert(Node node, int value)
  {   String color="Red";
    Node root=node;

        if (value < node.value)
      {
           if (node.left != null)
                 root=insert(node.left, value,root);
           else
       {
            node.left = new Node(value,color);
        ((node.left).parent)=node;

        root=RB_Insert(node.left,root);
      }
      }
      else if (value > node.value)
      {
            if (node.right != null)
            root=insert(node.right, value,root);
            else{
                 node.right = new Node(value,color);
               node.right.parent=node;

        root=RB_Insert(node.right,root);
               }
      }
      return root;
  }
 public static Node insert(Node node, int value,Node root)
  {   String color="Red";

        if (value < node.value)
      {
           if (node.left != null)
                 root=insert(node.left, value,root);
           else
           {
                node.left = new Node(value,color);
                ((node.left).parent)=node;

                root=RB_Insert(node.left,root);
           }
      }
      else if (value > node.value)
      {
            if (node.right != null)
                root=insert(node.right, value,root);
            else{
                node.right = new Node(value,color);
               ((node.right).parent)=node;

                root=RB_Insert(node.right,root);
        }

      }
      return root;
 }
 public static Node RB_Insert(Node node,Node root)
  {
    while(((node.parent).color).equals("Red")&&(node.value !=root.value))    //node and its parent both are red
    {
        Node y;
        // write the code if there is no uncle
        if((((node.parent).parent).right)==null)                //node's parent is left child of its parent
         {
             if(node==((node.parent).right))                        // node is right child
            {
                node=node.parent;
                root=LeftRotate(node,root);
                node.parent.color="Black";
                node.parent.parent.color="Red";
                root=RightRotate(node.parent.parent,root);
            }
            else                                                     // node is left child
            {
                node.parent.color="Black";
                node.parent.parent.color="Red";
                root=RightRotate(node.parent.parent,root);
            }
        }
        else if((((node.parent).parent).left)==null)            //node's parent is right child
        {
            if(node==((node.parent).left))                        // node is left child
            {
                node=node.parent;
                root=RightRotate(node,root);
                node.parent.color="Black";
                node.parent.parent.color="Red";
                root=LeftRotate(node.parent.parent,root);
            }
            else                                                     //node is right child
            {
                node.parent.color="Black";
                node.parent.parent.color="Red";
                root=LeftRotate(node.parent.parent,root);
            }
        }
        else if(node.parent==(((node.parent).parent).left))    //node's parent is left child of its parent
        {

            y= (((node.parent).parent).right);
            if((y.color).equals("Red"))                                    //node's uncle is also red
            {
                (((node.parent).parent).color)="Red";
                ((node.parent).color)="Black";
                ((((node.parent).parent).right).color)="Black";

                if(node.parent.parent.value==root.value)
                {
                    node.parent.parent.color="Black";
                    break;
                }
                node=((node.parent).parent);
            }
            else
            {
                 if(node==((node.parent).right))                        //node's uncle is not red but node is right child
                {
                    node=node.parent;
                    root=LeftRotate(node,root);
                }
                node.parent.parent.color="Red";
                node.parent.color="Black";
                root=RightRotate(node.parent.parent,root);
            }
        }
        else
        {
            y= (((node.parent).parent).left);
            if((y.color).equals("Red"))                                    //node's uncle is also red
            {
                (((node.parent).parent).color)="Red";
                ((node.parent).color)="Black";
                ((((node.parent).parent).left).color)="Black";

                if(node.parent.parent.value==root.value)
                {
                    node.parent.parent.color="Black";
                    break;
                }
                node=((node.parent).parent);
            }
            else
            {
                 if(node==((node.parent).left))                        //node's uncle is not red but node is left child
                {
                    node=node.parent;
                    root=RightRotate(node,root);
                }
                node.parent.parent.color="Red";
                node.parent.color="Black";
                root=LeftRotate(node.parent.parent,root);
            }
        }

    }
    return root;
 }
 public static Node LeftRotate(Node node,Node root)
 {
    Node y=node.right;                                   // see for null
    node.right=y.left;
    if(y.left!=null)
        y.left.parent=node;
    y.parent=node.parent;
    if(node.parent==null)      // node is root
        root=y;

    else
    {
         if(node==node.parent.left)
            node.parent.left=y;
        else
            node.parent.right=y;
    }
    node.parent=y;
    y.left=node;
    return root;
 }
 public static Node RightRotate(Node node,Node root)
 {
    Node y=node.left;
    node.left=y.right;
    if(y.right!=null)
        y.right.parent=node;
    y.parent=node.parent;
    if(node.parent==null)
        root=y;

    else
    {
         if(node==node.parent.right)
            node.parent.right=y;
        else
            node.parent.left=y;
    }
    node.parent=y;
    y.right=node;
    return root;
 }

  public static void search(int num,Node root,boolean flag)
  {
       Random generator = new Random();
       int i = num;

       for (i=1;i<(num+1);i++)
    {
        int a = generator.nextInt(65536);
        searchfor(a,root,flag);
    }
  }
  public static void searchfor(int b,Node node,boolean flag)
  {
    if ( node!=null)
    {
        if(node.value==b)
        {
            //System.out.print("found  "+b+"  ");
            if(flag)
            {
                //System.out.print("found  "+b+"  ");
                findPredecessor(node);
            }
        }
        else if(node.value>b)
            searchfor(b,node.left,flag);
        else
            searchfor(b,node.right,flag);
    }
    //else{}
    //    System.out.print("not found  "+b+"   " );
  }
public static void findPredecessor(Node node)
  {
      if(node.left!=null)
    findMax(node.left);
    else
     {
        Node x=node;
         if(x.parent!=null)
         {
                 while ((x!= null))
                {
                if(x.parent==null)
                {
                    //System.out.print("predecessor is null ");
                    break;
                }
                else if(x!=(x.parent).left)
                {
                    //System.out.println(" predecessor is  "+(x.parent).value);
                    break;
                }
                else
                x=x.parent;
            }
        }
    }
 }
 public static void findMax(Node node)
 {
    if (node.right==null)
    System.out.println("Predecessor is:  "+ node.value);
    else findMax(node.right);
  }
}