An AVL Tree is a self-balancing Binary Search Tree (BST). In a normal BST, the tree can become unbalanced, which makes searching slow. An AVL Tree solves this problem by automatically maintaining balance after every insertion or deletion.
Why do we need an AVL Tree?
Let’s understand the problem first. In a BST, if we insert values in sorted order, the tree may look like this:
10
\
20
\
30
\
40This looks like a linked list, not a tree. Searching here becomes slow. An AVL Tree prevents this by rebalancing itself.
What does AVL mean?
AVL is named after its inventors: Adelson-Velsky and Landis. It was the first self-balancing BST.
AVL Tree Rule
- It is a self-balancing Binary Search Tree.
- For every node: Balance Factor = height(left) − height(right) = −1, 0, or +1
- If unbalanced, rotations are used to fix it.
(Height = longest path from a node to a leaf)
After Insertion or Deletion, if the balance factor becomes -2 or +2, rotations are applied.
Types of Rotations
- LL (Left–Left): Occurs when a node becomes unbalanced due to insertion in the left subtree of the left child – fixed by Right Rotation
- RR (Right–Right): Occurs when insertion is in the right subtree of the right child – fixed by Left Rotation
- LR (Left–Right): Occurs when insertion is in the right subtree of the left child – fixed by Left Rotation on the child, then Right Rotation
- RL (Right–Left): Occurs when insertion is in the left subtree of the right child – fixed by Right Rotation on the child, then Left Rotation
Why AVL Tree is Important?
- Keeps the tree balanced automatically
- Ensures fast searching, insertion, and deletion
- Prevents the tree from becoming unbalanced
- Guarantees O(log n) time complexity
- Better performance than a normal Binary Search Tree in the worst case
AVL Tree Program in Java (Insertion + Traversal)
In this Java program, we insert values into an AVL Tree and print them using inorder traversal to verify the sorted structure.
// Node class for an AVL Tree
class Node {
int data;
int height;
Node left;
Node right;
Node(int data) {
this.data = data;
height = 1;
}
}
public class AVLTree {
Node root;
// Get height of node
int height(Node node) {
if (node == null)
return 0;
return node.height;
}
// Get balance factor
int getBalance(Node node) {
if (node == null)
return 0;
return height(node.left) - height(node.right);
}
// Right rotate
Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
// Rotation
x.right = y;
y.left = T2;
// Update heights
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
// Left rotate
Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
// Rotation
y.left = x;
x.right = T2;
// Update heights
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
// Insert into AVL Tree
Node insert(Node node, int value) {
// Normal BST insertion
if (node == null)
return new Node(value);
if (value < node.data)
node.left = insert(node.left, value);
else if (value > node.data)
node.right = insert(node.right, value);
else
return node; // no duplicates
// Update height
node.height = 1 + Math.max(height(node.left), height(node.right));
// Get balance factor
int balance = getBalance(node);
// LL Case
if (balance > 1 && value < node.left.data)
return rightRotate(node);
// RR Case
if (balance < -1 && value > node.right.data)
return leftRotate(node);
// LR Case
if (balance > 1 && value > node.left.data) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// RL Case
if (balance < -1 && value < node.right.data) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
// Inorder traversal
void inorder(Node node) {
if (node == null)
return;
inorder(node.left);
System.out.print(node.data + " ");
inorder(node.right);
}
// Main method
public static void main(String[] args) {
AVLTree tree = new AVLTree();
int[] values = {10, 20, 30, 40, 50, 25};
for (int val : values) {
tree.root = tree.insert(tree.root, val);
}
System.out.print("Inorder Traversal: ");
tree.inorder(tree.root); // Sorted output
}
}
An AVL Tree is a self-balancing Binary Search Tree. It automatically keeps itself balanced after every insertion.