AVL Tree

An AVL tree is a self-balancing binary search tree where the height difference between the left and right subtrees of any node (the balance factor) is at most 1.

Named after its inventors Adelson-Velsky and Landis (1962) — the first self-balancing BST ever invented.

Core Concept: Balance Factor

Balance Factor (BF) = Height(Left Subtree) - Height(Right Subtree)
BF Value Meaning
-1, 0, +1 ✅ Balanced — valid AVL node
≤ -2 ❌ Right-heavy — rotation needed
≥ +2 ❌ Left-heavy — rotation needed

Structure

graph TD A["30 (BF=0)"] B["20 (BF=0)"] C["40 (BF=0)"] D["10 (BF=0)"] E["25 (BF=0)"] A --> B A --> C B --> D B --> E

The 4 Rotation Cases

When a node becomes unbalanced after insertion or deletion, one of four rotations restores balance:

1. Left-Left (LL) → Right Rotation

Imbalance in the left child's left subtree.

    z                y
   / \             /   \
  y   T4   →     x     z
 / \            / \   / \
x   T3         T1 T2 T3 T4

2. Right-Right (RR) → Left Rotation

Imbalance in the right child's right subtree.

  z                  y
 / \               /   \
T1   y    →       z     x
    / \          / \   / \
   T2   x       T1 T2 T3 T4
       / \
      T3  T4

3. Left-Right (LR) → Left then Right Rotation

Imbalance in the left child's right subtree.

  z          z          x
 / \        / \        / \
y   T4 →  x   T4 →   y   z
 \        /          / \ / \
  x      y          T1 T2T3 T4

4. Right-Left (RL) → Right then Left Rotation

Imbalance in the right child's left subtree.

  z            z              x
 / \          / \            / \
T1   y   →  T1   x    →    z   y
    /              \       /\ / \
   x                y    T1 T2T3 T4

Time & Space Complexity

Operation Average Worst Case
Search O(log n) O(log n)
Insert O(log n) O(log n)
Delete O(log n) O(log n)
Space O(n) O(n)

The worst case is guaranteed O(log n) — unlike a regular BST which degrades to O(n) on sorted input.

Python Implementation

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1  # New node starts at height 1


class AVLTree:

    # ── Helpers ──────────────────────────────────────────

    def get_height(self, node):
        return node.height if node else 0

    def get_balance(self, node):
        if not node:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)

    def update_height(self, node):
        node.height = 1 + max(self.get_height(node.left),
                               self.get_height(node.right))

    # ── Rotations ────────────────────────────────────────

    def rotate_right(self, z):
        y = z.left
        T3 = y.right

        y.right = z          # perform rotation
        z.left = T3

        self.update_height(z)
        self.update_height(y)
        return y             # new subtree root

    def rotate_left(self, z):
        y = z.right
        T2 = y.left

        y.left = z
        z.right = T2

        self.update_height(z)
        self.update_height(y)
        return y

    # ── Insert ───────────────────────────────────────────

    def insert(self, node, key):
        # 1. Standard BST insert
        if not node:
            return Node(key)
        if key < node.key:
            node.left = self.insert(node.left, key)
        elif key > node.key:
            node.right = self.insert(node.right, key)
        else:
            return node  # duplicates not allowed

        # 2. Update height
        self.update_height(node)

        # 3. Get balance factor and rebalance
        balance = self.get_balance(node)

        # LL
        if balance > 1 and key < node.left.key:
            return self.rotate_right(node)
        # RR
        if balance < -1 and key > node.right.key:
            return self.rotate_left(node)
        # LR
        if balance > 1 and key > node.left.key:
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        # RL
        if balance < -1 and key < node.right.key:
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)

        return node

    # ── Search ───────────────────────────────────────────

    def search(self, node, key):
        if not node or node.key == key:
            return node
        if key < node.key:
            return self.search(node.left, key)
        return self.search(node.right, key)

    # ── In-order Traversal ───────────────────────────────

    def inorder(self, node, result=None):
        if result is None:
            result = []
        if node:
            self.inorder(node.left, result)
            result.append(node.key)
            self.inorder(node.right, result)
        return result


# ── Usage ─────────────────────────────────────────────────
tree = AVLTree()
root = None

for key in [30, 20, 10, 25, 40]:
    root = tree.insert(root, key)

print(tree.inorder(root))   # [10, 20, 25, 30, 40]
print(tree.search(root, 25))  # <Node object>

AVL vs. Other Balanced Trees

Feature AVL Tree Red-Black Tree B-Tree
Balance guarantee Strict (BF ≤ 1) Relaxed Relaxed
Search speed ✅ Faster Slightly slower Good for disk
Insert/Delete speed Slightly slower ✅ Faster Good for disk
Rotations per insert ≤ 2 ≤ 2 —
Best for Read-heavy workloads Write-heavy workloads Databases / filesystems

Key Takeaways