A+DS

Red-Black Tree

Self-balancing BST with red and black coloring rules.

A Red-Black Tree is a self-balancing BST where each node is colored red or black. By enforcing five properties (root is black, red nodes have black children, all paths have equal black-node count, etc.), the tree guarantees O(log n) height. On insert, fix-up uses recoloring and rotations.

       [20 B]
      /       \
   [10 R]    [30 R]
   /    \       \
 [5 B] [15 B]  [25 B]

  Insert 1: new RED leaf under 5
  5 is RED, uncle 15 is RED → Case 1
  Recolor: 5=B, 15=B, 10=R
  Root stays BLACK

How it works

  1. 1Insert as a red node using standard BST insertion
  2. 2If parent is red, apply fix-up cases
  3. 3Case 1: Uncle is red → recolor parent, uncle, grandparent
  4. 4Cases 2-3: Uncle is black → rotate and recolor

Loading...