Blog
Four ways to keep a tree balanced
A search tree is only fast while it stays short, and there are surprisingly different ways to keep it that way: measure heights, colour nodes, roll dice, or give up on binary altogether. Add and delete values in all four and watch each one repair itself a step at a time.