18.5 Summary
Binary search trees are simple, but they are subject to imbalance which leads to crappy runtime. 2-3 Trees (B Trees) are balanced, but painful to implement.
LLRB insertion is simple to implement (deletion is a bit harder to implement, we won't go over the specifics in this course).
Use three basic operations to maintain the balanced structure, namely rotateLeft, rotateRight, and color flip.
LLRBs maintain correspondence with 2-3 trees, Standard Red-Black trees maintain correspondence with 2-3-4 trees.
Java’s TreeMap is a red-black tree that corresponds to 2-3-4 trees.
2-3-4 trees allow glue links on either side (see Red-Black Tree).
More complex implementation, but faster.
Last updated