ExamplesBy LevelBy TopicLearning Paths
1083 Advanced
← 10821084 →

Red-Black Tree

Trees

Tutorial Video

Text description (accessibility)

This video demonstrates the "Red-Black Tree" functional Rust example. Difficulty level: Advanced. Key concepts covered: Trees. Implement a purely functional red-black tree supporting insert and membership lookup, using Okasaki's elegant balancing technique where all four rotation cases collapse into a single rewrite rule. Key difference from OCaml: 1. **Pattern matching depth:** OCaml matches 3 levels deep across 4 cases in one arm; Rust requires sequential peek

Tutorial

The Problem

Implement a purely functional red-black tree supporting insert and membership lookup, using Okasaki's elegant balancing technique where all four rotation cases collapse into a single rewrite rule.

🎯 Learning Outcomes

  • • How Rust enums model algebraic data types (sum types with data) just like OCaml variants
  • • Ownership-based tree restructuring via path copying — Rust's move semantics naturally implement persistent data structures
  • • Pattern matching on nested owned data requires a peek-then-destructure strategy, unlike OCaml's direct nested pattern matching
  • • The Box<T> heap allocation pattern for recursive data structures

    • 🦀 The Rust Way

    Rust uses enum RBTree<T> with Box for recursive children. The balance function cannot match four nested patterns in one arm like OCaml, so it peeks at the structure via references (to determine which case applies) then destructures by moving owned values out. The tree is generic over T: Ord and uses Ordering for comparisons. Insert takes self by value and returns a new tree — natural path-copying via Rust's move semantics.

    Code Example

    fn balance<T>(color: Color, left: RBTree<T>, value: T, right: RBTree<T>) -> RBTree<T> {
    if color != Black {
        return RBTree::node(color, left, value, right);
    }
    // Case 1: left-left — peek at shape, then destructure by move
    if left.is_red_node() {
        if let Node { left: ref ll, .. } = left {
            if ll.is_red_node() {
                if let Node { left: ll_box, value: y, right: c, .. } = left {
                    if let Node { left: a, value: x, right: b, .. } = *ll_box {
                        return RBTree::node(Red,
                            RBTree::node(Black, *a, x, *b), y,
                            RBTree::node(Black, *c, value, right));
                    }
                }
            }
        }
    }
    // ... Cases 2, 3, 4 follow the same peek-then-move pattern
    RBTree::node(Black, left, value, right)
}

    Key Differences

  • Pattern matching depth: OCaml matches 3 levels deep across 4 cases in one arm; Rust requires sequential peek-then-destructure for each case
  • Memory management: OCaml's GC handles sharing automatically; Rust uses Box<T> with explicit heap allocation and move semantics for path copying
  • Polymorphism: OCaml uses 'a with structural equality; Rust uses T: Ord trait bound for ordered comparisons
  • Conciseness: The OCaml balance is ~6 lines; Rust's is ~80 lines due to explicit destructuring — but both encode the same four-case logic

    • OCaml Approach

    OCaml defines the tree as a simple algebraic type 'a rbtree = E | T of color * 'a rbtree * 'a * 'a rbtree. The balance function uses a single match with four or-patterns to catch all red-red violations and rewrite them into one canonical balanced form. This is the essence of Okasaki's insight — the code is remarkably concise because OCaml allows deep nested pattern matching across multiple cases in one arm.

    Full Source

    #![allow(clippy::all)]
/// Red-Black Tree — Okasaki's purely functional balanced BST
///
/// A red-black tree maintains balance through color invariants:
/// 1. No red node has a red child
/// 2. Every path from root to leaf has the same number of black nodes
///
/// Okasaki's insight: all four rotation cases collapse into a single balance function
/// that pattern-matches on the four "red-red violation" shapes and rewrites them
/// into one canonical balanced form.
use std::cmp::Ordering;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Color {
    Red,
    Black,
}

/// A purely functional red-black tree.
/// Uses `Box` for heap-allocated children — no `Rc` needed because the tree is rebuilt
/// on each insert (persistent data structure via path copying).
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum RBTree<T> {
    Empty,
    Node {
        color: Color,
        left: Box<RBTree<T>>,
        value: T,
        right: Box<RBTree<T>>,
    },
}

use Color::{Black, Red};
use RBTree::{Empty, Node};

impl<T> RBTree<T> {
    fn node(color: Color, left: RBTree<T>, value: T, right: RBTree<T>) -> Self {
        Node {
            color,
            left: Box::new(left),
            value,
            right: Box::new(right),
        }
    }

