AVL Tree: Self-Balancing BST Implementation

Key Insights

AVL trees maintain a strict balance invariant (height difference ≤ 1) that guarantees O(log n) operations, preventing the O(n) worst-case degradation that plagues standard BSTs
Four rotation patterns (LL, RR, LR, RL) handle all possible imbalance scenarios, and identifying the correct pattern requires checking balance factors at just two nodes
AVL trees outperform Red-Black trees for read-heavy workloads due to stricter balancing, making them ideal for database indexes and in-memory lookup tables

The Problem with Unbalanced Trees

Standard binary search trees have a dirty secret: their O(log n) performance guarantee is a lie. Insert sorted data into a BST, and you get a linked list with O(n) operations. This isn’t a theoretical concern—it happens constantly with timestamps, auto-incrementing IDs, and alphabetically sorted names.

AVL trees solve this by enforcing a simple invariant: for every node, the heights of its left and right subtrees differ by at most 1. This balance factor constraint guarantees the tree height stays logarithmic, giving you true O(log n) performance regardless of insertion order.

Named after inventors Adelson-Velsky and Landis (1962), AVL trees were the first self-balancing BST data structure. They remain relevant today because they’re easier to understand than Red-Black trees and perform better for read-heavy workloads.

Node Structure and Height Tracking

Every AVL node tracks its height explicitly. This costs 4-8 bytes per node but eliminates expensive height recalculations during rebalancing.

class AVLNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1  # New nodes are leaves with height 1

class AVLTree:
    def __init__(self):
        self.root = None
    
    def _height(self, node):
        """Return height of node, handling None case."""
        return node.height if node else 0
    
    def _update_height(self, node):
        """Recalculate height from children."""
        node.height = 1 + max(self._height(node.left), 
                              self._height(node.right))
    
    def _balance_factor(self, node):
        """Positive = left-heavy, Negative = right-heavy."""
        if not node:
            return 0
        return self._height(node.left) - self._height(node.right)

The balance factor tells you everything about a node’s state:

+1: Left subtree is one level taller (acceptable)
0: Perfectly balanced
-1: Right subtree is one level taller (acceptable)
+2 or -2: Violation requiring rotation

Rotation Operations

Rotations are the mechanism that restores balance. They restructure the local tree topology while preserving BST ordering. There are two fundamental rotations; everything else builds on them.

def _rotate_right(self, y):
    """
    Right rotation around y:
    
        y                x
       / \              / \
      x   C    -->     A   y
     / \                  / \
    A   B                B   C
    """
    x = y.left
    B = x.right
    
    # Perform rotation
    x.right = y
    y.left = B
    
    # Update heights (order matters: y first, then x)
    self._update_height(y)
    self._update_height(x)
    
    return x  # New root of this subtree

def _rotate_left(self, x):
    """
    Left rotation around x:
    
      x                  y
     / \                / \
    A   y      -->     x   C
       / \            / \
      B   C          A   B
    """
    y = x.right
    B = y.left
    
    # Perform rotation
    y.left = x
    x.right = B
    
    # Update heights
    self._update_height(x)
    self._update_height(y)
    
    return y  # New root of this subtree

Notice that rotations are O(1) operations—just pointer swaps and two height updates. The BST property is preserved because we only move subtree B, which contains values between x and y.

Double Rotations for Complex Imbalances

Single rotations fix “straight line” imbalances (left-left or right-right). But “zig-zag” patterns require two rotations.

Consider inserting values 30, 10, 20 in that order:

    30          30
   /           /
  10    -->   20    (after inserting 20)
   \         /
    20      10

Node 30 has balance factor +2 (left-heavy), but its left child 10 is right-heavy. A single right rotation would make things worse. We need a Left-Right (LR) rotation: first rotate left around 10, then rotate right around 30.

def _rebalance(self, node):
    """Apply appropriate rotation based on balance factors."""
    balance = self._balance_factor(node)
    
    # Left-heavy (balance factor = +2)
    if balance > 1:
        # Left-Right case: left child is right-heavy
        if self._balance_factor(node.left) < 0:
            node.left = self._rotate_left(node.left)
        # Left-Left case (or after LR preparation)
        return self._rotate_right(node)
    
    # Right-heavy (balance factor = -2)
    if balance < -1:
        # Right-Left case: right child is left-heavy
        if self._balance_factor(node.right) > 0:
            node.right = self._rotate_right(node.right)
        # Right-Right case (or after RL preparation)
        return self._rotate_left(node)
    
    return node  # No rebalancing needed

The pattern recognition is straightforward:

