AVL Tree from Scratch (2026)
An 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 Ayodhyyya. Last updated June 1, 2026.