TreesData structureaka height-balanced BST, Adelson-Velsky and Landis tree

AVL Tree

A self-balancing BST that keeps every node's subtree heights within 1 of each other using rotations, guaranteeing O(log n) operations.

▶ Visualize Pattern: Binary Search Practice (2)

Progress

Definition

An AVL tree is a Binary Search Tree with an extra invariant: for every node, the balance factor height(left) - height(right) is -1, 0 or +1. Whenever an insert or delete breaks this, one or two local rotations restore it. The invariant forces the height to be at most 1.44 log₂(n + 2), so search, insert and delete are O(log n) in the worst case, not just on average.

AVL trees are the strictest of the common balanced trees: they are shallower than Red-Black Trees (better for read-heavy workloads) but perform more rotations during updates. Each node stores its height (or balance factor), which costs one extra integer per node.

self-balancingrotationsbalance factorO(log n) guaranteedBST

Intuition

A mental model before the formal terms.

Imagine a mobile hanging from the ceiling. If one arm gets much heavier than the other, it tips. A rotation is like re-hanging the mobile from a different knot: the same pieces, the same left-to-right order, but the heavy arm is now closer to the pivot. AVL trees do this re-hanging whenever any sub-mobile tips by more than one level.

Because only the ancestors of the inserted node can change height, and a single rotation restores the height of the subtree it fixes, at most one rotation (single or double) per insert is needed. Deletion may need one at every level on the way back up.

How it works

Insert exactly as in a BST, then walk back up the recursion updating height = 1 + max(h(left), h(right)) at each ancestor.
At each ancestor compute bf = h(left) - h(right). If bf > 1 the node is left-heavy; if bf < -1 it is right-heavy.
Left-Left (bf > 1 and key went into left child's left): right rotation. Right-Right: left rotation. Left-Right (bf > 1 and key went into left child's right): left-rotate the left child, then right-rotate the node. Right-Left: mirror image.
A right rotation at y with left child x: y.left = x.right; x.right = y, then recompute heights of y then x. The inorder sequence x.left, x, x.right, y, y.right is unchanged.
Delete as in a BST (successor replacement), then rebalance every ancestor on the way up using the same four cases, deciding the case by the balance factor of the taller child instead of the inserted key.

Why it works

Rotations preserve the BST property because they only reorder parent-child links among three consecutive inorder positions, never the inorder sequence itself.

Let N(h) be the minimum number of nodes in an AVL tree of height h. Then N(h) = N(h-1) + N(h-2) + 1, a Fibonacci-like recurrence, so N(h) ≥ φ^h and h ≤ log_φ(n) ≈ 1.44 log₂ n. Height is O(log n), hence every path-bound operation is O(log n).

After an insert, the rotated subtree returns to the height it had before the insert, so no ancestor above it can be unbalanced; the rebalance terminates after one fix.

Operations

Operation	Description	Cost
search(key)	Standard BST search; height is bounded so it is O(log n).	O(log n)
insert(key)	BST insert followed by height updates and at most one single/double rotation.	O(log n)
delete(key)	BST delete followed by rebalancing, possibly at every ancestor.	O(log n)
rotateLeft / rotateRight	Constant-time pointer surgery on three nodes plus two height updates.	O(1)
min / max / successor	Same as BST, with the logarithmic bound.	O(log n)
inorder traversal	Sorted output.	O(n)

Recognition

How to tell a problem wants this.

You need guaranteed O(log n) ordered operations and cannot trust the input distribution.
The problem says "sorted order must be maintained under many inserts and deletes" or "order statistics under updates" (augment nodes with subtree sizes).
Lookups dominate updates, where AVL's shallower height beats a red-black tree.

“sorted array” → Binary Search “binary tree” → Tree Traversal

Interactive demo

Play, step, change the input. ← → and space work too.

Commands — insert N commands separated by commas

Empty tree

1/63Empty AVL tree. Each node shows its balance factor bf = height(left) − height(right); the invariant is |bf| ≤ 1 everywhere.

Comparing / rebalancingInsertion pathNewly insertedMoved by a rotation

PseudocodeLearn AVL Tree →

