# 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](https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/999dbd4192d0f819cb5224f26e9e7fa75ca6f289/src/java.base/share/classes/java/util/TreeMap.java) 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](http://en.wikipedia.org/wiki/Red%E2%80%93black_tree)).
  * More complex implementation, but faster.