Ins:

Del:

Preset:

Overview & Concept

A Red-Black Tree is a self-balancing Binary Search Tree where each node stores an extra color bit (RED or BLACK). By enforcing five structural invariants, the tree ensures no simple path from the root to any leaf is more than twice as long as any other path, strictly bounding worst-case operations to O(log n) while requiring fewer rotations during modifications than AVL trees.

How It Works

Color Invariant: Every node is either RED or BLACK. Root is unconditionally BLACK.

Sentinel Leaves: All leaf nodes (NIL) are considered BLACK.

No Consecutive Reds: If a node is RED, both of its children must be BLACK.

Equal Black-Height: Every path from a node to descendant leaves contains the exact same number of black nodes.

Insert Fixup: Inserts as RED node; resolves double-red conflicts via uncle recoloring (Case 1) or triangle/line rotations (Cases 2 & 3).

Delete Fixup: Resolves double-black deficiencies through sibling rotations and recolorings across 4 standard cases.

Step-by-Step Execution

1. Standard BST Insertion / DeletionLocate position and insert new node colored RED, or splice out node during deletion.

2. Invariant CheckCheck if insertion created two consecutive RED nodes, or if deletion removed a BLACK node.

3. Uncle / Sibling InspectionInspect uncle color (for insert) or sibling color and children (for delete).

4. Recoloring & RotationsApply appropriate recoloring and single/double rotations to restore all 5 invariants.

Asymptotic Complexity Analysis

Metric	Best Case	Average Case	Worst Case	Space Complexity
Complexity Bound	O(log n)	O(log n)	O(log n) bounded by 2 log₂(n + 1)	O(n)
Explanation	Optimal input arrangement minimizing operations.	Expected time for uniformly distributed randomized inputs.	Adversarial degenerate conditions requiring full traversal.	Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic

// Red-Black Tree (CLRS Invariants)
operation rbInsert(T, z):
  bstInsert(T, z); z.color = RED
  while z != T.root and z.parent.color == RED:
    if z.parent == z.parent.parent.left:
      y = z.parent.parent.right // uncle
      if y.color == RED:        // Case 1: Red uncle
        z.parent.color = BLACK; y.color = BLACK
        z.parent.parent.color = RED; z = z.parent.parent
      else:                     // Black uncle
        if z == z.parent.right: // Case 2: Triangle
          z = z.parent; leftRotate(T, z)
        // Case 3: Line
        z.parent.color = BLACK; z.parent.parent.color = RED
        rightRotate(T, z.parent.parent)
    else: /* mirror right side */
  T.root.color = BLACK

Algorithmic Invariants

1. Every node is either red or black.
2. The root is always black.
3. Every leaf (NIL) is black.
4. If a node is red, both its children are black (no consecutive red nodes).
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

•Guaranteed O(log n) search, insert, and delete performance bounded by 2 log₂(n + 1).
•Requires at most 2 rotations on insert and at most 3 rotations on delete (faster write throughput than AVL).
•Industry standard balancing engine powering high-performance associative containers.

Trade-offs & Limitations

•Slightly taller tree height than strictly balanced AVL trees, resulting in marginally slower lookup times.
•Complex case-based fixup implementation logic.
•Stores color metadata alongside left, right, and parent pointers.

Real-World Applications

C++ STL std::map & std::set

Underlying self-balancing search tree in standard associative template libraries.

Linux Completely Fair Scheduler (CFS)

Indexes runnable tasks ordered by execution virtual runtime in an RB-Tree.

Java java.util.TreeMap

Red-Black tree backing NavigableMap and NavigableSet interfaces.

Decision Guide: When to Use

Ideal Scenarios

✓When operations involve a balanced mix of search, insertion, and deletion.
✓When predictable worst-case latency is mandatory for transactional data.

Consider Alternatives When

✕When reads overwhelmingly dominate writes (use AVL Tree for shallower search depth).
✕When keys are simple strings (use Trie for prefix matching).

Compare trade-offs and complexity across complementary tools in AlgoViz.

AVL Tree B-Tree Binary Search