18.5 Summary
Last updated
Last updated
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 is a red-black tree that corresponds to 2-3-4 trees.
2-3-4 trees allow glue links on either side (see ).
More complex implementation, but faster.