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 2 years ago

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 2 years ago