Java Program to Implement Red Black Tree

This is a Java Program to implement Red Black Tree. A red–black tree is a type of self-balancing binary search tree. The self-balancing is provided by painting each node with one of two colors (these are typically called ‘red’ and ‘black’, hence the name of the trees) in such a way that the resulting painted tree satisfies certain properties that don’t allow it to become significantly unbalanced. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently. This program is based on the implementation by Mark Allen Weiss.

Here is the source code of the Java program to implement Red Black Tree. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /*
  2.  *  Java Program to Implement Red Black Tree
  3.  */
  4.  
  5.  import java.util.Scanner;
  6.  
  7.  /* Class Node */
  8.  class RedBlackNode
  9.  {    
  10.      RedBlackNode left, right;
  11.      int element;
  12.      int color;
  13.  
  14.      /* Constructor */
  15.      public RedBlackNode(int theElement)
  16.      {
  17.          this( theElement, null, null );
  18.      } 
  19.      /* Constructor */
  20.      public RedBlackNode(int theElement, RedBlackNode lt, RedBlackNode rt)
  21.      {
  22.          left = lt;
  23.          right = rt;
  24.          element = theElement;
  25.          color = 1;
  26.      }    
  27.  }
  28.  
  29.  /* Class RBTree */
  30.  class RBTree
  31.  {
  32.      private RedBlackNode current;
  33.      private RedBlackNode parent;
  34.      private RedBlackNode grand;
  35.      private RedBlackNode great;
  36.      private RedBlackNode header;    
  37.      private static RedBlackNode nullNode;
  38.      /* static initializer for nullNode */
  39.      static 
  40.      {
  41.          nullNode = new RedBlackNode(0);
  42.          nullNode.left = nullNode;
  43.          nullNode.right = nullNode;
  44.      }
  45.      /* Black - 1  RED - 0 */
  46.      static final int BLACK = 1;    
  47.      static final int RED   = 0;
  48.  
  49.      /* Constructor */
  50.      public RBTree(int negInf)
  51.      {
  52.          header = new RedBlackNode(negInf);
  53.          header.left = nullNode;
  54.          header.right = nullNode;
  55.      }
  56.      /* Function to check if tree is empty */
  57.      public boolean isEmpty()
  58.      {
  59.          return header.right == nullNode;
  60.      }
  61.      /* Make the tree logically empty */
  62.      public void makeEmpty()
  63.      {
  64.          header.right = nullNode;
  65.      }
  66.      /* Function to insert item */
  67.      public void insert(int item )
  68.      {
  69.          current = parent = grand = header;
  70.          nullNode.element = item;
  71.          while (current.element != item)
  72.          {            
  73.              great = grand; 
  74.              grand = parent; 
  75.              parent = current;
  76.              current = item < current.element ? current.left : current.right;
  77.              // Check if two red children and fix if so            
  78.              if (current.left.color == RED && current.right.color == RED)
  79.                  handleReorient( item );
  80.          }
  81.          // Insertion fails if already present
  82.          if (current != nullNode)
  83.              return;
  84.          current = new RedBlackNode(item, nullNode, nullNode);
  85.          // Attach to parent
  86.          if (item < parent.element)
  87.              parent.left = current;
  88.          else
  89.              parent.right = current;        
  90.          handleReorient( item );
  91.      }
  92.      private void handleReorient(int item)
  93.      {
  94.          // Do the color flip
  95.          current.color = RED;
  96.          current.left.color = BLACK;
  97.          current.right.color = BLACK;
  98.  
  99.          if (parent.color == RED)   
  100.          {
  101.              // Have to rotate
  102.              grand.color = RED;
  103.              if (item < grand.element != item < parent.element)
  104.                  parent = rotate( item, grand );  // Start dbl rotate
  105.              current = rotate(item, great );
  106.              current.color = BLACK;
  107.          }
  108.          // Make root black
  109.          header.right.color = BLACK; 
  110.      }      
  111.      private RedBlackNode rotate(int item, RedBlackNode parent)
  112.      {
  113.          if(item < parent.element)
  114.              return parent.left = item < parent.left.element ? rotateWithLeftChild(parent.left) : rotateWithRightChild(parent.left) ;  
  115.          else
  116.              return parent.right = item < parent.right.element ? rotateWithLeftChild(parent.right) : rotateWithRightChild(parent.right);  
  117.      }
  118.      /* Rotate binary tree node with left child */
  119.      private RedBlackNode rotateWithLeftChild(RedBlackNode k2)
  120.      {
  121.          RedBlackNode k1 = k2.left;
  122.          k2.left = k1.right;
  123.          k1.right = k2;
  124.          return k1;
  125.      }
  126.      /* Rotate binary tree node with right child */
  127.      private RedBlackNode rotateWithRightChild(RedBlackNode k1)
  128.      {
  129.          RedBlackNode k2 = k1.right;
  130.          k1.right = k2.left;
  131.          k2.left = k1;
  132.          return k2;
  133.      }
  134.      /* Functions to count number of nodes */
  135.      public int countNodes()
  136.      {
  137.          return countNodes(header.right);
  138.      }
  139.      private int countNodes(RedBlackNode r)
  140.      {
  141.          if (r == nullNode)
  142.              return 0;
  143.          else
  144.          {
  145.              int l = 1;
  146.              l += countNodes(r.left);
  147.              l += countNodes(r.right);
  148.              return l;
  149.          }
  150.      }
  151.      /* Functions to search for an element */
  152.      public boolean search(int val)
  153.      {
  154.          return search(header.right, val);
  155.      }
  156.      private boolean search(RedBlackNode r, int val)
  157.      {
  158.          boolean found = false;
  159.          while ((r != nullNode) && !found)
  160.          {
  161.              int rval = r.element;
  162.              if (val < rval)
  163.                  r = r.left;
  164.              else if (val > rval)
  165.                  r = r.right;
  166.              else
  167.              {
  168.                  found = true;
  169.                  break;
  170.              }
  171.              found = search(r, val);
  172.          }
  173.          return found;
  174.      }
  175.      /* Function for inorder traversal */ 
  176.      public void inorder()
  177.      {
  178.          inorder(header.right);
  179.      }
  180.      private void inorder(RedBlackNode r)
  181.      {
  182.          if (r != nullNode)
  183.          {
  184.              inorder(r.left);
  185.              char c = 'B';
  186.              if (r.color == 0)
  187.                  c = 'R';
  188.              System.out.print(r.element +""+c+" ");
  189.              inorder(r.right);
  190.          }
  191.      }
  192.      /* Function for preorder traversal */
  193.      public void preorder()
  194.      {
  195.          preorder(header.right);
  196.      }
  197.      private void preorder(RedBlackNode r)
  198.      {
  199.          if (r != nullNode)
  200.          {
  201.              char c = 'B';
  202.              if (r.color == 0)
  203.                  c = 'R';
  204.              System.out.print(r.element +""+c+" ");
  205.              preorder(r.left);             
  206.              preorder(r.right);
  207.          }
  208.      }
  209.      /* Function for postorder traversal */
  210.      public void postorder()
  211.      {
  212.          postorder(header.right);
  213.      }
  214.      private void postorder(RedBlackNode r)
  215.      {
  216.          if (r != nullNode)
  217.          {
  218.              postorder(r.left);             
  219.              postorder(r.right);
  220.              char c = 'B';
  221.              if (r.color == 0)
  222.                  c = 'R';
  223.              System.out.print(r.element +""+c+" ");
  224.          }
  225.      }     
  226.  }
  227.  
  228.  /* Class RedBlackTreeTest */
  229.  public class RedBlackTreeTest
  230.  {
  231.      public static void main(String[] args)
  232.      {            
  233.         Scanner scan = new Scanner(System.in);
  234.         /* Creating object of RedBlack Tree */
  235.         RBTree rbt = new RBTree(Integer.MIN_VALUE); 
  236.         System.out.println("Red Black Tree Test\n");          
  237.         char ch;
  238.         /*  Perform tree operations  */
  239.         do    
  240.         {
  241.             System.out.println("\nRed Black Tree Operations\n");
  242.             System.out.println("1. insert ");
  243.             System.out.println("2. search");
  244.             System.out.println("3. count nodes");
  245.             System.out.println("4. check empty");
  246.             System.out.println("5. clear tree");
  247.  
  248.             int choice = scan.nextInt();            
  249.             switch (choice)
  250.             {
  251.             case 1 : 
  252.                 System.out.println("Enter integer element to insert");
  253.                 rbt.insert( scan.nextInt() );                     
  254.                 break;                          
  255.             case 2 : 
  256.                 System.out.println("Enter integer element to search");
  257.                 System.out.println("Search result : "+ rbt.search( scan.nextInt() ));
  258.                 break;                                          
  259.             case 3 : 
  260.                 System.out.println("Nodes = "+ rbt.countNodes());
  261.                 break;     
  262.             case 4 : 
  263.                 System.out.println("Empty status = "+ rbt.isEmpty());
  264.                 break;     
  265.             case 5 : 
  266.                 System.out.println("\nTree Cleared");
  267.                 rbt.makeEmpty();
  268.                 break;         
  269.             default : 
  270.                 System.out.println("Wrong Entry \n ");
  271.                 break;    
  272.             }
  273.             /*  Display tree  */
  274.             System.out.print("\nPost order : ");
  275.             rbt.postorder();
  276.             System.out.print("\nPre order : ");
  277.             rbt.preorder();
  278.             System.out.print("\nIn order : ");
  279.             rbt.inorder(); 
  280.  
  281.             System.out.println("\nDo you want to continue (Type y or n) \n");
  282.             ch = scan.next().charAt(0);                        
  283.         } while (ch == 'Y'|| ch == 'y');               
  284.      }
  285.  }

