Java Program to Implement Self Balancing Binary Search Tree

This is a Java Program to implement Self Balancing Binary Search Tree. A self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.
These structures provide efficient implementations for mutable ordered lists, and can be used for other abstract data structures such as associative arrays, priority queues and sets. The implementation of self balancing binary search tree is similar to that of a AVL Tree data structure.

Here is the source code of the Java program to implement Self Balancing Binary Search 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 Self Balancing Binary Search Tree
  3.  */
  4.  
  5.  import java.util.Scanner;
  6.  
  7.  /* Class SBBSTNode */
  8.  class SBBSTNode
  9.  {    
  10.      SBBSTNode left, right;
  11.      int data;
  12.      int height;
  13.  
  14.      /* Constructor */
  15.      public SBBSTNode()
  16.      {
  17.          left = null;
  18.          right = null;
  19.          data = 0;
  20.          height = 0;
  21.      }
  22.      /* Constructor */
  23.      public SBBSTNode(int n)
  24.      {
  25.          left = null;
  26.          right = null;
  27.          data = n;
  28.          height = 0;
  29.      }     
  30.  }
  31.  
  32.  /* Class SelfBalancingBinarySearchTree */
  33.  class SelfBalancingBinarySearchTree
  34.  {
  35.      private SBBSTNode root;     
  36.  
  37.      /* Constructor */
  38.      public SelfBalancingBinarySearchTree()
  39.      {
  40.          root = null;
  41.      }
  42.  
  43.      /* Function to check if tree is empty */
  44.      public boolean isEmpty()
  45.      {
  46.          return root == null;
  47.      }
  48.  
  49.      /* Make the tree logically empty */
  50.      public void clear()
  51.      {
  52.          root = null;
  53.      }
  54.      /* Function to insert data */
  55.      public void insert(int data)
  56.      {
  57.          root = insert(data, root);
  58.      }
  59.      /* Function to get height of node */
  60.      private int height(SBBSTNode t )
  61.      {
  62.          return t == null ? -1 : t.height;
  63.      }
  64.      /* Function to max of left/right node */
  65.      private int max(int lhs, int rhs)
  66.      {
  67.          return lhs > rhs ? lhs : rhs;
  68.      }
  69.      /* Function to insert data recursively */
  70.      private SBBSTNode insert(int x, SBBSTNode t)
  71.      {
  72.          if (t == null)
  73.              t = new SBBSTNode(x);
  74.          else if (x < t.data)
  75.          {
  76.              t.left = insert( x, t.left );
  77.              if (height( t.left ) - height( t.right ) == 2)
  78.                  if (x < t.left.data)
  79.                      t = rotateWithLeftChild( t );
  80.                  else
  81.                      t = doubleWithLeftChild( t );
  82.          }
  83.          else if (x > t.data)
  84.          {
  85.              t.right = insert( x, t.right );
  86.              if (height( t.right ) - height( t.left ) == 2)
  87.                  if (x > t.right.data)
  88.                      t = rotateWithRightChild( t );
  89.                  else
  90.                      t = doubleWithRightChild( t );
  91.          }
  92.          else
  93.            ;  // Duplicate; do nothing
  94.          t.height = max( height( t.left ), height( t.right ) ) + 1;
  95.          return t;
  96.      }
  97.      /* Rotate binary tree node with left child */     
  98.      private SBBSTNode rotateWithLeftChild(SBBSTNode k2)
  99.      {
  100.          SBBSTNode k1 = k2.left;
  101.          k2.left = k1.right;
  102.          k1.right = k2;
  103.          k2.height = max( height( k2.left ), height( k2.right ) ) + 1;
  104.          k1.height = max( height( k1.left ), k2.height ) + 1;
  105.          return k1;
  106.      }
  107.  
  108.      /* Rotate binary tree node with right child */
  109.      private SBBSTNode rotateWithRightChild(SBBSTNode k1)
  110.      {
  111.          SBBSTNode k2 = k1.right;
  112.          k1.right = k2.left;
  113.          k2.left = k1;
  114.          k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
  115.          k2.height = max( height( k2.right ), k1.height ) + 1;
  116.          return k2;
  117.      }
  118.      /**
  119.       * Double rotate binary tree node: first left child
  120.       * with its right child; then node k3 with new left child */
  121.      private SBBSTNode doubleWithLeftChild(SBBSTNode k3)
  122.      {
  123.          k3.left = rotateWithRightChild( k3.left );
  124.          return rotateWithLeftChild( k3 );
  125.      }
  126.      /**
  127.       * Double rotate binary tree node: first right child
  128.       * with its left child; then node k1 with new right child */      
  129.      private SBBSTNode doubleWithRightChild(SBBSTNode k1)
  130.      {
  131.          k1.right = rotateWithLeftChild( k1.right );
  132.          return rotateWithRightChild( k1 );
  133.      }    
  134.      /* Functions to count number of nodes */
  135.      public int countNodes()
  136.      {
  137.          return countNodes(root);
  138.      }
  139.      private int countNodes(SBBSTNode r)
  140.      {
  141.          if (r == null)
  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(root, val);
  155.      }
  156.      private boolean search(SBBSTNode r, int val)
  157.      {
  158.          boolean found = false;
  159.          while ((r != null) && !found)
  160.          {
  161.              int rval = r.data;
  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(root);
  179.      }
  180.      private void inorder(SBBSTNode r)
  181.      {
  182.          if (r != null)
  183.          {
  184.              inorder(r.left);
  185.              System.out.print(r.data +" ");
  186.              inorder(r.right);
  187.          }
  188.      }
  189.      /* Function for preorder traversal */
  190.      public void preorder()
  191.      {
  192.          preorder(root);
  193.      }
  194.      private void preorder(SBBSTNode r)
  195.      {
  196.          if (r != null)
  197.          {
  198.              System.out.print(r.data +" ");
  199.              preorder(r.left);             
  200.              preorder(r.right);
  201.          }
  202.      }
  203.      /* Function for postorder traversal */
  204.      public void postorder()
  205.      {
  206.          postorder(root);
  207.      }
  208.      private void postorder(SBBSTNode r)
  209.      {
  210.          if (r != null)
  211.          {
  212.              postorder(r.left);             
  213.              postorder(r.right);
  214.              System.out.print(r.data +" ");
  215.          }
  216.      }     
  217.  }
  218.  
  219.  /* Class SelfBalancingBinarySearchTreeTest */
  220. public class SelfBalancingBinarySearchTreeTest
  221. {
  222.     public static void main(String[] args)
  223.     {            
  224.         Scanner scan = new Scanner(System.in);
  225.         /* Creating object of SelfBalancingBinarySearchTree */
  226.         SelfBalancingBinarySearchTree sbbst = new SelfBalancingBinarySearchTree(); 
  227.         System.out.println("SelfBalancingBinarySearchTree Test\n");          
  228.         char ch;
  229.         /*  Perform tree operations  */
  230.         do    
  231.         {
  232.             System.out.println("\nSelfBalancingBinarySearchTree Operations\n");
  233.             System.out.println("1. insert ");
  234.             System.out.println("2. search");
  235.             System.out.println("3. count nodes");
  236.             System.out.println("4. check empty");
  237.             System.out.println("5. clear tree");
  238.  
  239.             int choice = scan.nextInt();            
  240.             switch (choice)
  241.             {
  242.             case 1 : 
  243.                 System.out.println("Enter integer element to insert");
  244.                 sbbst.insert( scan.nextInt() );                     
  245.                 break;                          
  246.             case 2 : 
  247.                 System.out.println("Enter integer element to search");
  248.                 System.out.println("Search result : "+ sbbst.search( scan.nextInt() ));
  249.                 break;                                          
  250.             case 3 : 
  251.                 System.out.println("Nodes = "+ sbbst.countNodes());
  252.                 break;     
  253.             case 4 : 
  254.                 System.out.println("Empty status = "+ sbbst.isEmpty());
  255.                 break;     
  256.             case 5 : 
  257.                 System.out.println("\nTree Cleared");
  258.                 sbbst.clear();
  259.                 break;         
  260.             default : 
  261.                 System.out.println("Wrong Entry \n "); 
  262.                 break;   
  263.             }
  264.             /*  Display tree  */  
  265.             System.out.print("\nPost order : ");
  266.             sbbst.postorder();
  267.             System.out.print("\nPre order : ");
  268.             sbbst.preorder();
  269.             System.out.print("\nIn order : ");
  270.             sbbst.inorder();
  271.  
  272.             System.out.println("\nDo you want to continue (Type y or n) \n");
  273.             ch = scan.next().charAt(0);                        
  274.         } while (ch == 'Y'|| ch == 'y');               
  275.     }
  276. }

SelfBalancingBinarySearchTree Test
 
 
SelfBalancingBinarySearchTree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
5
 
Post order : 5
Pre order : 5
In order : 5
Do you want to continue (Type y or n)
 
y
 
SelfBalancingBinarySearchTree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
8
 
Post order : 8 5
Pre order : 5 8
In order : 5 8
Do you want to continue (Type y or n)
 
y
 
SelfBalancingBinarySearchTree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
24
 
Post order : 5 24 8
Pre order : 8 5 24
In order : 5 8 24
Do you want to continue (Type y or n)
 
y
 
SelfBalancingBinarySearchTree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
1
Enter integer element to insert
6
 
Post order : 6 5 24 8
Pre order : 8 5 6 24
In order : 5 6 8 24
Do you want to continue (Type y or n)
 
y
 
SelfBalancingBinarySearchTree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
3
Nodes = 4
 
Post order : 6 5 24 8
Pre order : 8 5 6 24
In order : 5 6 8 24
Do you want to continue (Type y or n)
 
y
 
SelfBalancingBinarySearchTree Operations
 
1. insert
2. search
3. count nodes
4. check empty
5. clear tree
2
Enter integer element to search
8
Search result : true
 
Post order : 6 5 24 8
Pre order : 8 5 6 24
In order : 5 6 8 24
Do you want to continue (Type y or n)
 
y
 
SelfBalancingBinarySearchTree 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
 
SelfBalancingBinarySearchTree 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.