🔴⚫ Red-Black Tree

Overview

Implements a persistent red-black tree — a self-balancing BST that maintains balance invariants through node coloring. Guarantees O(log n) for insert, delete, and lookup. All operations return new trees (functional/immutable).

Concepts Demonstrated

• Algebraic data types — tree with color, left, key, value, right
• Pattern matching — the elegant four-case balance function
• Invariant maintenance — red-black properties preserved on mutation
• Persistent data structures — path copying for immutability
• Polymorphic comparison — generic key types

Red-Black Invariants

1. Every node is red or black
2. The root is always black
3. No red node has a red child
4. Every path from root to leaf has the same number of black nodes

These invariants guarantee the tree height is at most 2·log₂(n+1), ensuring logarithmic operations.

The Balance Function

(* Okasaki's elegant four-case balance *)
let balance = function
  | Black, Node(Red, Node(Red,a,x,b), y, c), z, d
  | Black, Node(Red, a, x, Node(Red,b,y,c)), z, d
  | Black, a, x, Node(Red, Node(Red,b,y,c), z, d)
  | Black, a, x, Node(Red, b, y, Node(Red,c,z,d))
    → Node(Red, Node(Black,a,x,b), y, Node(Black,c,z,d))
  | color, left, key, right
    → Node(color, left, key, right)

This single function handles all four rotation cases with pattern matching — one of the most elegant examples of algebraic data types in action.

Key Functions