1insert(node, key): BST insert recursively
2update height(node); bf = height(left) - height(right)
3if bf > 1 and key < node.left.key:  LL → rotateRight(node)
4if bf < -1 and key > node.right.key: RR → rotateLeft(node)
5if bf > 1 and key > node.left.key:  LR → rotateLeft(node.left), then rotateRight(node)
6if bf < -1 and key < node.right.key: RL → rotateRight(node.right), then rotateLeft(node)
7return node (possibly the new subtree root)

Variables

height0

Complexity

access O(log n)

search O(log n)

insert O(log n)

delete O(log n)

Speed

Pseudocode

1insert(node, key):
2  if node is null: return new Node(key)
3  standard BST descent
4  node.height = 1 + max(h(node.left), h(node.right))
5  bf = h(node.left) - h(node.right)
6  if bf > 1 and key < node.left.key: return rotateRight(node)
7  if bf < -1 and key > node.right.key: return rotateLeft(node)
8  if bf > 1: node.left = rotateLeft(node.left); return rotateRight(node)
9  if bf < -1: node.right = rotateRight(node.right); return rotateLeft(node)
10  return node

Implementation

1from typing import Optional
2 
3 
41 · Node with cached height
5class AVLNode:
6    def __init__(self, key: int) -> None:
7        self.key = key
8        self.height = 1
9        self.left: Optional["AVLNode"] = None
10        self.right: Optional["AVLNode"] = None
11 
12 
13class AVLTree:
14    def __init__(self) -> None:
15        self.root: Optional[AVLNode] = None
16 
172 · Height and balance helpers
18    @staticmethod
19    def _h(n: Optional[AVLNode]) -> int:
20        return n.height if n else 0
21 
22    def _balance(self, n: Optional[AVLNode]) -> int:
23        return self._h(n.left) - self._h(n.right) if n else 0
24 
25    def _update(self, n: AVLNode) -> None:
26        n.height = 1 + max(self._h(n.left), self._h(n.right))
27 
283 · Rotations
29    def _rotate_right(self, y: AVLNode) -> AVLNode:
30        x = y.left
31        assert x is not None
32        y.left = x.right
33        x.right = y
34        self._update(y)
35        self._update(x)
36        return x
37 
38    def _rotate_left(self, x: AVLNode) -> AVLNode:
39        y = x.right
40        assert y is not None
41        x.right = y.left
42        y.left = x
43        self._update(x)
44        self._update(y)
45        return y
46 
474 · Rebalance one node (four cases)
48    def _rebalance(self, n: AVLNode) -> AVLNode:
49        self._update(n)
50        b = self._balance(n)
51        if b > 1:
52            if self._balance(n.left) < 0:  # LR
53                n.left = self._rotate_left(n.left)  # type: ignore[arg-type]
54            return self._rotate_right(n)  # LL
55        if b < -1:
56            if self._balance(n.right) > 0:  # RL
57                n.right = self._rotate_right(n.right)  # type: ignore[arg-type]
58            return self._rotate_left(n)  # RR
59        return n
60 
615 · Insert then rebalance on the way up
62    def insert(self, key: int) -> None:
63        def go(n: Optional[AVLNode]) -> AVLNode:
64            if n is None:
65                return AVLNode(key)
66            if key < n.key:
67                n.left = go(n.left)
68            elif key > n.key:
69                n.right = go(n.right)
70            else:
71                return n
72            return self._rebalance(n)
73 
74        self.root = go(self.root)
75 
766 · Delete (BST cases) then rebalance on the way up
77    def remove(self, key: int) -> None:
78        def min_node(n: AVLNode) -> AVLNode:
79            while n.left is not None:
80                n = n.left
81            return n
82 
83        def go(n: Optional[AVLNode], k: int) -> Optional[AVLNode]:
84            if n is None:
85                return None
86            if k < n.key:
87                n.left = go(n.left, k)
88            elif k > n.key:
89                n.right = go(n.right, k)
90            else:
91                if n.left is None or n.right is None:
92                    return n.left or n.right
93                succ = min_node(n.right)
94                n.key = succ.key
95                n.right = go(n.right, succ.key)
96            return self._rebalance(n)
97 
98        self.root = go(self.root, key)
99 
100    def contains(self, key: int) -> bool:
101        cur = self.root
102        while cur is not None:
103            if key == cur.key:
104                return True
105            cur = cur.left if key < cur.key else cur.right
106        return False
107 
108    def inorder(self) -> list[int]:
109        out: list[int] = []
110 
111        def go(n: Optional[AVLNode]) -> None:
112            if n is None:
113                return
114            go(n.left)
115            out.append(n.key)
116            go(n.right)
117 
118        go(self.root)
119        return out

