Advanced Trees | LIZIU DSA

Why Should You Care About Advanced Trees?

🗄️

Database Indexes

MySQL, PostgreSQL, and almost every database uses B-Trees for indexes. That's why your queries run in milliseconds instead of minutes!

🎮

Game Engines

Unity and Unreal Engine use balanced trees for scene graphs, making it possible to render millions of objects smoothly.

📱

Operating Systems

Linux kernel uses Red-Black trees for process scheduling, ensuring your apps get fair CPU time!

🔍

Search Engines

Google uses tree structures to organize billions of web pages, making search results instant!

💾

File Systems

Your computer's file system (NTFS, ext4) uses B-Trees to organize millions of files efficiently!

📊

Data Analytics

Apache Spark and data warehouses use tree structures for range queries and aggregations on massive datasets!

Level 1: The Basics (Start Here!)

Level 1

What are Self-Balancing Trees? Think of it as a Smart Bookshelf!

Imagine a bookshelf that automatically reorganizes itself so you can always find any book quickly. That's exactly what self-balancing trees do with data!

The Problem with Unbalanced Trees

AVL Trees: The Perfectionists

AVL trees are like perfectionists - they keep the tree height-balanced at all times. The heights of left and right subtrees differ by at most 1!

Your First AVL Tree Implementation 🌲

# AVL Tree Node - Each node knows its height!
class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1  # New nodes start at height 1

# The magic happens with rotations!
def right_rotate(y):
    """
    Imagine picking up the left child and 
    rotating the tree clockwise!
    """
    x = y.left
    T2 = x.right
    
    # Perform the 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  # x is the new root!
                                

Try It Yourself: AVL Tree Builder

Insert numbers and watch the tree balance itself with rotations!

💡 Tip: AVL trees maintain balance by ensuring height difference ≤ 1 between subtrees!

Red-Black Trees: The Flexible Friends

Red-Black trees are more relaxed than AVL trees. They use colors (red and black) to maintain balance, like traffic lights controlling the flow!

Red-Black Tree Rules

Rules to Follow

Root is always BLACK
No two RED nodes in a row
All paths have same number of BLACK nodes
NULL nodes are BLACK

Why These Rules?

These simple rules guarantee the tree height is at most 2×log(n), ensuring fast operations!

Think of it as traffic rules that prevent congestion!

Try It Yourself: Red-Black Tree Simulator

Insert numbers and watch the colors change to maintain balance!

💡 Watch: Red nodes represent new insertions, Black nodes maintain balance. No two reds in a row!

Common Mistake: Forgetting to Update Heights

# ❌ WRONG - Forgot to update heights after rotation!
def bad_rotate(y):
    x = y.left
    x.right = y
    y.left = x.right
    return x  # Heights are now wrong!
                            

The Right Way: Always Update Heights

# ✅ CORRECT - Update heights bottom-up
def good_rotate(y):
    x = y.left
    x.right = y
    y.left = x.right
    
    # Update heights (y first, then x)
    update_height(y)
    update_height(x)
    
    return x
                            

Level 2: Common Tree Patterns

Level 2

Pattern 1: Tree Rotations

Rotations are the secret sauce of self-balancing trees! Think of them as gymnastics moves that keep the tree balanced.

The Four Types of Rotations

1

Left Rotation: When right side is too heavy

2

Right Rotation: When left side is too heavy

3

Left-Right Rotation: Zigzag on the left

4

Right-Left Rotation: Zigzag on the right

Pattern 2: B-Trees for Databases

B-Trees are like filing cabinets - each drawer (node) can hold multiple items, perfect for disk storage!

B-Tree Node Structure

class BTreeNode:
    def __init__(self, leaf=True):
        # A B-Tree node can have multiple keys!
        self.keys = []  # Sorted list of keys
        self.children = []  # Child pointers
        self.leaf = leaf  # Is this a leaf node?
        
    def split_child(self, i):
        """
        When a child is full, split it into two!
        Like dividing a full drawer into two drawers.
        """
        # Split logic here
        pass

# B-Trees are perfect for databases because:
# 1. Fewer disk reads (each node = one disk block)
# 2. Better cache performance
# 3. Sequential access is fast
                                

Pattern 3: Choosing the Right Tree

Use AVL Trees When:

Lookups are more frequent than insertions
You need guaranteed O(log n) worst case
Memory is not a concern
Example: Dictionary applications

Use Red-Black Trees When:

Insertions and deletions are frequent
You need good average performance
Used in: C++ STL, Java TreeMap
Example: Process schedulers

Use B-Trees When:

Data is stored on disk
You need to minimize disk I/O
Sequential access is important
Example: Database indexes

Level 3: Practice Problems

Practice Time!

Problem Set: From Easy to Hard

E

Easy: Check if Tree is Balanced

Given a binary tree, check if it's height-balanced (AVL property).

💡 Hint

Check height difference at each node. Use recursion!

M

Medium: Implement Tree Rotation

Implement left and right rotations for an AVL tree.

💡 Hint

Remember to update heights after rotation!

H

Hard: B-Tree Insertion

Implement insertion in a B-Tree with node splitting.

💡 Hint

Split full nodes proactively while traversing down!

Challenge: Balance Factor Calculator

Calculate the balance factor of each node in a tree.

def balance_factor(node):
    """
    Balance Factor = Height(Left) - Height(Right)
    Returns: -1, 0, or 1 for balanced
             < -1 or > 1 for unbalanced
    """
    # Your code here!
    pass
                            

Show Solution

def balance_factor(node):
    if not node:
        return 0
    
    left_height = get_height(node.left)
    right_height = get_height(node.right)
    
    return left_height - right_height

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

Level 4: Advanced Concepts

Level 4

Advanced AVL Operations

Let's dive deep into the four rotation cases that keep AVL trees balanced!

The Four Rotation Cases

Red-Black Tree Fixup

Red-Black Tree Color Fixing

def fix_insert(self, node):
    """
    Fix Red-Black tree after insertion
    Like traffic control - no two reds in a row!
    """
    while node.parent and node.parent.color == "RED":
        # Parent is red - we have a violation!
        
        if node.parent == node.parent.parent.left:
            uncle = node.parent.parent.right
            
            if uncle and uncle.color == "RED":
                # Case 1: Uncle is red - just recolor!
                node.parent.color = "BLACK"
                uncle.color = "BLACK"
                node.parent.parent.color = "RED"
                node = node.parent.parent
            else:
                # Case 2 & 3: Uncle is black - rotate!
                if node == node.parent.right:
                    # Left-Right case
                    node = node.parent
                    self.left_rotate(node)
                
                # Left-Left case
                node.parent.color = "BLACK"
                node.parent.parent.color = "RED"
                self.right_rotate(node.parent.parent)
    
    # Root must always be black!
    self.root.color = "BLACK"
                                

B-Tree Split Operation

When a B-Tree node gets full, we split it like dividing a full drawer into two!

B-Tree Properties

Order m: Each node has at most m children
Keys: Each node has at most m-1 keys
Half-full: Each node (except root) has at least ⌈m/2⌉ children
Sorted: Keys in each node are sorted
All leaves: Are at the same level

Quick Reference Guide

Tree Comparison Chart

Tree Type	Insert	Delete	Search	Best For
AVL Tree	O(log n)	O(log n)	O(log n)	Frequent lookups
Red-Black	O(log n)	O(log n)	O(log n)	Balanced ops
B-Tree	O(log n)	O(log n)	O(log n)	Disk storage
Binary Heap	O(log n)	O(log n)	O(n)	Priority queues

AVL Tree Operations

✅ Height-balanced: |BF| ≤ 1
🔄 Rotations: 4 types (LL, RR, LR, RL)
📊 Height: 1.44 × log(n)
⚡ Strict: More rotations

Red-Black Operations

🔴 Color-based: Red/Black nodes
📏 Black-height: Same for all paths
📊 Height: 2 × log(n)
⚡ Flexible: Fewer rotations

Common Tree Patterns

🌳 Balanced BST

Use for in-memory sorted data

🗄️ B-Tree/B+Tree

Database indexes

📊 Segment Tree

Range queries

🎯 Trie

String operations

🏔️ Binary Heap

Priority queue

🌲 Splay Tree

Cache-friendly

Common Pitfalls to Avoid

Forgetting to update heights: Always update after rotations
Wrong rotation direction: Draw it out first!
Not handling NULL nodes: Check before accessing
Incorrect color rules: Root is always black
B-Tree overflow: Split before insertion, not after