⚖️ Self-Balancing Trees Fundamentals

🎯 Why Self-Balancing Trees?

Standard Binary Search Trees (BST) can degenerate into a linked list (O(n) height) when keys are inserted in sorted order. Self-balancing trees automatically maintain a height of O(log n), guaranteeing optimal performance for all operations.

All Operations: O(log n) guaranteed | Space: O(n)

The Balancing Problem

Core Insight: Without rebalancing, a BST becomes a linked list when inserting 1,2,3,4,5. Self-balancing trees detect imbalance after insertions/deletions and restructure the tree via rotations to maintain logarithmic height.

Two Main Approaches:

AVL Trees Strict balance (height difference ≤ 1) → Faster lookups
Red-Black Trees Relaxed balance (approximate) → Faster insertions/deletions

📌 Rotations📌 O(log n) Guaranteed📌 Self-Adjusting

# Problem: BST Degeneration
# Insert 1,2,3,4,5 into empty BST:
# 1 -> 1.right = 2 -> 1.right.right = 3 -> etc.
# Results in: 1 - 2 - 3 - 4 - 5 (linked list!)
# Height = n = 5, O(n) operations

# Self-balancing trees fix this:
# After insertion, tree automatically rebalances
# Height remains O(log n)

🔵 AVL Trees - Deep Dive

🎯 Adelson-Velsky and Landis Trees

AVL trees (1962) were the first self-balancing BSTs. They maintain that for every node, the heights of its left and right subtrees differ by at most 1 (balance factor ∈ {-1,0,1}).

Balance Factor: height(left) - height(right)
Violation: When |bf| > 1, rotations are performed
Height: h ≤ 1.44 × log₂(n+2) - 1.328 (very strict!)

# AVL Node Structure
class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1  # Height of node (leaf = 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

🔄 AVL Rotations & Rebalancing

🎯 Four Rotation Cases

Left-Left (LL): Right rotate
Right-Right (RR): Left rotate
Left-Right (LR): Left rotate left child, then right rotate
Right-Left (RL): Right rotate right child, then left rotate

def right_rotate(y):
    x = y.left
    T2 = x.right
    
    # Perform rotation
    x.right = y
    y.left = T2
    
    # Update heights
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    
    return x  # New root