Walkthrough

_h is a @staticmethod returning 0 for None; _balance and _update build on it.
Rotations assert the child is not None to satisfy type checkers and document the invariant.
_rebalance mirrors the four cases; the # type: ignore comments acknowledge that the balance factor, not the type system, proves the child exists.
insert and remove use nested go closures that return the rebalanced subtree.
n.left or n.right returns whichever child exists (nodes are always truthy).

Complexity (this implementation)

time O(log n) insert, delete, search · space O(log n) recursion

Balanced height (~1.44 log2 n) keeps recursion under Python's 1000-frame limit for any realistic size.

Language notes

The _ prefix marks helpers as internal by convention; nothing is truly private.
assert can be stripped with python -O, so use it only for invariants that cannot fail, as here.
Attribute access is comparatively slow in CPython; an AVL tree in Python is many times slower than bisect on a list for small n.

Common mistakes in this language

Mixing up which node is x and which is y in the rotations.
Forgetting return self._rebalance(n) at the end of the recursive branch and returning the unbalanced node.
Updating height on only one of the two rotated nodes.

Language differences that matter here

Balanced-tree stdlib: C++ std::map/std::set (red-black); nothing built in for JS/TS/Python.
Null-safety of rotation children: TS uses !, Python uses assert, C++ and JS trust the invariant silently.
C++ frees the removed node explicitly in remove; the other languages drop the reference.

Complexity

Operation	Average	Worst	Note
Access	O(log n)	O(log n)	kth element with subtree sizes.
Search	O(log n)	O(log n)
Insert	O(log n)	O(log n)	At most one single or double rotation.
Delete	O(log n)	O(log n)	Up to O(log n) rotations.
Update	O(log n)	O(log n)
Rotation	O(1)	O(1)
Min / Max / Successor	O(log n)	O(log n)
Inorder traversal	O(n)	O(n)
Space	O(n)		Height ≤ 1.44 log₂(n + 2). One extra int per node for height.

Advantages & disadvantages

Advantages

Worst-case O(log n) for all dictionary operations regardless of input order.
Shallowest of the standard balanced trees, so lookups are fast.
Easy to augment (subtree size, sum) since rotations touch only a constant number of nodes.

Disadvantages

More rotations on update than a Red-Black Tree; deletes can rotate at every level.
One extra height/balance field per node and more code than a plain BST.
Still pointer-based with poor locality; for on-disk data a B-Tree is far better.

Use cases

Ordered in-memory dictionaries in read-heavy systems and some database indexes.
Order-statistic trees for rank/select queries under insertions and deletions.
Interval and sweep-line structures where guaranteed height matters.
The canonical interview example of self-balancing: expect to explain the four rotation cases.

Use it when

Ordered set/map with a hard O(log n) worst-case requirement.
Lookups vastly outnumber updates and you want the shallowest tree.
Augmented trees (order statistics, interval trees) where rotations are easy to keep consistent.

Avoid it when

Update-heavy workloads — a Red-Black Tree rotates less often.
Only exact lookups are needed — Hash Map.
Disk-resident or very large data — a B-Tree minimizes I/O.

Alternatives

Red-Black Tree Skip List B-Tree Binary Search Tree

Compare: AVL Tree vs Red-Black Tree

Common mistakes

Updating heights in the wrong order after a rotation (the lower node y must be updated before the new root x).
Choosing single vs double rotation by the inserted key when deleting; use the child's balance factor, which works for both.
Forgetting to rebalance on delete, or only rebalancing the node where the delete happened rather than every ancestor.
Storing balance factors but updating them with the height formula (or vice versa).

Interview patterns

Explain the four cases (LL, RR, LR, RL) with a three-node example.
Prove the height bound with the minimal-nodes Fibonacci recurrence.
Compare AVL vs red-black: height bound, rotation count, which library uses which.
Augment with subtree size for "count of elements less than x" in O(log n).

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Where does O(n log n) come from?Beginner
Recursion versus iterationIntermediate

Mock interviews

Minimum Size Subarray SumIntermediate
Search in Rotated Sorted ArrayIntermediate

Interview problems

Kth Smallest Element in a BSTmedium Validate Binary Search Treemedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related