The part where he explains how a binary tree can be unbalanced, and when, was really surprising to me. Never assume that just because your accesses are random that the tree will remain balanced on average.