In this post we'll see how to write a AVL tree Java program. Operations covered in this post are-
- Inserting a node in AVL tree
- Searching a node in AVL tree
- AVL tree traversal
AVL Binary Tree
An AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. In an AVL tree, the heights
of the left subtree and right subtree of any node differ by at most one. If any time that height difference goes beyond one,
rebalancing is done so that height difference is not more than one.
Because of this self-balancing property, AVL tree will not get skewed like Binary Search Tree. AVL tree height is kept to a
minimum so that searching, inserting and deleting nodes have time complexity of O(log n). It will never be O(n) which may be
the time complexity of BST under certain scenarios.
For example, suppose you are inserting {10, 20, 30, 40} in a BST then the BST is skewed towards right.
Which means searching for 40 becomes an O(n) operation.
Same nodes with AVL tree.
As you can see, because of self-balancing, AVL tries to keep the height as minimum, in the above AVL tree you can see that the
difference between left subtree height and right subtree height is 1 from root node.
How does self-balancing work
In an AVL tree, the heights of the left subtree and right subtree of any node differ by at most one. Whenever insertion and
deletion operations are performed on the tree, balance factor is calculated for the nodes to check if height difference is
going beyond the permissible limit for any node. If yes, then rebalancing is done.
The height of a subtree is the number of edges between the root node of that subtree and the leaf node farthest down in that
subtree.
Equation for Balance factor for any node n can be given as-
Balance Factor(n) = height of left subtree(n) - height of right subtree(n)
For a tree to be considered balanced, for every node balance factor should be in the range
-1 <= balance factor <= 1
Which can be explained as-
- BF = 0 means binary tree is perfectly balanced at that node
- BF = +1 means left-heavy at that node but permissible
- BF = -1 means right-heavy at that node but permissible
- BF < -1 or BF > +1 means binary tree is imbalanced and rotation is required to balance it.
Since height is constantly calculated while constructing AVL tree, in order to save time height for each node is stored with
the node.
class Node{
int data;
int height;
Node left;
Node right;
Node(int data){
this.data = data;
this.height = 1;
}
public void displayData(){
System.out.print(data + " ");
}
}
Rotation cases
Following are the scenarios for the AVL tree to become imbalance and each of these scenarios requires different rotation
operation.
- Left-Left scenario- When balance factor of Node n is more than 1 and its left child node is also left heavy that is
LL scenario. In that case a right rotation is needed to make it balanced. For example, consider the following tree. Here
node 30 has BF of 2 (left height is 2 and right height is 0).
So, it has to be right rotated around that node (node with data as 30) so that its left child becomes the parent node and any
right child of that left child becomes the left child of that node.
If the node around which right rotation is done is called node and we have to write that same thing in programming logic, it'll
be as given below.
Node temp1 = node.left;
Node temp2 = temp1.right;
// from where rotation started (origin node) should become right child
temp1.right = node;
// Right child of the left child of origin node should become left child
// of origin node
node.left = temp2;
- Right-Right scenario- When balance factor of Node n is less than -1 and its right child node is also right heavy
that is RR scenario. In that case a left rotation is needed to make it balanced. For example, consider the following tree.
Here node 10 has BF of -2 (left height is 0 and right height is 2).
So, it has to be left rotated around that node (node with data as 10) so that its right child becomes the parent node and any
left child of that right child becomes the right child of that original root node.
If the node around which left rotation is done is called node and we have to write that same thing in programming logic, it'll
be as given below.
Node temp1 = node.right;
Node temp2 = temp1.left;
// from where rotation started (origin node) should become left child
temp1.left = node;
// left child of the right child of origin node should become right child
// of origin node
node.right = temp2;
- Left-Right Scenario- This scenario occurs when parent node is imbalanced as its balance factor is more than +1
(left side imbalance) but it's left child is right heavy. This results in a zig-zag kind of structure which can't be balanced
just by right rotation. For example, consider the following tree.
Right rotation around 30 will make it a wrong structure as 10 as root node and 20 as its left child violates the BST structure
(20 is greater than 10 so it should be on right side).
What you need is left rotation around 10 making 20 the parent of 10.
That makes it a LL scenario needing a right rotation around 30 to finally balance it.
- Right-Left Scenario- This scenario occurs when parent node is imbalanced as its balance factor is less than -1
(right side imbalance) but its right child is left heavy. This results in a zig-zag kind of structure which can't be
balanced just by left rotation. For example, consider the following tree.
Single left rotation around 10 won't make it right. What you need is right rotation around 30 making 20 the parent of 30.
That makes it a RR scenario needing a left rotation around 10 to finally balance it.
AVL Tree Traversal
When you traverse an AVL tree you visit each node in a specified order. Orderings which are used for traversal are-
- Inorder traversal
- Preorder traversal
- Postorder traversal
Note that traversals of AVL trees are same as binary search trees.
AVL tree Inorder traversal in Java
Logic for Inorder traversal of AVL tree is as follows-
Recursively traverse the left subtree
Visit the root node
Recursively traverse the right subtree
// For traversing in order
public void inOrder(Node node){
if(node != null){
inOrder(node.left);
node.displayData();
inOrder(node.right);
}
}
AVL tree Preoder traversal in Java
Logic for preorder traversal of AVL tree is as follows-
Visit the root node
Recursively traverse the left subtree.
Recursively traverse the right subtree
// Preorder traversal
public void preOrder(Node node){
if(node != null){
node.displayData();
preOrder(node.left);
preOrder(node.right);
}
}
AVL tree Postoder traversal in Java
Logic for postoder traversal of AVL tree is as follows-
Recursively traverse the left subtree.
Recursively traverse the right subtree
Visit the root node
// Postorder traversal
public void postOrder(Node node){
if(node != null){
postOrder(node.left);
postOrder(node.right);
node.displayData();
}
}
public class AVLTree {
// first node
Node root;
AVLTree(){
root = null;
}
// Class for defining each node in the tree
static class Node{
int data;
int height;
Node left;
Node right;
Node(int data){
this.data = data;
// New node has height 1 because it has no children
// height of any node is calculated as
//height = 1 + max(height of left child, height of right child)
this.height = 1;
}
public void displayData(){
System.out.print(data + " ");
}
}
public void insert(int data){
root = insert(root, data);
}
public Node insert(Node node, int data) {
if(node == null) {
return new Node(data);
}
if(data < node.data) {
node.left = insert(node.left, data);
}else if(data > node.data) {
node.right = insert(node.right, data);
}else {
return node;
}
//update height of each node traversed
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
int balance = getBalance(node);
// left left
if(balance > 1 && data < node.left.data)
return rightRotate(node);
//right right
if(balance < -1 && data > node.right.data)
return leftRotate(node);
//left right
if(balance > 1 && data > node.left.data) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
//right left
if(balance < -1 && data < node.right.data) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
// method to get height of node
int getHeight(Node node) {
return node == null ? 0 : node.height;
}
// method to get balance factor of node
int getBalance(Node node) {
return node == null ? 0 : (getHeight(node.left) - getHeight(node.right));
}
Node rightRotate(Node node) {
System.out.println("Rotate right on node " + node.data);
Node temp1 = node.left;
Node temp2 = temp1.right;
// from where rotation started (origin node) should become right child
temp1.right = node;
// Right child of the left child of origin node should become left child
// of origin node
node.left = temp2;
// update heights
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
temp1.height = 1 + Math.max(getHeight(temp1.left), getHeight(temp1.right));
return temp1;
}
Node leftRotate(Node node) {
System.out.println("Rotate left on node " + node.data);
Node temp1 = node.right;
Node temp2 = temp1.left;
// from where rotation started (origin node) should become left child
temp1.left = node;
// left child of the right child of origin node should become right child
// of origin node
node.right = temp2;
// update heights
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
temp1.height = 1 + Math.max(getHeight(temp1.left), getHeight(temp1.right));
return temp1;
}
// Search node in binary search tree
public Node find(int searchedValue){
Node current = root;
while(current.data != searchedValue){
if(searchedValue < current.data)
// Move to the left if searched value is less
current = current.left;
else
// Move to the right if searched value is >=
current = current.right;
if(current == null){
return null;
}
}
return current;
}
// For traversing in order
public void inOrder(Node node){
if(node != null){
inOrder(node.left);
node.displayData();
inOrder(node.right);
}
}
// Preorder traversal
public void preOrder(Node node){
if(node != null){
node.displayData();
preOrder(node.left);
preOrder(node.right);
}
}
// Postorder traversal
public void postOrder(Node node){
if(node != null){
postOrder(node.left);
postOrder(node.right);
node.displayData();
}
}
public static void main(String[] args) {
AVLTree avlTree = new AVLTree();
int[] data = {10, 15, 20, 30, 40, 25};
for(int d : data) {
avlTree.insert(d);
}
System.out.println("Inorder traversal of binary tree");
avlTree.inOrder(avlTree.root);
System.out.println();
System.out.println("Post order traversal of binary tree");
avlTree.postOrder(avlTree.root);
System.out.println();
System.out.println("Pre order traversal of binary tree");
avlTree.preOrder(avlTree.root);
System.out.println();
Node node = avlTree.find(21);
System.out.println((node == null)? "Node not found" : String.valueOf(node.data));
}
}
Output
Rotate left on node 10
Rotate left on node 20
Rotate right on node 30
Rotate left on node 15
Inorder traversal of binary tree
10 15 20 25 30 40
Post order traversal of binary tree
10 15 25 40 30 20
Pre order traversal of binary tree
20 15 10 30 25 40
Node not found
Constructed AVL tree would look something like this-
That's all for the topic AVL Tree Java Program - Insertion, Traversal, Search. If something is missing or you have something to share about the topic please write a comment.
You may also like