    fn is_red_node(&self) -> bool {
        matches!(self, Node { color: Red, .. })
    }
}

impl<T: Ord> RBTree<T> {
    /// Creates an empty red-black tree.
    pub fn new() -> Self {
        Empty
    }

    /// Checks membership — O(log n).
    ///
    /// Direct translation of OCaml's `mem`:
    /// ```ocaml
    /// let rec mem x = function
    ///   | E -> false
    ///   | T (_, a, y, b) -> x = y || (if x < y then mem x a else mem x b)
    /// ```
    pub fn mem(&self, x: &T) -> bool {
        match self {
            Empty => false,
            Node {
                left, value, right, ..
            } => match x.cmp(value) {
                Ordering::Equal => true,
                Ordering::Less => left.mem(x),
                Ordering::Greater => right.mem(x),
            },
        }
    }

    /// Inserts a value, returning a new tree (functional/persistent).
    ///
    /// The inner `ins` builds a potentially unbalanced tree with a red-red violation,
    /// then `balance` fixes it. The root is always repainted black.
    pub fn insert(self, x: T) -> Self
    where
        T: Clone,
    {
        fn ins<T: Ord + Clone>(tree: RBTree<T>, x: &T) -> RBTree<T> {
            match tree {
                Empty => RBTree::node(Red, Empty, x.clone(), Empty),
                Node {
                    color,
                    left,
                    value,
                    right,
                } => match x.cmp(&value) {
                    Ordering::Less => balance(color, ins(*left, x), value, *right),
                    Ordering::Greater => balance(color, *left, value, ins(*right, x)),
                    Ordering::Equal => RBTree::node(color, *left, value, *right),
                },
            }
        }

        // Root is always black
        match ins(self, &x) {
            Node {
                left, value, right, ..
            } => Node {
                color: Black,
                left,
                value,
                right,
            },
            Empty => Empty,
        }
    }

    /// In-order traversal producing a sorted vector — recursive (OCaml style).
    ///
    /// Mirrors OCaml's `to_list`:
    /// ```ocaml
    /// let rec to_list = function
    ///   | E -> [] | T (_, a, v, b) -> to_list a @ [v] @ to_list b
    /// ```
    pub fn to_sorted_vec(&self) -> Vec<&T> {
        match self {
            Empty => vec![],
            Node {
                left, value, right, ..
            } => {
                let mut result = left.to_sorted_vec();
                result.push(value);
                result.extend(right.to_sorted_vec());
                result
            }
        }
    }

    /// In-order traversal — iterative with explicit stack (idiomatic Rust).
    pub fn to_sorted_vec_iter(&self) -> Vec<&T> {
        let mut stack = vec![];
        let mut result = vec![];
        let mut current = self;

        loop {
            match current {
                Node {
                    left, value, right, ..
                } => {
                    stack.push((value, right.as_ref()));
                    current = left.as_ref();
                }
                Empty => match stack.pop() {
                    Some((value, right)) => {
                        result.push(value);
                        current = right;
                    }
                    None => break,
                },
            }
        }

        result
    }

    /// Returns the number of elements in the tree.
    pub fn len(&self) -> usize {
        match self {
            Empty => 0,
            Node { left, right, .. } => 1 + left.len() + right.len(),
        }
    }

    /// Returns true if the tree is empty.
    pub fn is_empty(&self) -> bool {
        matches!(self, Empty)
    }

    /// Returns the height (longest path from root to leaf).
    pub fn height(&self) -> usize {
        match self {
            Empty => 0,
            Node { left, right, .. } => 1 + left.height().max(right.height()),
        }
    }

    /// Validates red-black tree invariants:
    /// 1. No red node has a red child
    /// 2. Every root-to-leaf path has the same black depth
    ///
    /// Returns `Some(black_depth)` if valid, `None` if violated.
    pub fn validate(&self) -> Option<usize> {
        match self {
            Empty => Some(1), // leaves count as black
            Node {
                color, left, right, ..
            } => {
                if *color == Red
                    && (matches!(left.as_ref(), Node { color: Red, .. })
                        || matches!(right.as_ref(), Node { color: Red, .. }))
                {
                    return None;
                }

                let left_depth = left.validate()?;
                let right_depth = right.validate()?;

                if left_depth != right_depth {
                    return None;
                }

                Some(if *color == Black {
                    left_depth + 1
                } else {
                    left_depth
                })
            }
        }
    }
}

