ayodhyya.comAn AVL Tree is a self-balancing Binary Search Tree named after its inventors Adelson-Velsky and Landis. It maintains a balance factor (height of left subtree minus height of right subtree) of −1, 0, or +1 for every node. When an insertion or deletion causes the balance factor to go out of range, rotations are performed to restore balance.
AVL trees guarantee O(log n) search, insert, and delete operations. They are more strictly balanced than Red-Black trees, making them faster for lookup-intensive applications but slower for insertion-heavy workloads due to more frequent rotations.
Rotations: LL, RR, LR, RL
LL imbalance occurs when a node is inserted into the left subtree of the left child — resolved by a right rotation. RR is symmetric (left rotation). LR requires a left rotation on the left child followed by a right rotation on the node. RL requires a right rotation on the right child followed by a left rotation on the node.
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
y->height = 1 + max(height(y->left), height(y->right));
x->height = 1 + max(height(x->left), height(x->right));
return x;
}
Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
x->height = 1 + max(height(x->left), height(x->right));
y->height = 1 + max(height(y->left), height(y->right));
return y;
}Insertion with Balancing
After a standard BST insertion, we update heights and check the balance factor. If unbalanced, we identify the case (LL, LR, RR, RL) and apply the corresponding rotation(s). The tree remains balanced after each insertion.
Node* insert(Node* node, int key) {
if (!node) return new Node(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;
node->height = 1 + max(height(node->left), height(node->right));
int bal = getBalance(node);
if (bal > 1 && key < node->left->key) return rightRotate(node);
if (bal < -1 && key > node->right->key) return leftRotate(node);
if (bal > 1 && key > node->left->key) {
node->left = leftRotate(node->left); return rightRotate(node); }
if (bal < -1 && key < node->right->key) {
node->right = rightRotate(node->right); return leftRotate(node); }
return node;
}Frequently Asked Questions
What is the balance factor?
The balance factor is height(left) − height(right). In an AVL tree, it must be −1, 0, or +1 for every node. If outside this range after insertion or deletion, rotations rebalance the tree.
How does AVL differ from Red-Black Tree?
AVL trees are more strictly balanced, offering faster lookups (O(log n)) but requiring more rotations per insertion/deletion. Red-Black trees are less strict, requiring fewer rotations and thus faster inserts/deletes.
Originally published on Ayodhyya. Last updated June 1, 2026.
Balance Factor and Rotations
An AVL tree tracks the balance factor (left height minus right height) for every node, keeping it in {-1, 0, 1}. When an insertion or deletion violates this, single or double rotations restore balance. There are four cases: LL, RR, LR, RL.
AVL vs Red-Black Tree
AVL trees are more strictly balanced, giving faster lookups (about 0.44 log n vs 0.65 log n comparisons) but more rotations during writes. Red-black trees are preferred when updates dominate (e.g., Java TreeMap, Linux kernel scheduler).
Complexity Guarantees
All operations — search, insert, delete — run in O(log n) guaranteed, with at most O(1) rotations per insertion and O(log n) per deletion. The tree height never exceeds about 1.44 log2(n+2).
When to Use AVL
Use AVL trees for read-heavy workloads with occasional updates: symbol tables in compilers, in-memory indexes, and any application where lookup latency is critical and writes are rare.
Balance Factor and Rotations
An AVL tree tracks the balance factor (left height minus right height) for every node, keeping it in {-1, 0, 1}. When an insertion or deletion violates this, single or double rotations restore balance. There are four cases: LL, RR, LR, RL.<\/p>
AVL vs Red-Black Tree
AVL trees are more strictly balanced, giving faster lookups (about 0.44 log n vs 0.65 log n comparisons) but more rotations during writes. Red-black trees are preferred when updates dominate (e.g., Java TreeMap, Linux kernel scheduler).<\/p>
Complexity Guarantees
All operations — search, insert, delete — run in O(log n) guaranteed, with at most O(1) rotations per insertion and O(log n) per deletion. The tree height never exceeds about 1.44 log2(n+2).<\/p>
When to Use AVL
Use AVL trees for read-heavy workloads with occasional updates: symbol tables in compilers, in-memory indexes, and any application where lookup latency is critical and writes are rare.<\/p>