Red-Black Tree

A red-black tree is a self-balancing binary search tree that maintains balance using node coloring rules instead of strict height constraints. Compared to AVL trees, red-black trees allow slightly looser balance, resulting in fewer rotations and better performance for workloads with frequent insertions and deletions.

Because of this trade-off, red-black trees are widely used in real-world systems (e.g., TreeMap in Rust, std::map in C++).

Core Properties

Every node in a red-black tree is colored red or black, and the tree must satisfy these rules:

1. Every node is either red or black
2. The root is always black
3. All leaf (null) nodes are black
4. Red nodes cannot have red children (no two reds in a row)
5. Every path from a node to its descendant leaves contains the same number of black nodes

These rules ensure the tree remains approximately balanced.

Why Red-Black Trees Work

Unlike AVL trees, which strictly enforce balance using height differences, red-black trees:

• Allow temporary imbalance
• Fix violations using recoloring first
• Use rotations only when necessary

This results in:

• Faster insertions and deletions
• Slightly slower lookups than AVL trees
• Guaranteed O(log n) performance

Red-Black vs AVL (High-Level)

Insertion Overview

Red-black tree insertion follows these steps:

1. Insert the node like a BST

2. Color the new node red

3. Fix any rule violations using:

   • Recoloring
   • Rotations (left or right)

4. Ensure the root is black

Violations occur only when a red node has a red parent.

Fix-Up Cases After Insertion

Let:

• N = newly inserted node
• P = parent
• U = uncle
• G = grandparent

Case 1 - Uncle is Red

• Recolor P and U to black
• Recolor G to red
• Continue fixing from G

Case 2 - Uncle is Black & Node is Inner Child

• Rotate at P to convert into Case 3

Case 3 - Uncle is Black & Node is Outer Child

• Rotate at G
• Recolor P and G

Rust Implementation (Insertion Only)

This is a simplified educational implementation focusing on structure and insertion logic. Full red-black trees are verbose; production code typically relies on libraries.

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

#[derive(Debug)]
pub struct Node<T> {
    value: T,
    color: Color,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

impl<T: Ord> Node<T> {
    pub fn new(value: T) -> Self {
        Node {
            value,
            color: Color::Red,
            left: None,
            right: None,
        }
    }

    fn is_red(node: &Option<Box<Node<T>>>) -> bool {
        matches!(node.as_ref().map(|n| &n.color), Some(Color::Red))
    }

    fn rotate_left(mut h: Box<Node<T>>) -> Box<Node<T>> {
        let mut x = h.right.take().unwrap();
        h.right = x.left.take();
        x.left = Some(h);
        x.color = x.left.as_ref().unwrap().color.clone();
        x.left.as_mut().unwrap().color = Color::Red;
        x
    }

    fn rotate_right(mut h: Box<Node<T>>) -> Box<Node<T>> {
        let mut x = h.left.take().unwrap();
        h.left = x.right.take();
        x.right = Some(h);
        x.color = x.right.as_ref().unwrap().color.clone();
        x.right.as_mut().unwrap().color = Color::Red;
        x
    }

    fn flip_colors(h: &mut Box<Node<T>>) {
        h.color = Color::Red;
        if let Some(ref mut left) = h.left {
            left.color = Color::Black;
        }
        if let Some(ref mut right) = h.right {
            right.color = Color::Black;
        }
    }

    pub fn insert(mut h: Option<Box<Node<T>>>, value: T) -> Option<Box<Node<T>>> {
        match h {
            None => return Some(Box::new(Node::new(value))),
            Some(ref mut node) => {
                if value < node.value {
                    node.left = Self::insert(node.left.take(), value);
                } else if value > node.value {
                    node.right = Self::insert(node.right.take(), value);
                }
            }
        }

        let mut node = h.unwrap();

        // Fix right-leaning reds
        if Self::is_red(&node.right) && !Self::is_red(&node.left) {
            node = Self::rotate_left(node);
        }

        // Fix two consecutive left reds
        if Self::is_red(&node.left) && Self::is_red(&node.left.as_ref().unwrap().left) {
            node = Self::rotate_right(node);
        }

        // Split 4-nodes
        if Self::is_red(&node.left) && Self::is_red(&node.right) {
            Self::flip_colors(&mut node);
        }

        Some(node)
    }
}

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

    fn is_bst<T: Ord>(node: &Option<Box<Node<T>>>, min: Option<&T>, max: Option<&T>) -> bool {
        if let Some(n) = node {
            if min.map_or(false, |m| n.value <= *m) {
                return false;
            }
            if max.map_or(false, |m| n.value >= *m) {
                return false;
            }
            is_bst(&n.left, min, Some(&n.value))
                && is_bst(&n.right, Some(&n.value), max)
        } else {
            true
        }
    }

    fn no_red_red<T>(node: &Option<Box<Node<T>>>) -> bool {
        if let Some(n) = node {
            if n.color == Color::Red {
                if matches!(n.left.as_ref().map(|l| &l.color), Some(Color::Red))
                    || matches!(n.right.as_ref().map(|r| &r.color), Some(Color::Red))
                {
                    return false;
                }
            }
            no_red_red(&n.left) && no_red_red(&n.right)
        } else {
            true
        }
    }

    #[test]
    fn inserts_preserve_bst_property() {
        let mut root = None;
        for v in [20, 10, 30, 5, 15, 25, 35] {
            root = Node::insert(root, v);
            if let Some(ref mut r) = root {
                r.color = Color::Black;
            }
        }

        assert!(is_bst(&root, None, None));
    }

    #[test]
    fn no_consecutive_red_links() {
        let mut root = None;
        for v in [10, 20, 30, 15, 25, 5] {
            root = Node::insert(root, v);
            if let Some(ref mut r) = root {
                r.color = Color::Black;
            }
        }

        assert!(no_red_red(&root));
    }

    #[test]
    fn root_is_black() {
        let mut root = Node::insert(None, 42);
        if let Some(ref mut r) = root {
            r.color = Color::Black;
        }

        assert_eq!(root.unwrap().color, Color::Black);
    }
}

This implementation follows the Left-Leaning Red-Black Tree (LLRB) model, which simplifies balancing logic while preserving red-black properties.

Example Usage

fn main() {
    let mut root: Option<Box<Node<i32>>> = None;

    for v in [10, 20, 30, 15, 25, 5] {
        root = Node::insert(root, v);
        // root must always be black
        if let Some(ref mut r) = root {
            r.color = Color::Black;
        }
    }

    println!("{:#?}", root);
}

Time and Space Complexity

Red-black trees guarantee logarithmic height.

Time Complexity

Space Complexity

When to Use Red-Black Trees

Red-black trees are ideal when:

• Insertions and deletions are frequent
• Predictable performance is required
• Slightly slower reads are acceptable

They are often preferred over AVL trees in system-level libraries.

Playground Links

Rust - Red-Black Tree