impl<T: Ord> Default for RBTree<T> {
    fn default() -> Self {
        Self::new()
    }
}

/// Okasaki's balance function — the heart of the algorithm.
///
/// Pattern-matches on four cases where a black node has a red child
/// with a red grandchild (red-red violation), and rewrites all four
/// into one canonical balanced form:
///
/// ```text
///        y(R)
///       /    \
///     x(B)   z(B)
///    / \     / \
///   a   b   c   d
/// ```
///
/// This is a direct translation of the OCaml:
/// ```ocaml
/// let balance = function
///   | Black, T(Red, T(Red,a,x,b), y, c), z, d      (* left-left *)
///   | Black, T(Red, a, x, T(Red,b,y,c)), z, d      (* left-right *)
///   | Black, a, x, T(Red, T(Red,b,y,c), z, d)      (* right-left *)
///   | Black, a, x, T(Red, b, y, T(Red,c,z,d))      (* right-right *)
///     -> T(Red, T(Black,a,x,b), y, T(Black,c,z,d))
///   | color, a, x, b -> T(color, a, x, b)
/// ```
///
/// In Rust we can't match four nested patterns in one arm like OCaml, so we
/// peek at the structure via references first, then destructure by move.
fn balance<T>(color: Color, left: RBTree<T>, value: T, right: RBTree<T>) -> RBTree<T> {
    if color != Black {
        return RBTree::node(color, left, value, right);
    }

    // Peek at two levels of nesting to determine which (if any) case applies.
    // All four cases rewrite to: Red(Black(a,x,b), y, Black(c,z,d))

    // Case 1: left-left — Black(Red(Red(a,x,b),y,c), z, d)
    if left.is_red_node() {
        if let Node { left: ref ll, .. } = left {
            if ll.is_red_node() {
                // Destructure by move now that we've confirmed the shape
                if let Node {
                    left: ll_box,
                    value: y,
                    right: c,
                    ..
                } = left
                {
                    if let Node {
                        left: a,
                        value: x,
                        right: b,
                        ..
                    } = *ll_box
                    {
                        return RBTree::node(
                            Red,
                            RBTree::node(Black, *a, x, *b),
                            y,
                            RBTree::node(Black, *c, value, right),
                        );
                    }
                }
                unreachable!();
            }
        }
    }

    // Case 2: left-right — Black(Red(a,x,Red(b,y,c)), z, d)
    if left.is_red_node() {
        if let Node { right: ref lr, .. } = left {
            if lr.is_red_node() {
                if let Node {
                    left: a,
                    value: x,
                    right: lr_box,
                    ..
                } = left
                {
                    if let Node {
                        left: b,
                        value: y,
                        right: c,
                        ..
                    } = *lr_box
                    {
                        return RBTree::node(
                            Red,
                            RBTree::node(Black, *a, x, *b),
                            y,
                            RBTree::node(Black, *c, value, right),
                        );
                    }
                }
                unreachable!();
            }
        }
    }

    // Case 3: right-left — Black(a, x, Red(Red(b,y,c),z,d))
    if right.is_red_node() {
        if let Node { left: ref rl, .. } = right {
            if rl.is_red_node() {
                if let Node {
                    left: rl_box,
                    value: z,
                    right: d,
                    ..
                } = right
                {
                    if let Node {
                        left: b,
                        value: y,
                        right: c,
                        ..
                    } = *rl_box
                    {
                        return RBTree::node(
                            Red,
                            RBTree::node(Black, left, value, *b),
                            y,
                            RBTree::node(Black, *c, z, *d),
                        );
                    }
                }
                unreachable!();
            }
        }
    }

    // Case 4: right-right — Black(a, x, Red(b,y,Red(c,z,d)))
    if right.is_red_node() {
        if let Node { right: ref rr, .. } = right {
            if rr.is_red_node() {
                if let Node {
                    left: b,
                    value: y,
                    right: rr_box,
                    ..
                } = right
                {
                    if let Node {
                        left: c,
                        value: z,
                        right: d,
                        ..
                    } = *rr_box
                    {
                        return RBTree::node(
                            Red,
                            RBTree::node(Black, left, value, *b),
                            y,
                            RBTree::node(Black, *c, z, *d),
                        );
                    }
                }
                unreachable!();
            }
        }
    }

    // Default: no rebalancing needed
    RBTree::node(Black, left, value, right)
}