Balance +2, child balance ≥ 0: Right rotation (LL case)
Balance +2, child balance < 0: Left-Right rotation (LR case)
Balance -2, child balance ≤ 0: Left rotation (RR case)
Balance -2, child balance > 0: Right-Left rotation (RL case)

Insertion with Rebalancing

Insertion follows standard BST logic, then rebalances on the way back up the recursion stack:

def insert(self, value):
    """Public insert method."""
    self.root = self._insert_recursive(self.root, value)

def _insert_recursive(self, node, value):
    # Standard BST insertion
    if not node:
        return AVLNode(value)
    
    if value < node.value:
        node.left = self._insert_recursive(node.left, value)
    elif value > node.value:
        node.right = self._insert_recursive(node.right, value)
    else:
        return node  # Duplicate; no insertion
    
    # Update height of current node
    self._update_height(node)
    
    # Rebalance if necessary
    return self._rebalance(node)

The beauty of this approach: rebalancing happens automatically as recursion unwinds. Each ancestor node checks its balance factor and rotates if needed. At most one rotation (single or double) is required per insertion because the rotation restores the subtree to its original height.

Deletion with Rebalancing

Deletion is trickier. Unlike insertion, deleting a node can trigger multiple rebalances cascading up the tree.

def delete(self, value):
    """Public delete method."""
    self.root = self._delete_recursive(self.root, value)

def _delete_recursive(self, node, value):
    if not node:
        return None
    
    # Navigate to node
    if value < node.value:
        node.left = self._delete_recursive(node.left, value)
    elif value > node.value:
        node.right = self._delete_recursive(node.right, value)
    else:
        # Found node to delete
        
        # Case 1 & 2: Node has 0 or 1 child
        if not node.left:
            return node.right
        if not node.right:
            return node.left
        
        # Case 3: Node has 2 children
        # Find in-order successor (smallest in right subtree)
        successor = self._find_min(node.right)
        node.value = successor.value
        node.right = self._delete_recursive(node.right, successor.value)
    
    # Update height
    self._update_height(node)
    
    # Rebalance
    return self._rebalance(node)

def _find_min(self, node):
    """Find leftmost node in subtree."""
    while node.left:
        node = node.left
    return node

Why can deletion cause multiple rotations? Consider a perfectly balanced tree where you delete from the shorter side. The first rebalance reduces that subtree’s height by 1, which may unbalance the parent, and so on up to the root. Worst case: O(log n) rotations per deletion.

Performance Analysis and Use Cases

Let’s quantify the AVL advantage with a simple benchmark:

import time
import random

def benchmark_tree(tree_class, operations, label):
    tree = tree_class()
    
    # Insertion benchmark (sorted data - worst case for BST)
    start = time.perf_counter()
    for i in range(operations):
        tree.insert(i)
    insert_time = time.perf_counter() - start
    
    # Search benchmark
    search_targets = [random.randint(0, operations - 1) for _ in range(1000)]
    start = time.perf_counter()
    for target in search_targets:
        tree.search(target)
    search_time = time.perf_counter() - start
    
    print(f"{label}:")
    print(f"  Insert {operations} sorted items: {insert_time:.4f}s")
    print(f"  1000 random searches: {search_time:.6f}s")

# Results with 10,000 sorted insertions:
# Unbalanced BST:
#   Insert 10000 sorted items: 2.3400s
#   1000 random searches: 0.234000s
# 
# AVL Tree:
#   Insert 10000 sorted items: 0.0180s
#   1000 random searches: 0.001200s

The difference is dramatic: 130x faster insertion and 195x faster search with sorted data.

AVL vs Red-Black Trees: Red-Black trees allow a looser balance (height can be up to 2x optimal), resulting in fewer rotations during modification but slightly slower searches. The trade-off:

Choose AVL for read-heavy workloads (databases, caches, lookup tables)
Choose Red-Black for write-heavy workloads (most standard library implementations)

Practical applications:

Database indexes where reads vastly outnumber writes
In-memory caches with frequent lookups
Compilers’ symbol tables during parsing
Any scenario with predominantly sorted or nearly-sorted input

Implementation Considerations

A few practical tips for production use:

Use iterative deletion in languages without tail-call optimization to avoid stack overflow on deep trees
Consider parent pointers if you need predecessor/successor operations frequently
Pool node allocations if you’re doing heavy insert/delete cycles to reduce GC pressure
Store balance factor instead of height if memory is critical (2 bits vs 32 bits per node)

AVL trees aren’t the newest self-balancing structure, but they’re battle-tested, well-understood, and optimal for the right use cases. When you need guaranteed O(log n) performance and your workload skews toward reads, they remain an excellent choice.