Red Black Tree Test
 
 
Red Black Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
4
Empty status = true
 
Post order :
Pre order :
In order :
Do you want to continue (Type y or n)
 
y
 
Red Black Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
8
 
Post order : 8B
Pre order : 8B
In order : 8B
Do you want to continue (Type y or n)
 
y
 
Red Black Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
3
 
Post order : 3R 8B
Pre order : 8B 3R
In order : 3R 8B
Do you want to continue (Type y or n)
 
y
 
Red Black Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
5
 
Post order : 3R 8R 5B
Pre order : 5B 3R 8R
In order : 3R 5B 8R
Do you want to continue (Type y or n)
 
y
 
Red Black Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
2
 
Post order : 2R 3B 8B 5B
Pre order : 5B 3B 2R 8B
In order : 2R 3B 5B 8B
Do you want to continue (Type y or n)
 
y
 
Red Black Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
1
 
Post order : 1R 3R 2B 8B 5B
Pre order : 5B 2B 1R 3R 8B
In order : 1R 2B 3R 5B 8B
Do you want to continue (Type y or n)
 
y
 
Red Black Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
9
 
Post order : 1R 3R 2B 9R 8B 5B
Pre order : 5B 2B 1R 3R 8B 9R
In order : 1R 2B 3R 5B 8B 9R
Do you want to continue (Type y or n)
 