def left_rotate(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

# LL: y is unbalanced (bf=2), left child bf >= 0
def ll_case(y):
    return right_rotate(y)

# RR: y is unbalanced (bf=-2), right child bf <= 0
def rr_case(y):
    return left_rotate(y)

# LR: y is unbalanced (bf=2), left child bf = -1
def lr_case(y):
    y.left = left_rotate(y.left)
    return right_rotate(y)

# RL: y is unbalanced (bf=-2), right child bf = 1
def rl_case(y):
    y.right = right_rotate(y.right)
    return left_rotate(y)

💻 AVL Implementation

class AVLTree:
    def insert(self, root, val):
        # Standard BST insert
        if not root:
            return AVLNode(val)
        if val < root.val:
            root.left = self.insert(root.left, val)
        else:
            root.right = self.insert(root.right, val)
        
        # Update height
        root.height = 1 + max(get_height(root.left), get_height(root.right))
        
        # Get balance factor
        balance = get_balance(root)
        
        # Balance the tree
        # LL Case
        if balance > 1 and val < root.left.val:
            return right_rotate(root)
        # RR Case
        if balance < -1 and val > root.right.val:
            return left_rotate(root)
        # LR Case
        if balance > 1 and val > root.left.val:
            root.left = left_rotate(root.left)
            return right_rotate(root)
        # RL Case
        if balance < -1 and val < root.right.val:
            root.right = right_rotate(root.right)
            return left_rotate(root)
        
        return root
    
    def delete(self, root, val):
        # Standard BST delete
        if not root:
            return None
        if val < root.val:
            root.left = self.delete(root.left, val)
        elif val > root.val:
            root.right = self.delete(root.right, val)
        else:
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            # Two children: find inorder successor
            temp = self.min_value_node(root.right)
            root.val = temp.val
            root.right = self.delete(root.right, temp.val)
        
        if not root:
            return None
        
        # Update height and balance (same as insert)
        root.height = 1 + max(get_height(root.left), get_height(root.right))
        balance = get_balance(root)
        
        # Balancing cases (same logic as insert)
        if balance > 1 and get_balance(root.left) >= 0:
            return right_rotate(root)
        if balance > 1 and get_balance(root.left) < 0:
            root.left = left_rotate(root.left)
            return right_rotate(root)
        if balance < -1 and get_balance(root.right) <= 0:
            return left_rotate(root)
        if balance < -1 and get_balance(root.right) > 0:
            root.right = right_rotate(root.right)
            return left_rotate(root)
        
        return root
    
    def min_value_node(self, root):
        curr = root
        while curr.left:
            curr = curr.left
        return curr

🔴 Red-Black Trees - Deep Dive

🎯 Red-Black Tree Properties

Red-Black trees are self-balancing BSTs where each node has a color (red or black). They maintain balance through color rules rather than strict height balance.

Every node is either red or black
Root is always black
No two consecutive reds (red parent has black children)
Every path from root to leaf has same number of black nodes (black height)

📐 Red-Black Properties & Rules

🎯 The 5 Properties

Property 1: Every node is either red or black
Property 2: The root is black
Property 3: All leaves (NIL) are black
Property 4: If a node is red, both its children are black (no adjacent reds)
Property 5: For each node, all paths from the node to descendant leaves contain the same number of black nodes (black height)

These properties guarantee that the tree height is ≤ 2 × log₂(n+1) — O(log n).

💻 Red-Black Implementation

class RBNode:
    RED = True
    BLACK = False
    
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
        self.color = RBNode.RED  # New nodes are always red

class RedBlackTree:
    def __init__(self):
        self.NIL = RBNode(None)
        self.NIL.color = RBNode.BLACK
        self.NIL.left = self.NIL.right = self.NIL
        self.root = self.NIL
    
    def left_rotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.NIL:
            y.left.parent = x
        y.parent = x.parent
        if x.parent == self.NIL:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y
    
    def right_rotate(self, y):
        x = y.left
        y.left = x.right
        if x.right != self.NIL:
            x.right.parent = y
        x.parent = y.parent
        if y.parent == self.NIL:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        x.right = y
        y.parent = x
    
    def insert(self, key):
        node = RBNode(key)
        node.left = node.right = self.NIL
        
        # Standard BST insert
        parent = self.NIL
        curr = self.root
        while curr != self.NIL:
            parent = curr
            if node.val < curr.val:
                curr = curr.left
            else:
                curr = curr.right
        
        node.parent = parent
        if parent == self.NIL:
            self.root = node
        elif node.val < parent.val:
            parent.left = node
        else:
            parent.right = node
        
        # Fix violations
        self.insert_fixup(node)
    
    def insert_fixup(self, z):
        while z.parent.color == RBNode.RED:
            if z.parent == z.parent.parent.left:
                y = z.parent.parent.right
                if y.color == RBNode.RED:
                    # Case 1: Uncle is red
                    z.parent.color = RBNode.BLACK
                    y.color = RBNode.BLACK
                    z.parent.parent.color = RBNode.RED
                    z = z.parent.parent
                else:
                    # Case 2: Uncle is black
                    if z == z.parent.right:
                        z = z.parent
                        self.left_rotate(z)
                    # Case 3
                    z.parent.color = RBNode.BLACK
                    z.parent.parent.color = RBNode.RED
                    self.right_rotate(z.parent.parent)
            else:  # Mirror case (right side)
                y = z.parent.parent.left
                if y.color == RBNode.RED:
                    z.parent.color = RBNode.BLACK
                    y.color = RBNode.BLACK
                    z.parent.parent.color = RBNode.RED
                    z = z.parent.parent
                else:
                    if z == z.parent.left:
                        z = z.parent
                        self.right_rotate(z)
                    z.parent.color = RBNode.BLACK
                    z.parent.parent.color = RBNode.RED
                    self.left_rotate(z.parent.parent)
        self.root.color = RBNode.BLACK

⚖️ AVL vs Red-Black Comparison

Feature	AVL Tree	Red-Black Tree
Balance Strategy	Height difference ≤ 1	Color properties (black height)
Balance Factor	-1, 0, 1	Not applicable
Height Bound	≈ 1.44 log n	≤ 2 log n
Lookup (Search)	Faster (more strict balance)	Slightly slower
Insert/Delete	Slower (more rotations)	Faster (fewer rotations)
Memory Overhead	Height field (int)	Color field (1 bit)
Rotations per Insert	O(log n) worst-case	O(1) amortized
Use Cases	Read-heavy workloads	Write-heavy workloads
Standard Library	Less common	Java TreeMap, C++ map, Python dict (pre-3.6)

⏱️ Time & Space Complexities

Search: O(log n) guaranteed for both AVL and Red-Black
Insert: O(log n) for both, but AVL may require more rotations
Delete: O(log n) for both
Space: O(n) for both (plus O(log n) recursion stack)

🌲 Other Balanced Trees

Splay Trees: Self-adjusting, recently accessed nodes move to root
B-Trees: Multi-way trees used in databases (each node has many children)
Treap: Tree + Heap — randomized balancing
Scapegoat Trees: Lazy rebuilding when subtree becomes too unbalanced
Weight-Balanced Trees: Maintain size balance rather than height balance

🌍 Real-World Applications

Java TreeMap/TreeSet: Red-Black tree implementation
C++ std::map / std::set: Typically Red-Black trees
Linux Kernel: Completely Fair Scheduler (CFS) uses Red-Black trees
Database Indexes: B-Trees (generalization)
File Systems: ext4 uses B-trees for directory indexing
Memory Management: Some allocators use balanced trees

📊 Visualization & Examples

🎯 Insert 1,2,3,4,5 into AVL vs Red-Black

AVL: More rotations, stricter balance → tree is "flatter"
Red-Black: Fewer rotations, but tree height may be larger

AVL after 1,2,3,4,5:
        2
       / \
      1   4
         / \
        3   5

Red-Black after 1,2,3,4,5:
        2 (B)
       / \
      1(B) 4(R)
         / \
        3(B) 5(B)

💪 Classic Problems & Algorithms

Verify AVL: Check if tree satisfies AVL balance property
Verify Red-Black: Check all 5 properties
Count Rotations: Track rotations during insert/delete
Tree Height: Compute height of balanced tree
Range Queries: Efficiently query values in range

📝 Interview Patterns

🎯 Key Interview Questions

When would you choose AVL over Red-Black? (Read-heavy → AVL)
What's the maximum height of a Red-Black tree with n nodes? (≈ 2 log n)
Explain how rotations maintain balance
What are the Red-Black properties? (The 5 rules)
What's the difference between AVL and Red-Black? (Strictness vs speed)

# Quick Red-Black property checker
def is_valid_red_black(root):
    # Returns (is_valid, black_height, has_red_parent)
    def check(node, parent_is_red):
        if not node:
            return (True, 1, False)
        
        # Property 4: No consecutive reds
        if parent_is_red and node.color == RBNode.RED:
            return (False, 0, False)
        
        left_valid, left_bh, _ = check(node.left, node.color == RBNode.RED)
        right_valid, right_bh, _ = check(node.right, node.color == RBNode.RED)
        
        # Property 5: Equal black heights
        if left_bh != right_bh:
            return (False, 0, False)
        
        current_bh = left_bh + (1 if node.color == RBNode.BLACK else 0)
        return (left_valid and right_valid, current_bh, node.color == RBNode.RED)
    
    valid, bh, _ = check(root, False)
    # Property 2: Root must be black
    return valid and (not root or root.color == RBNode.BLACK)