Balancing Tree Algorithms

The goal of this section is not to actually study tree-balancing algorithms (that's an Algorithms topic) but to give a more concrete sense of how those algorithms work.

Opinion: If you find yourself heading off to implement a self-balancing binary search tree; do yourself a favor and don't do it. If you just need association, use a hashmap instead. If you do need the ordered-nature, implement a SkipList instead -- for basically the same performance, the code/algorithms are much simpler! (Pugh, 1990)

Why we Balance Trees (3:28)

Tree Rotations (3:04)

AVL Self-Balancing Algorithm Overview (5:11)

Red-Black Self-Balancing Algorithm Overview (2:25)

Treaps & SkipLists (2:23)