Java Program to Perform AVL Tree Operations

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 Print the Kind of Rotation the AVL Tree is Undergoing When you Add an Element or Delete an Element. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to implement self balancing binary search trees and indicate when rotation is performed
  2. import java.util.Scanner;
  3.  
  4. class SBBST
  5. {
  6.     SBBST left, right;
  7.     int   data;
  8.     int   height;
  9.  
  10.     public SBBST()
  11.     {
  12.         left = null;
  13.         right = null;
  14.         data = 0;
  15.         height = 0;
  16.     }
  17.  
  18.     public SBBST(int n)
  19.     {
  20.  
  21.         left = null;
  22.         right = null;
  23.         data = n;
  24.         height = 0;
  25.     }
  26. }
  27.  
  28. class SelfBalancingBinarySearchTree
  29. {
  30.     private SBBST root;
  31.  
  32.     public SelfBalancingBinarySearchTree()
  33.     {
  34.         root = null;
  35.     }
  36.  
  37.     public boolean isEmpty()
  38.     {
  39.         return root == null;
  40.     }
  41.  
  42.     public void clear()
  43.     {
  44.         root = null;
  45.     }
  46.  
  47.     public void insert(int data)
  48.     {
  49.         root = insert(data, root);
  50.     }
  51.  
  52.     private int height(SBBST t)
  53.     {
  54.  
  55.         return t == null ? -1 : t.height;
  56.     }
  57.  
  58.     private int max(int lhs, int rhs)
  59.     {
  60.         return lhs > rhs ? lhs : rhs;
  61.     }
  62.  
  63.     private SBBST insert(int x, SBBST t)
  64.     {
  65.         if (t == null)
  66.             t = new SBBST(x);
  67.         else if (x < t.data)
  68.         {
  69.             t.left = insert(x, t.left);
  70.             if (height(t.left) - height(t.right) == 2)
  71.                 if (x < t.left.data)
  72.                     t = rotateWithLeftChild(t);
  73.                 else
  74.                     t = doubleWithLeftChild(t);
  75.         } else if (x > t.data)
  76.         {
  77.             t.right = insert(x, t.right);
  78.             if (height(t.right) - height(t.left) == 2)
  79.                 if (x > t.right.data)
  80.                     t = rotateWithRightChild(t);
  81.                 else
  82.                     t = doubleWithRightChild(t);
  83.         } else
  84.             ;
  85.         t.height = max(height(t.left), height(t.right)) + 1;
  86.         return t;
  87.     }
  88.  
  89.     private SBBST rotateWithLeftChild(SBBST k2)
  90.     {
  91.         System.out.println("Left Rotation Performed");
  92.         SBBST k1 = k2.left;
  93.         k2.left = k1.right;
  94.         k1.right = k2;
  95.         k2.height = max(height(k2.left), height(k2.right)) + 1;
  96.         k1.height = max(height(k1.left), k2.height) + 1;
  97.         return k1;
  98.     }
  99.  
  100.     private SBBST rotateWithRightChild(SBBST k1)
  101.     {
  102.         System.out.println("Right Rotation Performed");
  103.         SBBST k2 = k1.right;
  104.         k1.right = k2.left;
  105.         k2.left = k1;
  106.         k1.height = max(height(k1.left), height(k1.right)) + 1;
  107.         k2.height = max(height(k2.right), k1.height) + 1;
  108.         return k2;
  109.     }
  110.  
  111.     private SBBST doubleWithLeftChild(SBBST k3)
  112.     {
  113.         System.out.println("Left Rotation Performed");
  114.         k3.left = rotateWithRightChild(k3.left);
  115.         return rotateWithLeftChild(k3);
  116.     }
  117.  
  118.     private SBBST doubleWithRightChild(SBBST k1)
  119.     {
  120.         System.out.println("Right Rotation Performed");
  121.         k1.right = rotateWithLeftChild(k1.right);
  122.         return rotateWithRightChild(k1);
  123.     }
  124.  
  125.     public int countNodes()
  126.     {
  127.         return countNodes(root);
  128.     }
  129.  
  130.     private int countNodes(SBBST r)
  131.     {
  132.         if (r == null)
  133.             return 0;
  134.         else
  135.         {
  136.             int l = 1;
  137.             l += countNodes(r.left);
  138.             l += countNodes(r.right);
  139.             return l;
  140.         }
  141.     }
  142.  
  143.     public boolean search(int val)
  144.     {
  145.         return search(root, val);
  146.     }
  147.  
  148.     private boolean search(SBBST r, int val)
  149.     {
  150.         boolean found = false;
  151.         while ((r != null) && !found)
  152.         {
  153.             int rval = r.data;
  154.             if (val < rval)
  155.                 r = r.left;
  156.             else if (val > rval)
  157.                 r = r.right;
  158.             else
  159.             {
  160.                 found = true;
  161.                 break;
  162.             }
  163.             found = search(r, val);
  164.         }
  165.         return found;
  166.     }
  167.  
  168.     public void inorder()
  169.     {
  170.         inorder(root);
  171.     }
  172.  
  173.     private void inorder(SBBST r)
  174.     {
  175.         if (r != null)
  176.         {
  177.             inorder(r.left);
  178.             System.out.print(r.data + " ");
  179.             inorder(r.right);
  180.         }
  181.     }
  182.  
  183.     public void preorder()
  184.     {
  185.  
  186.         preorder(root);
  187.     }
  188.  
  189.     private void preorder(SBBST r)
  190.     {
  191.         if (r != null)
  192.         {
  193.             System.out.print(r.data + " ");
  194.             preorder(r.left);
  195.             preorder(r.right);
  196.         }
  197.     }
  198.  
  199.     public void postorder()
  200.     {
  201.         postorder(root);
  202.     }
  203.  
  204.     private void postorder(SBBST r)
  205.     {
  206.         if (r != null)
  207.         {
  208.             postorder(r.left);
  209.             postorder(r.right);
  210.             System.out.print(r.data + " ");
  211.         }
  212.     }
  213. }
  214.  
  215. public class Rotation_BST
  216. {
  217.     public static void main(String[] args)
  218.     {
  219.         Scanner scan = new Scanner(System.in);
  220.  
  221.         SelfBalancingBinarySearchTree sbbst = new SelfBalancingBinarySearchTree();
  222.         System.out.println("Self Balancing Tree\n");
  223.  
  224.         System.out.println("Inset first 10 Elements");
  225.         int N = 10;
  226.         for (int i = 0; i < N; i++)
  227.         {
  228.             sbbst.insert(scan.nextInt());
  229.  
  230.             System.out.println("\nPre-order  :");
  231.             sbbst.preorder();
  232.             System.out.println("\nIn-order   :");
  233.             sbbst.inorder();
  234.             System.out.println("\nPost-order :");
  235.             sbbst.postorder();
  236.  
  237.             System.out.println();
  238.         }
  239.         scan.close();
  240.     }
  241. }

