[binarybanana]

>splay tree

Oh yes!

Probably my favorite data structure. In the past I've used them instead of arrays for performance (latency) reasons when constructing ordered sets from randomly distributed elements that came in multiple batches. Insertion into a splay tree meant that no sorting step at the end was necessary and the overhead was lower than first collecting everything into an array and only sorting after all elements were inserted.

Their amortized performance characteristics in general are close to ideal and the self-tuning character is intriguing. The only downside is the possibility of getting into a degenerate state, but that can be avoided by adding some randomness. Some paper I read even suggested that splaying only occasionally actually improves performance.

[bob1029]

> The only downside is the possibility of getting into a degenerate state, but that can be avoided by adding some randomness.

If you use GUID keys, this problem magically goes away with zero effort.