/// Convenience: build a tree from an iterator (functional fold).
pub fn from_iter<T: Ord + Clone>(iter: impl IntoIterator<Item = T>) -> RBTree<T> {
    iter.into_iter().fold(RBTree::new(), |t, x| t.insert(x))
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_empty_tree() {
        let tree: RBTree<i32> = RBTree::new();
        assert!(tree.is_empty());
        assert_eq!(tree.len(), 0);
        assert!(!tree.mem(&1));
        assert_eq!(tree.to_sorted_vec(), Vec::<&i32>::new());
    }

    #[test]
    fn test_single_insert() {
        let tree = RBTree::new().insert(42);
        assert!(!tree.is_empty());
        assert_eq!(tree.len(), 1);
        assert!(tree.mem(&42));
        assert!(!tree.mem(&0));
        assert_eq!(tree.to_sorted_vec(), vec![&42]);
        // Root must be black
        assert!(matches!(tree, Node { color: Black, .. }));
    }

    #[test]
    fn test_multiple_inserts_sorted_output() {
        // Same sequence as the OCaml example
        let tree = from_iter([5, 3, 7, 1, 4, 6, 8, 2, 9]);
        let sorted = tree.to_sorted_vec();
        assert_eq!(sorted, vec![&1, &2, &3, &4, &5, &6, &7, &8, &9]);
    }

    #[test]
    fn test_membership() {
        let tree = from_iter([5, 3, 7, 1, 4, 6, 8, 2, 9]);
        for x in 1..=9 {
            assert!(tree.mem(&x), "expected {x} to be in the tree");
        }
        assert!(!tree.mem(&0));
        assert!(!tree.mem(&10));
        assert!(!tree.mem(&100));
    }

    #[test]
    fn test_duplicate_insert() {
        let tree = from_iter([3, 1, 3, 2, 1, 3]);
        assert_eq!(tree.len(), 3);
        assert_eq!(tree.to_sorted_vec(), vec![&1, &2, &3]);
    }

    #[test]
    fn test_red_black_invariants() {
        let tree = from_iter([5, 3, 7, 1, 4, 6, 8, 2, 9]);
        assert!(matches!(tree, Node { color: Black, .. }));
        assert!(tree.validate().is_some(), "red-black invariants violated");
    }

    #[test]
    fn test_invariants_ascending_insert() {
        // Ascending order stresses right-rotation paths
        let tree = from_iter(1..=20);
        assert!(
            tree.validate().is_some(),
            "invariants violated on ascending insert"
        );
        assert_eq!(tree.len(), 20);
        let result = tree.to_sorted_vec();
        assert_eq!(result.len(), 20);
        assert_eq!(*result[0], 1);
        assert_eq!(*result[19], 20);
    }

    #[test]
    fn test_invariants_descending_insert() {
        // Descending order stresses left-rotation paths
        let tree = from_iter((1..=20).rev());
        assert!(
            tree.validate().is_some(),
            "invariants violated on descending insert"
        );
        assert_eq!(tree.len(), 20);
    }

    #[test]
    fn test_height_is_logarithmic() {
        let tree = from_iter(1..=100);
        let h = tree.height();
        // Red-black tree height <= 2 * log2(n+1)
        // For n=100: 2 * log2(101) ≈ 13.3, so height should be <= 14
        assert!(h <= 14, "height {h} exceeds 2*log2(101) bound");
    }

    #[test]
    fn test_iterator_traversal_matches_recursive() {
        let tree = from_iter([5, 3, 7, 1, 4, 6, 8, 2, 9]);
        assert_eq!(tree.to_sorted_vec(), tree.to_sorted_vec_iter());
    }

    #[test]
    fn test_string_keys() {
        let tree = from_iter(["delta", "alpha", "charlie", "bravo"].map(String::from));
        let sorted = tree.to_sorted_vec();
        assert_eq!(
            sorted.iter().map(|s| s.as_str()).collect::<Vec<_>>(),
            vec!["alpha", "bravo", "charlie", "delta"]
        );
    }
}
    ✓ Tests Rust test suite 
    #[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_empty_tree() {
        let tree: RBTree<i32> = RBTree::new();
        assert!(tree.is_empty());
        assert_eq!(tree.len(), 0);
        assert!(!tree.mem(&1));
        assert_eq!(tree.to_sorted_vec(), Vec::<&i32>::new());
    }

    #[test]
    fn test_single_insert() {
        let tree = RBTree::new().insert(42);
        assert!(!tree.is_empty());
        assert_eq!(tree.len(), 1);
        assert!(tree.mem(&42));
        assert!(!tree.mem(&0));
        assert_eq!(tree.to_sorted_vec(), vec![&42]);
        // Root must be black
        assert!(matches!(tree, Node { color: Black, .. }));
    }

    #[test]
    fn test_multiple_inserts_sorted_output() {
        // Same sequence as the OCaml example
        let tree = from_iter([5, 3, 7, 1, 4, 6, 8, 2, 9]);
        let sorted = tree.to_sorted_vec();
        assert_eq!(sorted, vec![&1, &2, &3, &4, &5, &6, &7, &8, &9]);
    }

    #[test]
    fn test_membership() {
        let tree = from_iter([5, 3, 7, 1, 4, 6, 8, 2, 9]);
        for x in 1..=9 {
            assert!(tree.mem(&x), "expected {x} to be in the tree");
        }
        assert!(!tree.mem(&0));
        assert!(!tree.mem(&10));
        assert!(!tree.mem(&100));
    }

    #[test]
    fn test_duplicate_insert() {
        let tree = from_iter([3, 1, 3, 2, 1, 3]);
        assert_eq!(tree.len(), 3);
        assert_eq!(tree.to_sorted_vec(), vec![&1, &2, &3]);
    }

    #[test]
    fn test_red_black_invariants() {
        let tree = from_iter([5, 3, 7, 1, 4, 6, 8, 2, 9]);
        assert!(matches!(tree, Node { color: Black, .. }));
        assert!(tree.validate().is_some(), "red-black invariants violated");
    }

    #[test]
    fn test_invariants_ascending_insert() {
        // Ascending order stresses right-rotation paths
        let tree = from_iter(1..=20);
        assert!(
            tree.validate().is_some(),
            "invariants violated on ascending insert"
        );
        assert_eq!(tree.len(), 20);
        let result = tree.to_sorted_vec();
        assert_eq!(result.len(), 20);
        assert_eq!(*result[0], 1);
        assert_eq!(*result[19], 20);
    }

    #[test]
    fn test_invariants_descending_insert() {
        // Descending order stresses left-rotation paths
        let tree = from_iter((1..=20).rev());
        assert!(
            tree.validate().is_some(),
            "invariants violated on descending insert"
        );
        assert_eq!(tree.len(), 20);
    }

    #[test]
    fn test_height_is_logarithmic() {
        let tree = from_iter(1..=100);
        let h = tree.height();
        // Red-black tree height <= 2 * log2(n+1)
        // For n=100: 2 * log2(101) ≈ 13.3, so height should be <= 14
        assert!(h <= 14, "height {h} exceeds 2*log2(101) bound");
    }

    #[test]
    fn test_iterator_traversal_matches_recursive() {
        let tree = from_iter([5, 3, 7, 1, 4, 6, 8, 2, 9]);
        assert_eq!(tree.to_sorted_vec(), tree.to_sorted_vec_iter());
    }

    #[test]
    fn test_string_keys() {
        let tree = from_iter(["delta", "alpha", "charlie", "bravo"].map(String::from));
        let sorted = tree.to_sorted_vec();
        assert_eq!(
            sorted.iter().map(|s| s.as_str()).collect::<Vec<_>>(),
            vec!["alpha", "bravo", "charlie", "delta"]
        );
    }
}

    Deep Comparison

    OCaml vs Rust: Red-Black Tree (Okasaki's Functional Balancing)

    Side-by-Side Code

    OCaml

    type color = Red | Black
type 'a rbtree = E | T of color * 'a rbtree * 'a * 'a rbtree

let balance = function
  | Black, T (Red, T (Red, a, x, b), y, c), z, d
  | Black, T (Red, a, x, T (Red, b, y, c)), z, d
  | Black, a, x, T (Red, T (Red, b, y, c), z, d)
  | Black, a, x, T (Red, b, y, T (Red, c, z, d)) ->
    T (Red, T (Black, a, x, b), y, T (Black, c, z, d))
  | color, a, x, b -> T (color, a, x, b)

let insert x t =
  let rec ins = function
    | E -> T (Red, E, x, E)
    | T (color, a, y, b) ->
      if x < y then balance (color, ins a, y, b)
      else if x > y then balance (color, a, y, ins b)
      else T (color, a, y, b)
  in
  match ins t with T (_, a, y, b) -> T (Black, a, y, b) | E -> E

    Rust (idiomatic — peek-then-destructure)

    fn balance<T>(color: Color, left: RBTree<T>, value: T, right: RBTree<T>) -> RBTree<T> {
    if color != Black {
        return RBTree::node(color, left, value, right);
    }
    // Case 1: left-left — peek at shape, then destructure by move
    if left.is_red_node() {
        if let Node { left: ref ll, .. } = left {
            if ll.is_red_node() {
                if let Node { left: ll_box, value: y, right: c, .. } = left {
                    if let Node { left: a, value: x, right: b, .. } = *ll_box {
                        return RBTree::node(Red,
                            RBTree::node(Black, *a, x, *b), y,
                            RBTree::node(Black, *c, value, right));
                    }
                }
            }
        }
    }
    // ... Cases 2, 3, 4 follow the same peek-then-move pattern
    RBTree::node(Black, left, value, right)
}

    Rust (insert — functional path copying)

    pub fn insert(self, x: T) -> Self where T: Clone {
    fn ins<T: Ord + Clone>(tree: RBTree<T>, x: &T) -> RBTree<T> {
        match tree {
            Empty => RBTree::node(Red, Empty, x.clone(), Empty),
            Node { color, left, value, right } => match x.cmp(&value) {
                Ordering::Less => balance(color, ins(*left, x), value, *right),
                Ordering::Greater => balance(color, *left, value, ins(*right, x)),
                Ordering::Equal => RBTree::node(color, *left, value, *right),
            },
        }
    }
    match ins(self, &x) {
        Node { left, value, right, .. } => Node { color: Black, left, value, right },
        Empty => Empty,
    }
}

    Type Signatures

    ConceptOCamlRust
    Color typetype color = Red \| Blackenum Color { Red, Black }
    Tree type'a rbtree = E \| T of color * 'a rbtree * 'a * 'a rbtreeenum RBTree<T> { Empty, Node { color, left: Box<RBTree<T>>, value: T, right: Box<RBTree<T>> } }
    Insertval insert : 'a -> 'a rbtree -> 'a rbtreefn insert(self, x: T) -> Self where T: Ord + Clone
    Membershipval mem : 'a -> 'a rbtree -> boolfn mem(&self, x: &T) -> bool
    Balanceval balance : color * 'a rbtree * 'a * 'a rbtree -> 'a rbtreefn balance(color, left, value, right) -> RBTree<T>

    Key Insights

  • Or-patterns vs sequential checks: OCaml's balance uses four or-patterns in a single match arm — arguably the most elegant expression of Okasaki's algorithm. Rust lacks this capability for nested owned destructuring, requiring sequential peek-then-move checks for each case.
  • Move semantics as path copying: Rust's ownership system naturally implements the functional "path copying" technique. When insert takes self by value and reconstructs the spine, moved subtrees are shared for free — no reference counting or GC needed.
  • Box for recursive types: OCaml's recursive types are heap-allocated automatically by the runtime. Rust requires explicit Box<T> to break the infinite-size recursion, making the indirection visible in the type signature.
  • Comparison traits: OCaml uses structural equality (=) and comparison (<, >) via polymorphic operators. Rust requires explicit T: Ord trait bounds, making the ordering requirement part of the type contract.
  • Clone for insert: OCaml's insert x t captures x by reference implicitly (GC keeps it alive). Rust's insert requires T: Clone because the inner ins function may need to clone x at each recursive call when creating new leaf nodes.

    • When to Use Each Style

    Use idiomatic Rust (peek-then-destructure) when: building production-quality balanced trees where you need compile-time ownership guarantees and zero-cost abstraction — the verbose balance function compiles to the same efficient code as hand-written rotations.

    Use OCaml/functional style when: prototyping tree algorithms or writing educational code where the elegance of pattern matching makes the algorithm's structure immediately visible — Okasaki's four-case balance is a canonical example of how pattern matching shines.

    Exercises

  • Implement contains for the red-black tree that searches for a value without modifying the tree structure.
  • Add an in_order method that returns all elements of the red-black tree as a sorted Vec<T> by performing an in-order traversal.
  • Implement delete for the red-black tree (the hardest operation) and verify that red-black invariants are maintained after each deletion using a property-based test.

    • Open Source Repos

    functional-rust

    View the source for this example on GitHub — OCaml and Rust side by side in the repo.

    Rust