Output:

$ javac Rotation_BST.java
$ java Rotation_BST
 
Self Balancing Tree
 
Inset first 10 Elements
1
 
Pre-order  :
1 
In-order   :
1 
Post-order :
1 
2
 
Pre-order  :
1 2 
In-order   :
1 2 
Post-order :
2 1 
3
Right Rotation Performed
 
Pre-order  :
2 1 3 
In-order   :
1 2 3 
Post-order :
1 3 2 
6
 
Pre-order  :
2 1 3 6 
In-order   :
1 2 3 6 
Post-order :
1 6 3 2 
5
Right Rotation Performed
Left Rotation Performed
Right Rotation Performed
 
Pre-order  :
2 1 5 3 6 
In-order   :
1 2 3 5 6 
Post-order :
1 3 6 5 2 
4
Right Rotation Performed
Left Rotation Performed
Right Rotation Performed
 
Pre-order  :
3 2 1 5 4 6 
In-order   :
1 2 3 4 5 6 
Post-order :
1 2 4 6 5 3 
9
 
Pre-order  :
3 2 1 5 4 6 9 
In-order   :
1 2 3 4 5 6 9 
Post-order :
1 2 4 9 6 5 3 
8
Right Rotation Performed
Left Rotation Performed
Right Rotation Performed
 
Pre-order  :
3 2 1 5 4 8 6 9 
In-order   :
1 2 3 4 5 6 8 9 
Post-order :
1 2 4 6 9 8 5 3 
7
Right Rotation Performed
Left Rotation Performed
Right Rotation Performed
 
Pre-order  :
3 2 1 6 5 4 8 7 9 
In-order   :
1 2 3 4 5 6 7 8 9 
Post-order :
1 2 4 5 7 9 8 6 3

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

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
I’m Manish - Founder and CTO at Sanfoundry. I’ve been working in tech for over 25 years, with deep focus on Linux kernel, SAN technologies, Advanced C, Full Stack and Scalable website designs.

You can connect with me on LinkedIn, watch my Youtube Masterclasses, or join my Telegram tech discussions.

If you’re in your 40s–60s and exploring new directions in your career, I also offer mentoring. Learn more here.