Java Data Structure Implementation : Balanced BST(AVL Tree)

This program demonstrates the Balanced Binary Tree implementation in Java. The Operation which has been implemented are –

1. Insert Into Binary Tree
2. Balance Tree Automatically After Insertion
3. LL, LR, RR, RL Rotations Implemented

Find the Java Code below :

import java.util.Scanner;

/*
* This class demonstrates Balanced Binary Tree (AVL Tree) Implementation in java with Insert/Delete Operations.
* @author : Madan Gopal Singh
* @version : 1.0
* @date : 22nd March, 2013
*/
public class AVLTree {
AVLTree left;
int id;
AVLTree right;
int height;
int balanceFactor;

public AVLTree() {
}

public AVLTree(int id){
left = null;
this.id = id;
right = null;
}

public AVLTree(AVLTree left,int id,AVLTree right){
this.left = left;
this.id =id;
this.right = right;
}

/**
* This method rotates the Left to balance the binary tree.
* @param rootNode The Starting node of Tree.
* @return AVLTree.
*/
public static AVLTree rotateLeftLeft(AVLTree rootNode){
AVLTree tempNode;
tempNode = rootNode.left;
rootNode.left = tempNode.right;
tempNode.right = rootNode;
return tempNode;
}

/**
* This method rotates the Right to balance the binary tree.
* @param rootNode The Starting node of Tree.
* @return AVLTree.
*/
public static AVLTree rotateRightRight(AVLTree rootNode){
AVLTree tempNode;
tempNode = rootNode.right;
rootNode.right = tempNode.left;
tempNode.left = rootNode;
return tempNode;
}

/**
* This method rotates the Left first the Right to balance the binary tree.
* @param rootNode The Starting node of Tree.
* @return AVLTree.
*/
public static AVLTree rotateLeftRight(AVLTree rootNode){
AVLTree tempNode;
tempNode = rootNode.left;
rootNode.left = AVLTree.rotateRightRight(tempNode);
return AVLTree.rotateLeftLeft(rootNode);
}

/**
* This method rotates the Right first then Left to balance the binary tree.
* @param rootNode The Starting node of Tree.
* @return AVLTree.
*/
public static AVLTree rotateRightLeft(AVLTree rootNode){
AVLTree tempNode;
tempNode = rootNode.right;
rootNode.right = AVLTree.rotateLeftLeft(tempNode);
return AVLTree.rotateRightRight(rootNode);
}

/**
* This method returns the height of the binary tree.
* @param rootNode The Starting node of Tree.
* @return integer.
*/
public static int getHeight(AVLTree rootNode){
if(rootNode == null){
return 0;
}
if(rootNode.left == null && rootNode.right == null){
return 1;
}else{
return 1+AVLTree.maximum(AVLTree.getHeight(rootNode.left),AVLTree.getHeight(rootNode.right));
}
}

/**
* This method maximum between two heights of the Binary Tree.
* @param rootNode The Starting node of Tree.
* @return integer.
*/
public static int maximum(int height1,int height2){
if(height1>=height2)
return height1;
else
return height2;
}

/**
* This method returns the balance factor of the node of binary tree.
* @param rootNode The Starting node of Tree.
* @return integer.
*/
public static int getBalanceFactor(AVLTree rootNode){
if(rootNode == null)
return 0;
else
return (AVLTree.getHeight(rootNode.left)-AVLTree.getHeight(rootNode.right));
}

/**
* This method balances the binary tree.
* @param rootNode The Starting node of Tree.
* @return AVLTree.
*/
public static AVLTree balanceTree(AVLTree rootNode){
int balanceFactor = AVLTree.getBalanceFactor(rootNode);
int balanceFactorSubNode;
AVLTree tempNode = null;
if(balanceFactor>1){
balanceFactorSubNode = AVLTree.getBalanceFactor(rootNode.left);
if(balanceFactorSubNode>0){
System.out.println("Rotating Left Left");
tempNode = AVLTree.rotateLeftLeft(rootNode);
}else{
System.out.println("Rotating left Right");
tempNode = AVLTree.rotateLeftRight(rootNode);
}
return tempNode;
}else{
if(balanceFactor0){
System.out.println("Rotating Right Left");
tempNode = AVLTree.rotateRightLeft(rootNode);
}else{
System.out.println("Rotating Right Right");
tempNode = AVLTree.rotateRightRight(rootNode);
}
return tempNode;
}
}
return rootNode;
}

