If a tree is perfectly balanced, then a search will visit no more than lg n nodes.
If a tree is perfectly skewed, a search might visit all n nodes.
lg 16777216 = 24.
"self-balancing trees": removes the skew while you use them!
"What if perfection isn't the goal? What if 'good enough' is the goal?"
AVL Trees Search: 1.6 lg n
Red-Black Trees Search: 2 lg n
B-Trees (Balanced Trees) Search: different system (trees are not even binary)
Red Black Trees:
Every node has a color: red or black
1. The root is always black
2. NULL is always black (even though NULL isn't really a node)
3. The parent of a red node is always black. (No two red nodes in a row.)
4. The number of black nodes on any path from root to NULL is the same as the number of black nodes on any other path from root to NULL.