Red-Black Tree - Delete

Deletion in a red-black tree is more complex than insertion because removing a node can violate the tree’s black-height and coloring rules. To fix these violations, the algorithm uses a series of recoloring steps and rotations.

Unlike AVL trees, red-black trees prioritize fewer rotations, even if the tree becomes slightly less balanced.

Key Idea

When deleting a node from a red-black tree:

• If a red node is removed → no rules are broken
• If a black node is removed → the tree may lose a black node along one path

To track this imbalance, deletion introduces the idea of a “double black” node.

What Is a Double Black?

A double black represents an extra black height on a node or null leaf after deletion.

This is not a real color, but a conceptual state used during rebalancing.

The goal of RB deletion is to eliminate the double black while restoring all red-black properties.

High-Level Deletion Steps

1. Perform BST deletion
2. If the deleted node was red → done
3. If the deleted node was black → fix violations using rebalancing cases
4. Ensure the root is black

Deletion Scenarios (BST Step)

Case 1: Deleting a Red Leaf

Red leaf → delete directly

✔ No fix needed

Case 2: Deleting a Node with One Child

• Replace node with its child
• If the child is red → recolor it black ✔ No further fix needed

Case 3: Deleting a Black Leaf

⚠ Creates a double black situation ➡ Requires rebalancing

This is where most complexity lies.

Fixing the Double Black: Rebalancing Cases

Let:

• DB = double black node
• S = sibling
• P = parent

Case 1: Sibling Is Red

Condition

• S is red

Action

• Recolor S → black
• Recolor P → red
• Rotate around P
• Convert to another case

      P(B)              S(B)
     /   \     →       /   \
   DB     S(R)       P(R)   X

This case reduces the problem to one where the sibling is black.

Case 2: Sibling Is Black & Both Sibling’s Children Are Black

Condition

• S is black
• Both children of S are black (or null)

Action

• Recolor S → red
• Move double black up to parent

      P(?)             P(DB)
     /   \     →      /   \
   DB     S(B)       N     S(R)

If P was red, recoloring it black resolves the issue.

Case 3: Sibling Is Black & One Inner Child Is Red

Condition

• S is black
• Inner child of S is red
• Outer child is black

Action

• Rotate at S
• Swap colors
• Convert to Case 4

      P               P
     / \     →       / \
   DB   S(B)       DB   X(B)
        /
      R

Case 4: Sibling Is Black & Outer Child Is Red

Condition

• S is black
• Outer child of S is red

Action

• Rotate at P

• Recolor:

  • S takes P’s color
  • P → black
  • Outer child → black

• Remove double black

      P(?)              S(?)
     /   \     →       /   \
   DB     S(B)        P(B)   R(B)
            \
             R

✔ Tree is fully balanced again.

Rust Implementation (Deletion Only)

#[derive(Debug, Clone, PartialEq)]
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 + Clone> 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 = match h.color {
            Color::Red => Color::Black,
            Color::Black => Color::Red,
        };

        if let Some(ref mut l) = h.left {
            l.color = match l.color {
                Color::Red => Color::Black,
                Color::Black => Color::Red,
            };
        }

        if let Some(ref mut r) = h.right {
            r.color = match r.color {
                Color::Red => Color::Black,
                Color::Black => Color::Red,
            };
        }
    }

    fn move_red_left(mut h: Box<Node<T>>) -> Box<Node<T>> {
        Self::flip_colors(&mut h);
        if Self::is_red(&h.right.as_ref().unwrap().left) {
            h.right = Some(Self::rotate_right(h.right.take().unwrap()));
            h = Self::rotate_left(h);
            Self::flip_colors(&mut h);
        }
        h
    }

    fn move_red_right(mut h: Box<Node<T>>) -> Box<Node<T>> {
        Self::flip_colors(&mut h);
        if Self::is_red(&h.left.as_ref().unwrap().left) {
            h = Self::rotate_right(h);
            Self::flip_colors(&mut h);
        }
        h
    }

    fn fix_up(mut h: Box<Node<T>>) -> Box<Node<T>> {
        if Self::is_red(&h.right) {
            h = Self::rotate_left(h);
        }
        if Self::is_red(&h.left) && Self::is_red(&h.left.as_ref().unwrap().left) {
            h = Self::rotate_right(h);
        }
        if Self::is_red(&h.left) && Self::is_red(&h.right) {
            Self::flip_colors(&mut h);
        }
        h
    }

    fn min(node: &Box<Node<T>>) -> &T {
        match node.left {
            Some(ref left) => Self::min(left),
            None => &node.value,
        }
    }

    fn delete_min(mut h: Box<Node<T>>) -> Option<Box<Node<T>>> {
        if h.left.is_none() {
            return None;
        }

        if !Self::is_red(&h.left) && !Self::is_red(&h.left.as_ref().unwrap().left) {
            h = Self::move_red_left(h);
        }

        h.left = h.left.take().and_then(|l| Self::delete_min(l));
        Some(Self::fix_up(h))
    }

    pub fn delete(mut h: Box<Node<T>>, value: &T) -> Option<Box<Node<T>>> {
        if value < &h.value {
            if !Self::is_red(&h.left) && !Self::is_red(&h.left.as_ref().unwrap().left) {
                h = Self::move_red_left(h);
            }
            h.left = h.left.take().and_then(|l| Self::delete(l, value));
        } else {
            if Self::is_red(&h.left) {
                h = Self::rotate_right(h);
            }

            if value == &h.value && h.right.is_none() {
                return None;
            }

            if !Self::is_red(&h.right) && !Self::is_red(&h.right.as_ref().unwrap().left) {
                h = Self::move_red_right(h);
            }

            if value == &h.value {
                let min = Self::min(h.right.as_ref().unwrap()).clone();
                h.value = min;
                h.right = h.right.take().and_then(Self::delete_min);
            } else {
                h.right = h.right.take().and_then(|r| Self::delete(r, value));
            }
        }

        Some(Self::fix_up(h))
    }
}

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

    #[test]
    fn it_deletes_value() {
        let mut root = Box::new(Node::new(20));
        root = Node::insert(Some(root), 10).unwrap();
        root = Node::insert(Some(root), 30).unwrap();
        root = Node::insert(Some(root), 5).unwrap();

        let root = Node::delete(root, &10).unwrap();
        assert!(root.value == 20);
    }
}

Example Usage

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

    // Insert values
    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!("Before deletion:\n{:#?}", root);

    // Delete a value
    if let Some(r) = root {
        root = Node::delete(r, &15);
    }

    // Ensure root remains black after deletion
    if let Some(ref mut r) = root {
        r.color = Color::Black;
    }

    println!("After deletion:\n{:#?}", root);
}

Why RB Deletion Is Harder Than AVL Deletion

Red-black trees trade simplicity for performance.

Time and Space Complexity

Despite the complexity, red-black deletion remains efficient.

Time Complexity

Space Complexity

Practical Note

Because red-black deletion is extremely intricate:

• Most production code uses well-tested libraries
• Rust’s BTreeMap and BTreeSet use B-trees, not RB trees
• RB trees are still critical for understanding balanced tree theory

Summary

• Red-black deletion revolves around fixing double black
• Recoloring is preferred over rotation
• Rotations are used only when necessary
• Guarantees logarithmic performance

Playground Links

Rust - Red-Black Tree - Delete