/**
* This method add a new node into the balanced binary tree (AVL Tree).
* @param rootNode The Starting node of Tree.
* @param toBeInsertedNodeId The node which you want to insert
* @return AVLTree.
*/
public static AVLTree insertNewNodeInAVLTree(AVLTree rootNode,int toBeInsertedNodeId){
AVLTree tempRootNode = rootNode;
if(rootNode.left==null && rootNode.right==null){
if(toBeInsertedNodeId<=rootNode.id){
System.out.println("Inserting Left Branch");
rootNode.left = new AVLTree(toBeInsertedNodeId);
}else{
System.out.println("Inserting Right Branch");
rootNode.right = new AVLTree(toBeInsertedNodeId);
}
}else{
if(toBeInsertedNodeId<=rootNode.id){
if(rootNode.left==null){
System.out.println("Inserting into Left Subtree");
rootNode.left = new AVLTree(toBeInsertedNodeId);
}else{
System.out.println("Traversing Left Subtree");
rootNode = insertNewNodeInAVLTree(rootNode.left, toBeInsertedNodeId);
}
}else{
if(rootNode.right==null){
System.out.println("Inserting into Right Subtree");
rootNode.right = new AVLTree(toBeInsertedNodeId);
}else{
System.out.println("Traversing Right Subtree");
rootNode = insertNewNodeInAVLTree(rootNode.right, toBeInsertedNodeId);
}
}
}
return tempRootNode;
}

/**
* This method performs preorder travarsal of the binary tree.
* @param rootNode The Starting node of Tree.
* @return Tree.
*/
public static AVLTree treePreOrderTraversal(AVLTree root){
System.out.print(root.id+" ");
if(root.left==null&&root.right==null){
return root;
}else{
if(root.left!=null){
AVLTree.treePreOrderTraversal(root.left);
}
if(root.right!=null){
AVLTree.treePreOrderTraversal(root.right);
}
}
return root;
}

/**
* Main Method
* @param args command line argument list
* @return void.
*/
public static void main(String[] args) {
AVLTree rootNode = null;
int nodeId = 0,userOperation=0;
String mainMenuString = "";
Scanner sc = new Scanner(System.in);
do{
mainMenuString = "What operation you want to perform on AVL Tree?"+
"\n 1. Insert New Node "+
"\n 2. Delete a Node"+
"\n 3. Preorder Traversal"+
"\n -1. Exit from Menu"+
"\n Please enter Operation Number : ";
System.out.println(mainMenuString);
userOperation = sc.nextInt();
switch(userOperation){
case 1:
System.out.println("Please enter the Node Id to which you want to insert : ");
nodeId = sc.nextInt();
if(rootNode==null){
rootNode = new AVLTree(nodeId);
}else{
AVLTree.insertNewNodeInAVLTree(rootNode, nodeId);
System.out.println("Height of Root Node after Insertion is :-"+AVLTree.getHeight(rootNode));
System.out.println("BalanceFactor of Root Node after Insertion is :-"+AVLTree.getBalanceFactor(rootNode));
rootNode = AVLTree.balanceTree(rootNode);
}
break;
case 2:
System.out.println("Please enter the Node Id of which you want to delete : ");
nodeId = sc.nextInt();
//AVLTree.deleteNodeFromAVLTree(rootNode,nodeId);
System.out.println("Similar to Tree Deletion. Kindly read my BST Post");
break;
case 3:
System.out.println("Preorder traversal sequence : ");
if(rootNode!=null){
AVLTree.treePreOrderTraversal(rootNode);
}else{
System.out.println("No node to traversal.");
}
break;
case -1:
System.out.println("Exit Application");
System.exit(0);
break;
default:
System.out.println("Invalid Operation!! Please try again");
}
}while(userOperation!=-1);
}
}

Any Optimization/Suggestions are invited.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s