[nmwnmw]

My personal favorite of these is the Splay Tree[1]. I've never used it in production, but it's really simple to implement and reason about. Though my main experience was trying (and failing) to prove amortized bounds on the operations.

[1] https://en.wikipedia.org/wiki/Splay_tree

[3PS]

If anything, the incredibly convoluted amortized analysis that goes into proving bounds on the cost of splay tree operations is perhaps more iconic than the actual splay tree data structure.

[jvanderbot]

Tarjan and Sleator are legends.