y
 
Red Black Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
10
 
Post order : 1R 3R 2B 8R 10R 9B 5B
Pre order : 5B 2B 1R 3R 9B 8R 10R
In order : 1R 2B 3R 5B 8R 9B 10R
Do you want to continue (Type y or n)
 
y
 
Red Black Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
3
Nodes = 7
 
Post order : 1R 3R 2B 8R 10R 9B 5B
Pre order : 5B 2B 1R 3R 9B 8R 10R
In order : 1R 2B 3R 5B 8R 9B 10R
Do you want to continue (Type y or n)
 
y
 
Red Black Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
2
Enter integer element to search
4
Search result : false
 
Post order : 1R 3R 2B 8R 10R 9B 5B
Pre order : 5B 2B 1R 3R 9B 8R 10R
In order : 1R 2B 3R 5B 8R 9B 10R
Do you want to continue (Type y or n)
 
y
 
Red Black Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
2
Enter integer element to search
6
Search result : false
 
Post order : 1R 3R 2B 8R 10R 9B 5B
Pre order : 5B 2B 1R 3R 9B 8R 10R
In order : 1R 2B 3R 5B 8R 9B 10R
Do you want to continue (Type y or n)
 
y
 
Red Black Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
2
Enter integer element to search
3
Search result : true
 
Post order : 1R 3R 2B 8R 10R 9B 5B
Pre order : 5B 2B 1R 3R 9B 8R 10R
In order : 1R 2B 3R 5B 8R 9B 10R
Do you want to continue (Type y or n)
 
y
 
Red Black Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
5
 
Tree Cleared
 
Post order :
Pre order :
In order :
Do you want to continue (Type y or n)
 
y
 
Red Black Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
4
Empty status = true
 
Post order :
Pre order :
In order :
Do you want to continue (Type y or n)
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.