Splay tree – binary search tree with faster repeated access (en.wikipedia.org)

I found splay trees because Wikipedia mentioned them as being particularly useful for discrete-event simulations: http://en.wikipedia.org/wiki/Discrete_event_simulation

> The pending event set is typically organized as a priority queue, sorted by event time. That is, regardless of the order in which events are added to the event set, they are removed in strictly chronological order. Several general-purpose priority queue algorithms have proven effective for discrete-event simulation, most notably, the splay tree. More recent alternatives include skip lists, calendar queues, and ladder queues.

Splay trees are much easier to code than red-black trees, but have the very annoying property of being mutable even in pure read workloads.

Here is a previous HN discussion about splay trees: https://news.ycombinator.com/item?id=1370986