Left Leaning Red-Black BSTs (LLRB tree)

Red-Black Tree

• Represent 2-3 tree as a BST
• Use internal left-leaning links as glue for 3-nodes

Properties

• No node has two red links connected to it
• Every path from root to null link has the same number of black links
• Red links lean left

Operations

Search

Implementation

Left rotation - Orient a (temporarily) right-leaning red link to lean left

Right rotation - Orient a left-leaning red link to (temporarily) lean right

Color flip - Recolor to split a (temporary) 4-node

Insertion in a LLRB tree

Basic Strategy

Insert into a tree with exactly 1 node

• Insert into a 2-node at the bottom
  • Do standard BST insert; color new link red
  • If new red link is a right link, rotate left

Insert into a tree with exactly 2 nodes

• Insert into a 3-node at the bottom
  • Do standard BST insert; color new link red
  • Rotate to balance the 4-node
  • Flip colors to pass red link up one level
  • Rotate to make lean left
  • Repeat case 1 or case 2 up the tree

Insertion Code

If implemented properly, the height of a red-black BST with N keys is at most 2 lg N

Applications

Red-black trees are widely used as system symbol tables

• Java: Java.util.TreeMap, java.util.TreeSet
• C++ STL: map, multimap, multiset
• Linux kernel: completely fair scheduler, linux/rbtree.h
• Emacs: conservative stack scanning