Balanced Binary Trees

BSTs are great. O(log n) operations. But only if balanced.

Insert sorted values? You get a linked list. O(n) operations. Terrible.

Solution: keep the tree balanced. Automatically.

What's Balance?

A balanced tree has height O(log n). Different definitions exist, but the goal is the same: prevent degeneration.

Height-balanced: For every node, height difference between left and right subtrees ≤ k (commonly k=1).

Weight-balanced: For every node, size of left and right subtrees differ by at most a constant factor.

AVL and Red-Black trees use height-balancing. B-trees use a different approach.

Why Balance Matters

Degenerate BST (sorted insertion):

Height = 4, nodes = 4. O(n).

Balanced BST (same values):

Height = 2, nodes = 4. O(log n).

Balance ensures height stays logarithmic.

AVL Trees

Rule: For every node, |height(left) - height(right)| ≤ 1.

Strictly balanced. Guarantees height ≤ 1.44 log n.

How it works: After insert/delete, check balance. If violated, perform rotations to restore balance.

Rotations

Four cases when node becomes unbalanced:

Left-Left (LL): Left child's left subtree too tall.

      z
     /
    y
   /
  x

Rotate right at z:

    y
   / \
  x   z

Right-Right (RR): Mirror of LL.

  x
   \
    y
     \
      z

Rotate left at x:

    y
   / \
  x   z

Left-Right (LR): Left child's right subtree too tall.

    z
   /
  x
   \
    y

Rotate left at x, then right at z:

    y
   / \
  x   z

Right-Left (RL): Mirror of LR.

AVL Implementation Sketch

class AVLNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1

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

def get_balance(node):
    return get_height(node.left) - get_height(node.right) if node else 0

def rotate_right(z):
    y = z.left
    T3 = y.right
    
    y.right = z
    z.left = T3
    
    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    
    return y

def rotate_left(x):
    y = x.right
    T2 = y.left
    
    y.left = x
    x.right = T2
    
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    
    return y

def insert_avl(root, value):
    if root is None:
        return AVLNode(value)
    
    if value < root.value:
        root.left = insert_avl(root.left, value)
    elif value > root.value:
        root.right = insert_avl(root.right, value)
    else:
        return root  # Duplicate
    
    # Update height
    root.height = 1 + max(get_height(root.left), get_height(root.right))
    
    # Check balance
    balance = get_balance(root)
    
    # Left-Left
    if balance > 1 and value < root.left.value:
        return rotate_right(root)
    
    # Right-Right
    if balance < -1 and value > root.right.value:
        return rotate_left(root)
    
    # Left-Right
    if balance > 1 and value > root.left.value:
        root.left = rotate_left(root.left)
        return rotate_right(root)
    
    # Right-Left
    if balance < -1 and value < root.right.value:
        root.right = rotate_right(root.right)
        return rotate_left(root)
    
    return root

Inserts like BST, then checks balance and rotates if needed. O(log n).

Red-Black Trees

Less strictly balanced than AVL. Allows more imbalance but fewer rotations.

Rules:

Every node is red or black
Root is black
Leaves (null) are black
Red node has black children (no two reds in a row)
Every path from root to leaf has same number of black nodes

Guarantees height ≤ 2 log n. Slightly worse than AVL but faster insertions/deletions (fewer rotations).

Used in C++ std::map, Java TreeMap, Linux kernel.

More complex to implement than AVL. Requires color tracking and more rotation cases.

AVL vs Red-Black

Feature	AVL	Red-Black
Balance	Strict (height diff ≤ 1)	Relaxed (height ≤ 2 log n)
Lookup	Slightly faster	Slightly slower
Insert/Delete	More rotations	Fewer rotations
Use case	Read-heavy	Write-heavy

For most uses, Red-Black is preferred (fewer rotations, good enough balance).

Check if Balanced

def is_balanced(root):
    def check_height(node):
        if node is None:
            return 0
        
        left_height = check_height(node.left)
        if left_height == -1:
            return -1
        
        right_height = check_height(node.right)
        if right_height == -1:
            return -1
        
        if abs(left_height - right_height) > 1:
            return -1
        
        return 1 + max(left_height, right_height)
    
    return check_height(root) != -1

Returns -1 if unbalanced, otherwise height. O(n).

Balancing an Unbalanced BST

Given unbalanced BST, convert to balanced.

Inorder traversal → sorted array
Build balanced BST from sorted array (pick middle as root)

def balance_bst(root):
    # Step 1: Get sorted values
    values = []
    
    def inorder(node):
        if node is None:
            return
        inorder(node.left)
        values.append(node.value)
        inorder(node.right)
    
    inorder(root)
    
    # Step 2: Build balanced BST
    def build(arr):
        if not arr:
            return None
        mid = len(arr) // 2
        root = TreeNode(arr[mid])
        root.left = build(arr[:mid])
        root.right = build(arr[mid+1:])
        return root
    
    return build(values)

O(n). Works for one-time balancing. For ongoing balance, use AVL or Red-Black.

When to Use Balanced Trees

Frequent insertions/deletions with lookups: Use Red-Black. Good balance with fewer rotations.

Read-heavy workload: Use AVL. Stricter balance means slightly faster lookups.

Static data, occasional rebalancing: Build balanced BST from sorted array. Simple, no rotation complexity.

Databases, file systems: Use B-trees. Better for disk I/O (fewer, wider nodes).

The Trade-off

Plain BST: Simple, but can degenerate.

AVL: Strict balance, fast lookups, but more rotations.

Red-Black: Relaxed balance, fewer rotations, but slightly slower lookups.

Understanding balance means understanding:

The height matters for performance
Rotations restore balance locally
Different balancing strategies suit different workloads

Master balanced trees, and you'll use the right structure for your needs (AVL for reads, Red-Black for writes, B-trees for databases).