AVL Trees
AVL Tree (named after inventors Adelson-Velsky and Landis) is a self-balancing Binary Search Tree where the difference between heights of left and right subtrees (Balance Factor) cannot be more than 1 for any node.
How an AVL Tree Works
An AVL Tree (named after inventors Adelson-Velsky and Landis) is a self-balancing Binary Search Tree (BST). It solves the critical flaw of a standard BST—preventing it from degrading into a slow, one-sided line.
- The Balance Factor: Every node in an AVL tree keeps track of its “Balance Factor.” This is calculated by taking the height of its left subtree and subtracting the height of its right subtree.
- The Golden Rule: The Balance Factor of every node must strictly be -1, 0, or 1.
- Rotations: If you insert or delete a node and the balance factor of any node becomes 2 or -2, the tree immediately pauses and performs a “Rotation” (shifting nodes up and down) to fix the imbalance before moving on.
Real-Life Examples
- A Hanging Mobile: Think of a decorative mobile hanging from the ceiling. If you attach a heavy toy to one side, the whole structure tips. To fix it, you have to adjust the strings (rotate the nodes) to perfectly distribute the weight again.
- Corporate Restructuring: An HR policy where no single manager is allowed to have a massive, deep chain of command while another manager at the same level has none. If one team gets too deep, employees are shifted to keep the reporting structure flat and efficient.
Technical & Software Applications
Because AVL trees guarantee that the tree is always perfectly balanced, they are highly optimized for read-heavy tasks where search speed is absolutely critical:
- In-Memory Databases: Applications that need to rapidly retrieve data stored in RAM without any lag.
- Dictionary Lookups: Software dictionaries where you are constantly searching for word definitions but rarely adding new words.
- Caching Mechanisms: Systems that need to quickly check if a specific piece of data is currently stored in the cache.
Core Rotations
To fix an imbalance, the tree uses four specific moves depending on where the heavy side is:
- Left Rotation (LL): Used when the right side is too heavy in a straight line.
- Right Rotation (RR): Used when the left side is too heavy in a straight line.
- Left-Right Rotation (LR): A two-step move when the left side is heavy, but the extra weight is “inside” the tree.
- Right-Left Rotation (RL): A two-step move when the right side is heavy, but the extra weight is “inside” the tree.
Time and Space Complexity
- Time Complexity: O(log n) guaranteed for searching, inserting, and deleting. Because the tree strictly enforces its balance, you will never face the O(n) worst-case scenario of a standard BST.
- Space Complexity: O(n). However, in practice, it requires slightly more memory per node than a standard BST because each node must store an extra integer to remember its height/balance factor.
AVL Tree Implementation
Code Example
JavaPythonCC++
// Node of AVL Tree
class AVLNode {
int data, height;
AVLNode left, right;
AVLNode(int value) {
data = value;
height = 1; // new node height = 1
}
}
class AVLTree {
AVLNode root;
// Get height of node
int height(AVLNode n) {
if (n == null)
return 0;
return n.height;
}
// Get balance factor
int getBalance(AVLNode n) {
if (n == null)
return 0;
return height(n.left) - height(n.right);
}
// Right rotation
AVLNode rightRotate(AVLNode y) {
AVLNode x = y.left;
AVLNode T2 = x.right;
// rotation
x.right = y;
y.left = T2;
// update height
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x; // new root
}
// Left rotation
AVLNode leftRotate(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 node
AVLNode insert(AVLNode node, int key) {
// Normal BST insert
if (node == null)
return new AVLNode(key);
if (key < node.data)
node.left = insert(node.left, key);
else if (key > node.data)
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));
// Check balance
int balance = getBalance(node);
// LL case
if (balance > 1 && key < node.left.data)
return rightRotate(node);
// RR case
if (balance < -1 && key > node.right.data)
return leftRotate(node);
// LR case
if (balance > 1 && key > node.left.data) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// RL case
if (balance < -1 && key < node.right.data) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
// Preorder traversal
void preOrder(AVLNode node) {
if (node != null) {
System.out.print(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
// Insert nodes
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);
System.out.println("Preorder Traversal:");
tree.preOrder(tree.root);
}
}
# Node of AVL Tree
class AVLNode:
def __init__(self, value):
self.data = value
self.left = None
self.right = None
self.height = 1
class AVLTree:
def height(self, node):
if node is None:
return 0
return node.height
def getBalance(self, node):
if node is None:
return 0
return self.height(node.left) - self.height(node.right)
# Right rotation
def rightRotate(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = max(self.height(y.left), self.height(y.right)) + 1
x.height = max(self.height(x.left), self.height(x.right)) + 1
return x
# Left rotation
def leftRotate(self, x):
y = x.right
T2 = y.left
y.left = x
x.right = T2
x.height = max(self.height(x.left), self.height(x.right)) + 1
y.height = max(self.height(y.left), self.height(y.right)) + 1
return y
# Insert node
def insert(self, node, key):
if node is None:
return AVLNode(key)
if key < node.data:
node.left = self.insert(node.left, key)
elif key > node.data:
node.right = self.insert(node.right, key)
else:
return node
node.height = 1 + max(self.height(node.left), self.height(node.right))
balance = self.getBalance(node)
# LL
if balance > 1 and key < node.left.data:
return self.rightRotate(node)
# RR
if balance < -1 and key > node.right.data:
return self.leftRotate(node)
# LR
if balance > 1 and key > node.left.data:
node.left = self.leftRotate(node.left)
return self.rightRotate(node)
# RL
if balance < -1 and key < node.right.data:
node.right = self.rightRotate(node.right)
return self.leftRotate(node)
return node
def preOrder(self, node):
if node:
print(node.data, end=" ")
self.preOrder(node.left)
self.preOrder(node.right)
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
int height;
struct Node* left;
struct Node* right;
};
int height(struct Node* n) {
if (n == NULL)
return 0;
return n->height;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
struct Node* newNode(int value) {
struct Node* node = malloc(sizeof(struct Node));
node->data = value;
node->left = NULL;
node->right = NULL;
node->height = 1;
return node;
}
#include <iostream>
using namespace std;
class Node {
public:
int data, height;
Node* left;
Node* right;
Node(int value) {
data = value;
height = 1;
left = right = NULL;
}
};
class AVLTree {
public:
Node* root;
int height(Node* n) {
if (n == NULL)
return 0;
return n->height;
}
int getBalance(Node* n) {
if (n == NULL)
return 0;
return height(n->left) - height(n->right);
}
};