Red Black Trees Performance

Last updated Dec 30, 2022

• Data structures
• Software

• LLRB has height $O(log(n))$
• Contains is trivially $O(log(n))$
• Insert is $O(log(n))$
  • $O(log(n))$ to add new node
  • $O(log(n))$ to fix up tree (rotation and color flips)

We won’t discuss delete because it’s uninteresting.

• BSTs are simple, but they are subject to imbalance.
• 2-3 Trees (B-Trees) are balanced, but are painful to implement and are slow.
• LLRBs insertion is simple to implement (but delete is hard).
  • Works by maintaining a mathematical bijection with 2-3 trees.
• Java’s TreeMap is a red-black tree (not left leaning).
• Maintains correspondence with a 2-3-4 tree (is not a 1-1 correspondence).
• Allows glue links on either side
• More complex implementation, but significantly (?) faster.

There are many other types of search trees out there. AVL trees, splay trees, treaps, etc.

• And there are other efficient ways to implement sets and maps entirely.
  • Skip lists
  • Hashing (the most common alternatives)