Red Black Tree

• Alternative to AVL Trees
• A Binary Search Tree
• Rules
  • A node is either red or black
  • The root is always black
  • A red node always has black children (null references are considered references to black nodes)
    • aka: no two consecutive red nodes
  • The number of black nodes in any path from the root to a leaf is the same
  • Null nodes are attached to the leaves and are black
    • Here for the proof of time complexity
• Derived from a B Tree of order 4
• Experimentally they have the best performance

Operations

Insertion

• Steps
  1. Insert the item into the binary search tree as usual
  2. Color Node
     • If it is the root → color it black and return
     • Else → color it red
  3. Check color
     • If the uncle is red 2. Change the color of parent and uncle to black 3. Change the color of a grandparent to red 4. Change x = x’s grandparent 5. Repeat steps 2 and 3 for new x
     • If the uncle is black
       1. rotate so the parent is where the grandparent was
       2. flip the colors of parent and uncle

Performance

Operation	Best Case	Worst Case
Searching	$O(\log n)$	$O(\log n)$
Insertion	$O(\log n)$	$O(\log n)$
Deletion	$O(\log n)$	$O(\log n)$

Applications

• Scheduling algorithms
• Backend to the C++ map class