Data Structure

AVL Tree

“The Strict Disciplinarian”

Search: O(log n)

Space: O(n)

Self-Balancing: Yes

History

Invented in 1962 by Georgy Adelson-Velsky and Evgenii Landis, the AVL tree was the first data structure to solve the BST's "degenerate line" problem.

It acts like a strict building inspector. Every time you modify the structure, it pulls out a measuring tape. If one side of the tree is more than one level deeper than the other, it forces a "rotation" to fix the symmetry immediately.

Core Property

The Balance Factor

For every node, the height difference between the left and right subtrees must be $-1$ , $0$ , or $+1$ . If it hits $\pm 2$ , the tree is invalid and must be fixed.

How It Works

The AVL tree maintains balance via Rotations. A rotation is a local rearrangement of nodes that fixes height without breaking the sort order.

The Four Cases

LL Case: Left-left heavy. Fixed by a single Right Rotation.
RR Case: Right-right heavy. Fixed by a single Left Rotation.
LR Case: Left-right heavy. Fixed by Left then Right rotation.
RL Case: Right-left heavy. Fixed by Right then Left rotation.

Every insert or delete triggers a trace back up to the root to update heights and rotate if needed.

SearchO(log n)

Guaranteed. The strict balancing ensures the height is always logarithmic.

InsertO(log n)

Finding the spot is fast, but we might have to rotate our way back up.

DeleteO(log n)

Similar to insert, but a deletion might trigger multiple rotations up the tree.

SpaceO(n)

Stores $n$ nodes, plus a tiny integer for 'Height' or 'Balance Factor' on each node.

Code Walkthrough

Complete data structure implementations in multiple programming languages. Select a language to view idiomatic code.

1class AVLNode:
2    """Node for AVL Tree with height tracking."""
3    def __init__(self, val: int):
4        self.val = val
5        self.left: AVLNode | None = None
6        self.right: AVLNode | None = None
7        self.height = 1
8
9
10class AVLTree:
11    """Self-balancing AVL Tree with rotations."""
12    def __init__(self):
13        self.root: AVLNode | None = None
14
15    def _height(self, node: AVLNode | None) -> int:
16        return node.height if node else 0
17
18    def _balance_factor(self, node: AVLNode | None) -> int:
19        return self._height(node.left) - self._height(node.right) if node else 0
20
21    def _update_height(self, node: AVLNode) -> None:
22        node.height = 1 + max(self._height(node.left), self._height(node.right))
23
24    def _rotate_right(self, y: AVLNode) -> AVLNode:
25        """Right rotation for LL case."""
26        x = y.left
27        t2 = x.right
28
29        x.right = y
30        y.left = t2
31
32        self._update_height(y)
33        self._update_height(x)
34        return x
35
36    def _rotate_left(self, x: AVLNode) -> AVLNode:
37        """Left rotation for RR case."""
38        y = x.right
39        t2 = y.left
40
41        y.left = x
42        x.right = t2
43
44        self._update_height(x)
45        self._update_height(y)
46        return y
47
48    def _rebalance(self, node: AVLNode) -> AVLNode:
49        """Rebalance node if needed."""
50        self._update_height(node)
51        balance = self._balance_factor(node)
52
53        # Left-heavy
54        if balance > 1:
55            if self._balance_factor(node.left) < 0:
56                node.left = self._rotate_left(node.left)  # LR case
57            return self._rotate_right(node)  # LL case
58
59        # Right-heavy
60        if balance < -1:
61            if self._balance_factor(node.right) > 0:
62                node.right = self._rotate_right(node.right)  # RL case
63            return self._rotate_left(node)  # RR case
64
65        return node
66
67    def insert(self, val: int) -> None:
68        self.root = self._insert_recursive(self.root, val)
69
70    def _insert_recursive(self, node: AVLNode | None, val: int) -> AVLNode:
71        if not node:
72            return AVLNode(val)
73
74        if val < node.val:
75            node.left = self._insert_recursive(node.left, val)
76        else:
77            node.right = self._insert_recursive(node.right, val)
78
79        return self._rebalance(node)
80
81    def delete(self, val: int) -> None:
82        self.root = self._delete_recursive(self.root, val)
83
84    def _delete_recursive(self, node: AVLNode | None, val: int) -> AVLNode | None:
85        if not node:
86            return None
87
88        if val < node.val:
89            node.left = self._delete_recursive(node.left, val)
90        elif val > node.val:
91            node.right = self._delete_recursive(node.right, val)
92        else:
93            if not node.left:
94                return node.right
95            if not node.right:
96                return node.left
97
98            successor = node.right
99            while successor.left:
100                successor = successor.left
101            node.val = successor.val
102            node.right = self._delete_recursive(node.right, successor.val)
103
104        return self._rebalance(node)

Python • .py

Real World Use Cases

1Databases where read speed is critical
2In-memory sets and dictionaries
3Symbol tables in compilers
4Systems with heavy search loads and infrequent writes

Key Insights

It is rigidly balanced.
Lookups are faster than Red-Black trees because the tree is shallower.
Insertions are slower than Red-Black trees because of the strict rotation rules.
It guarantees $O(log n)$ worst-case for everything.