AVL Tree
Last updated
An AVL tree is a self-balancing binary search tree. It works like a normal BST, but after every insertion it checks each ancestor's balance factor - the height difference between its left and right subtrees - and if any node becomes unbalanced (a difference greater than 1), it performs rotations to restore balance. Press play above to watch values inserted and the tree rotate itself back into shape.
Because it never lets the tree get more than slightly lopsided, an AVL tree guarantees O(log n) height, so search, insert, and delete are always O(log n) - even for sorted input that would wreck a plain BST. The cost is the extra rotations and height bookkeeping on each insert.
Time & space complexity
| Operation | Complexity | Notes |
|---|---|---|
| Search | O(log n) | Height is always ~1.44 log n |
| Insert | O(log n) | Plus O(1) rotations |
| Delete | O(log n) | Plus O(log n) rotations |
| Space | O(n) | One height field per node |
The four rotation cases
| Case | Imbalance | Fix |
|---|---|---|
| Left-Left | Heavy on left child's left | One right rotation |
| Right-Right | Heavy on right child's right | One left rotation |
| Left-Right | Heavy on left child's right | Left, then right rotation |
| Right-Left | Heavy on right child's left | Right, then left rotation |
Worked example
Inserting [10, 20, 30, 40, 50, 25] one value at a time:
| Step | Structure | Action |
|---|---|---|
Insert 10 | 10 | First node becomes the root; balanced |
Insert 20 | 10(_, 20) | Goes right of 10; still balanced |
Insert 30 | 20(10, 30) | Right-Right at 10, so one left rotation lifts 20 to the root |
Insert 40 | 20(10, 30(_, 40)) | Goes right of 30; every balance factor stays within ±1 |
Insert 50 | 20(10, 40(30, 50)) | Right-Right at 30, so a left rotation at 30 lifts 40 |
Insert 25 | 30(20(10, 25), 40(_, 50)) | Right-Left at 20: right-rotate 40's subtree, then left-rotate 20 |
When to use an AVL tree
| Use it when | Avoid it when |
|---|---|
| Lookups vastly outnumber inserts and you want the tightest possible height | Inserts and deletes dominate - the extra rotations and rebalancing cost more than a red-black tree's |
You need guaranteed O(log n) worst case, even for adversarial or sorted input | A plain hash table would do - you don't need ordered traversal or range queries |
| You need ordered operations: in-order traversal, predecessor/successor, range queries | The data set is tiny - a plain BST or sorted array is simpler and fast enough |
| Data may arrive already sorted, which would turn an unbalanced BST into a linked list | You can't afford the per-node height field's extra memory in a very tight footprint |
AVL Tree code
A clean, runnable AVL Tree implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
AVL Tree code in Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6 self.height = 17
8
9def height(node):10 return node.height if node else 011
12
13def update(node):14 node.height = 1 + max(height(node.left), height(node.right))15
16
17def rotate_right(y):18 x = y.left19 y.left = x.right20 x.right = y21 update(y)22 update(x)23 return x24
25
26def rotate_left(x):27 y = x.right28 x.right = y.left29 y.left = x30 update(x)31 update(y)32 return y33
34
35def insert(node, key):36 if node is None:37 return Node(key)38 if key < node.key:39 node.left = insert(node.left, key)40 else:41 node.right = insert(node.right, key)42 update(node)43 balance = height(node.left) - height(node.right)44 # Four imbalance cases: LL, RR, LR, RL45 if balance > 1 and key < node.left.key:46 return rotate_right(node)47 if balance < -1 and key > node.right.key:48 return rotate_left(node)49 if balance > 1:50 node.left = rotate_left(node.left)51 return rotate_right(node)52 if balance < -1:53 node.right = rotate_right(node.right)54 return rotate_left(node)55 return node56
57
58def inorder(node):59 if node is None:60 return []61 return inorder(node.left) + [node.key] + inorder(node.right)62
63
64root = None65for key in [10, 20, 30, 40, 50, 25]:66 root = insert(root, key)67
68print("Inorder:", inorder(root))69print("Root:", root.key, "| tree height:", root.height)AVL Tree code in JavaScript
JavaScript
1class Node {2 constructor(key) {3 this.key = key;4 this.left = null;5 this.right = null;6 this.height = 1;7 }8}9
10const height = (n) => (n ? n.height : 0);11const update = (n) => {12 n.height = 1 + Math.max(height(n.left), height(n.right));13};14const balance = (n) => height(n.left) - height(n.right);15
16function rotateRight(y) {17 const x = y.left;18 y.left = x.right;19 x.right = y;20 update(y);21 update(x);22 return x;23}24
25function rotateLeft(x) {26 const y = x.right;27 x.right = y.left;28 y.left = x;29 update(x);30 update(y);31 return y;32}33
34function insert(node, key) {35 if (!node) return new Node(key);36 if (key < node.key) node.left = insert(node.left, key);37 else node.right = insert(node.right, key);38 update(node);39 const b = balance(node);40 // Four rebalancing cases: LL, RR, LR, RL41 if (b > 1 && key < node.left.key) return rotateRight(node);42 if (b < -1 && key > node.right.key) return rotateLeft(node);43 if (b > 1) {44 node.left = rotateLeft(node.left);45 return rotateRight(node);46 }47 if (b < -1) {48 node.right = rotateRight(node.right);49 return rotateLeft(node);50 }51 return node;52}53
54function inorder(node, out = []) {55 if (!node) return out;56 inorder(node.left, out);57 out.push(node.key);58 inorder(node.right, out);59 return out;60}61
62let root = null;63for (const key of [10, 20, 30, 40, 50, 25]) root = insert(root, key);64console.log("Root after rebalancing:", root.key);65console.log("Inorder:", inorder(root).join(" "));AVL Tree code in Java
Java
1public class Main {2 static class Node {3 int key, height = 1;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static int height(Node n) { return n == null ? 0 : n.height; }9 static int balance(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }10 static void update(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }11
12 static Node rotateRight(Node y) {13 Node x = y.left;14 y.left = x.right;15 x.right = y;16 update(y); update(x);17 return x;18 }19
20 static Node rotateLeft(Node x) {21 Node y = x.right;22 x.right = y.left;23 y.left = x;24 update(x); update(y);25 return y;26 }27
28 static Node insert(Node node, int key) {29 if (node == null) return new Node(key);30 if (key < node.key) node.left = insert(node.left, key);31 else node.right = insert(node.right, key);32 update(node);33 int b = balance(node);34 // Four imbalance cases: LL, RR, LR, RL35 if (b > 1 && key < node.left.key) return rotateRight(node);36 if (b < -1 && key > node.right.key) return rotateLeft(node);37 if (b > 1) { node.left = rotateLeft(node.left); return rotateRight(node); }38 if (b < -1) { node.right = rotateRight(node.right); return rotateLeft(node); }39 return node;40 }41
42 static void inorder(Node n, StringBuilder sb) {43 if (n == null) return;44 inorder(n.left, sb);45 sb.append(n.key).append(" ");46 inorder(n.right, sb);47 }48
49 public static void main(String[] args) {50 Node root = null;51 int[] keys = {10, 20, 30, 40, 50, 25};52 for (int k : keys) root = insert(root, k);53 StringBuilder sb = new StringBuilder();54 inorder(root, sb);55 System.out.println("Inorder: " + sb.toString().trim());56 System.out.println("Root after rebalancing: " + root.key + " (height " + root.height + ")");57 }58}AVL Tree code in C++
C++
1#include <algorithm>2#include <iostream>3
4struct Node {5 int value;6 int height = 1;7 Node* left = nullptr;8 Node* right = nullptr;9 explicit Node(int v) : value(v) {}10};11
12int height(const Node* n) { return n ? n->height : 0; }13int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }14void updateHeight(Node* n) {15 n->height = 1 + std::max(height(n->left), height(n->right));16}17
18Node* rotateRight(Node* y) {19 Node* x = y->left;20 y->left = x->right;21 x->right = y;22 updateHeight(y);23 updateHeight(x);24 return x;25}26
27Node* rotateLeft(Node* x) {28 Node* y = x->right;29 x->right = y->left;30 y->left = x;31 updateHeight(x);32 updateHeight(y);33 return y;34}35
36Node* insert(Node* node, int value) {37 if (node == nullptr) return new Node(value);38 if (value < node->value) node->left = insert(node->left, value);39 else node->right = insert(node->right, value);40 updateHeight(node);41 int balance = balanceFactor(node);42 // Four rebalancing cases: LL, RR, LR, RL43 if (balance > 1 && value < node->left->value) return rotateRight(node);44 if (balance < -1 && value > node->right->value) return rotateLeft(node);45 if (balance > 1) {46 node->left = rotateLeft(node->left);47 return rotateRight(node);48 }49 if (balance < -1) {50 node->right = rotateRight(node->right);51 return rotateLeft(node);52 }53 return node;54}55
56void inorder(const Node* n) {57 if (n == nullptr) return;58 inorder(n->left);59 std::cout << n->value << "(h" << n->height << ") ";60 inorder(n->right);61}62
63int main() {64 Node* root = nullptr;65 for (int value : {10, 20, 30, 40, 50, 25}) root = insert(root, value);66 std::cout << "Root after rebalancing: " << root->value << "\n";67 std::cout << "In-order: ";68 inorder(root);69 std::cout << "\n";70 return 0;71}AVL Tree code in C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value, height;6 struct Node* left;7 struct Node* right;8} Node;9
10int height(const Node* n) { return n ? n->height : 0; }11int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }12int maxInt(int a, int b) { return a > b ? a : b; }13
14Node* newNode(int value) {15 Node* n = calloc(1, sizeof(Node));16 n->value = value;17 n->height = 1;18 return n;19}20
21void updateHeight(Node* n) {22 n->height = 1 + maxInt(height(n->left), height(n->right));23}24
25Node* rotateRight(Node* y) {26 Node* x = y->left;27 y->left = x->right;28 x->right = y;29 updateHeight(y);30 updateHeight(x);31 return x;32}33
34Node* rotateLeft(Node* x) {35 Node* y = x->right;36 x->right = y->left;37 y->left = x;38 updateHeight(x);39 updateHeight(y);40 return y;41}42
43Node* insert(Node* node, int value) {44 if (node == NULL) return newNode(value);45 if (value < node->value) node->left = insert(node->left, value);46 else node->right = insert(node->right, value);47 updateHeight(node);48 int balance = balanceFactor(node);49 // Four rebalancing cases: LL, RR, LR, RL50 if (balance > 1 && value < node->left->value) return rotateRight(node);51 if (balance < -1 && value > node->right->value) return rotateLeft(node);52 if (balance > 1) {53 node->left = rotateLeft(node->left);54 return rotateRight(node);55 }56 if (balance < -1) {57 node->right = rotateRight(node->right);58 return rotateLeft(node);59 }60 return node;61}62
63void inorder(const Node* n) {64 if (n == NULL) return;65 inorder(n->left);66 printf("%d(h%d) ", n->value, n->height);67 inorder(n->right);68}69
70int main(void) {71 int values[] = {10, 20, 30, 40, 50, 25};72 Node* root = NULL;73 for (int i = 0; i < 6; i++) root = insert(root, values[i]);74 printf("Root after rebalancing: %d\n", root->value);75 printf("In-order: ");76 inorder(root);77 printf("\n");78 return 0;79}AVL Tree FAQ
What is a balance factor in an AVL tree?
The balance factor of a node is the height of its left subtree minus the height of its right subtree. An AVL tree keeps every node's balance factor at -1, 0, or +1; if an insertion pushes it outside that range, a rotation restores balance.
What is the difference between an AVL tree and a red-black tree?
Both are self-balancing BSTs with
O(log n) operations. AVL trees are more strictly balanced, so lookups are slightly faster, but they may do more rotations on insert/delete. Red-black trees are more loosely balanced, favoring fewer rotations - which is why many standard libraries use them for maps and sets.Why use an AVL tree over a plain binary search tree?
A plain BST can degrade to
O(n) operations if values arrive in sorted order, forming a skewed chain. An AVL tree rotates to stay balanced, guaranteeing O(log n) height and operations regardless of insertion order.Is an AVL tree better than a red-black tree for a database index?
It depends on the workload. AVL trees are more rigidly balanced, so they win when reads dominate and you want the shortest possible search paths. But most databases and language libraries choose red-black trees (or B-trees) because they rebalance with fewer rotations on write-heavy workloads, which matters more when inserts and deletes are frequent.
How many rotations does a single AVL insertion need?
At most one rotation - either a single or a double (two-step) rotation - is ever needed to rebalance the tree after inserting one value. That is because an insertion increases a subtree's height by at most one, so a single fix at the lowest unbalanced ancestor is enough. Deletion is different: it can require up to
O(log n) rotations as the rebalancing propagates toward the root.Do I need to update node heights after every rotation?
Yes - a common bug is rotating pointers correctly but forgetting to recompute the height of the two nodes involved. After each rotation you must update the height of the demoted node first, then the promoted node, because the promoted node's height depends on its new children. Skipping this leaves stale balance factors that break future rebalancing decisions.
Related resources
More visualizations
