AVL Tree
About
An AVL Tree is a self-balancing Binary Search Tree (BST) named after its inventors Adelson-Velsky and Landis. It ensures that the tree remains approximately balanced at all times, keeping operations efficient.
In a regular Binary Search Tree, the performance can degrade to linear time (O(n)) in the worst case (e.g., when the tree becomes a linked list). An AVL Tree maintains a balance condition to ensure that the height of the tree remains logarithmic (O(log n)).
Balance Factor
For every node in an AVL Tree:
Balance Factor = Height of Left Subtree - Height of Right SubtreeIf the balance factor of a node is -1, 0, or 1, then the node is balanced.
If it is less than -1 or greater than 1, the tree becomes unbalanced and needs rebalancing via rotations.
Height of AVL Tree
The height h of an AVL tree with n nodes is strictly O(log n). This is what differentiates AVL trees from unbalanced BSTs.
AVL trees achieve this logarithmic height by ensuring no node gets too deep compared to its siblings.
AVL Tree Properties
Binary Search Tree Property: Left subtree contains smaller values, right subtree contains larger values.
Balance Factor Property: For every node, the balance factor must be -1, 0, or +1.
Height-balanced: Ensures tree height stays in O(log n).
All operations (insertion, deletion, search) take O(log n) time due to the balance condition.
Rotations in AVL Trees
When we insert or delete nodes in an AVL tree, the balance factor (difference in height between the left and right subtrees) of certain nodes might become more than 1 or less than -1. This violates the AVL tree property of being balanced.
To restore balance, rotations are used. A rotation is a local rearrangement of nodes in a small part of the tree (typically three nodes) to rebalance it.
Rotations can also be needed after deletion. Deletion might cause height imbalance going up the tree. At each ancestor node, we must:
Recalculate height and balance factor.
Apply the appropriate rotation based on the case.
Types of Rotations
There are four kinds of rotations used in AVL trees, based on how the imbalance occurs:
1. Right Rotation (RR Rotation)
When to use: Occurs when a node is inserted into the left subtree of the left child (Left-Left case).
Structure before rotation
z
/
y
/
xSteps:
Make
ythe new root of this subtree.Move
zto the right ofy.Move the right subtree of
y(if any) to be the left subtree ofz.
After rotation
y
/ \
x z2. Left Rotation (LL Rotation)
When to use: Occurs when a node is inserted into the right subtree of the right child (Right-Right case).
Structure before rotation
z
\
y
\
xSteps:
Make
ythe new root of this subtree.Move
zto the left ofy.Move the left subtree of
y(if any) to be the right subtree ofz.
After rotation
y
/ \
z x3. Left-Right Rotation (LR Rotation)
When to use: Occurs when a node is inserted into the right subtree of the left child (Left-Right case).
Structure before rotation
z
/
y
\
xSteps:
Left Rotation on y to convert it into a Left-Left case.
Right Rotation on z.
After rotation
x
/ \
y z4. Right-Left Rotation (RL Rotation)
When to use: Occurs when a node is inserted into the left subtree of the right child (Right-Left case).
Structure before rotation
z
\
y
/
xSteps:
Right Rotation on y to convert it into a Right-Right case.
Left Rotation on z.
After rotation:
x
/ \
z yRules for Rotation
Rotation does not break the BST property. The in-order traversal before and after rotation remains the same.
Rotation is a local operation. Only a small section of the tree is adjusted; the rest remains untouched.
Rotation must be followed by height updates. After performing a rotation, we must recompute the height and balance factors for the involved nodes.
When Exactly to Perform Which Rotation?
Left-Left (LL)
Insertion in left subtree of left child
Right Rotation
Right-Right (RR)
Insertion in right subtree of right child
Left Rotation
Left-Right (LR)
Insertion in right subtree of left child
Left Rotation on child, then Right Rotation on root
Right-Left (RL)
Insertion in left subtree of right child
Right Rotation on child, then Left Rotation on root
AVL Tree Operations
1. Insertion
Insert the node like in a BST.
Update the heights.
Check for imbalance.
Perform rotation if needed.
2. Deletion
Delete the node like in a BST.
Update the heights from the deleted node upward.
Check for imbalance at every node.
Perform rotations as necessary to rebalance.
3. Search
Same as a regular BST.
O(log n) time because the tree remains balanced.
Example to Tie Everything Together
Suppose we insert values in the following order: 30, 20, 25
Insert 30 → root is 30 → balanced.
Insert 20 → left of 30 → still balanced.
Insert 25 → right of 20 → causes Left-Right (LR) imbalance at 30.
Before rotation:
30
/
20
\
25Perform:
Left rotation on 20 → makes 25 the new child of 30.
Right rotation on 30 → makes 25 the new root.
After rotation:
25
/ \
20 30Java Implementation
1. AVL Tree Node Structure
class AVLNode {
int key;
int height;
AVLNode left;
AVLNode right;
AVLNode(int key) {
this.key = key;
this.height = 1; // height starts from 1 (leaf)
}
}2. AVL Tree Insert with Rotation
class AVLTree {
private AVLNode root;
// Helper: Get height of node
int height(AVLNode node) {
return (node == null) ? 0 : node.height;
}
// Helper: Get balance factor
int getBalance(AVLNode node) {
return (node == null) ? 0 : height(node.left) - height(node.right);
}
// Helper: Right rotate
AVLNode rotateRight(AVLNode y) {
AVLNode x = y.left;
AVLNode T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
// Helper: Left rotate
AVLNode rotateLeft(AVLNode x) {
AVLNode y = x.right;
AVLNode T2 = y.left;
y.left = x;
x.right = T2;
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 a key and balance the tree
AVLNode insert(AVLNode node, int key) {
if (node == null)
return new AVLNode(key);
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else
return node; // duplicates not allowed
// Update height
node.height = 1 + Math.max(height(node.left), height(node.right));
// Balance
int balance = getBalance(node);
// Left Left
if (balance > 1 && key < node.left.key)
return rotateRight(node);
// Right Right
if (balance < -1 && key > node.right.key)
return rotateLeft(node);
// Left Right
if (balance > 1 && key > node.left.key) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
// Right Left
if (balance < -1 && key < node.right.key) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}
// Public insert
public void insert(int key) {
root = insert(root, key);
}3. AVL Delete Operation
AVLNode minValueNode(AVLNode node) {
AVLNode current = node;
while (current.left != null)
current = current.left;
return current;
}
AVLNode delete(AVLNode root, int key) {
if (root == null)
return root;
if (key < root.key)
root.left = delete(root.left, key);
else if (key > root.key)
root.right = delete(root.right, key);
else {
// Node with one or no child
if ((root.left == null) || (root.right == null)) {
AVLNode temp = (root.left != null) ? root.left : root.right;
root = (temp == null) ? null : temp;
} else {
// Node with two children: get inorder successor
AVLNode temp = minValueNode(root.right);
root.key = temp.key;
root.right = delete(root.right, temp.key);
}
}
if (root == null)
return root;
root.height = 1 + Math.max(height(root.left), height(root.right));
int balance = getBalance(root);
// Balance cases
if (balance > 1 && getBalance(root.left) >= 0)
return rotateRight(root);
if (balance > 1 && getBalance(root.left) < 0) {
root.left = rotateLeft(root.left);
return rotateRight(root);
}
if (balance < -1 && getBalance(root.right) <= 0)
return rotateLeft(root);
if (balance < -1 && getBalance(root.right) > 0) {
root.right = rotateRight(root.right);
return rotateLeft(root);
}
return root;
}
public void delete(int key) {
root = delete(root, key);
}4. Level-Order Traversal
public void levelOrder() {
if (root == null) return;
Queue<AVLNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
AVLNode current = queue.poll();
System.out.print(current.key + " ");
if (current.left != null) queue.add(current.left);
if (current.right != null) queue.add(current.right);
}
System.out.println();
}5. Visual Tree Printing (Diagram Style)
public void printTree() {
printTree(root, "", true);
}
private void printTree(AVLNode node, String prefix, boolean isTail) {
if (node == null) return;
System.out.println(prefix + (isTail ? "└── " : "├── ") + node.key);
if (node.left != null || node.right != null) {
if (node.right != null)
printTree(node.right, prefix + (isTail ? " " : "│ "), false);
if (node.left != null)
printTree(node.left, prefix + (isTail ? " " : "│ "), true);
}
}6. Check Tree Height
public int getHeight() {
return height(root);
}
}Sample Usage
public class Main {
public static void main(String[] args) {
AVLTree avl = new AVLTree();
avl.insert(10);
avl.insert(20);
avl.insert(30);
avl.insert(40);
avl.insert(50);
avl.insert(25);
System.out.println("AVL Tree:");
avl.printTree();
System.out.println("Level Order:");
avl.levelOrder();
System.out.println("Height: " + avl.getHeight());
avl.delete(30);
System.out.println("After Deletion of 30:");
avl.printTree();
}
}Last updated