Originally from here, I've added some polish.

This code runs on CPython 2.x, CPython 3.x, Pypy and Jython. It also passes pylint, and has a suite of automated tests.

A splay tree is always implicitly sorted, but is reordered on each fetch or store to optimize for the most-recently-used value being used again. For this reason, they get used for caches a lot.

However, when I benchmarked a cache with a splay tree against a cache with a treap, the treap outperformed the splay tree - just FYI.

You can check it out from here. It's Apache v2 licensed.

See also this list of datastructures I've worked on.

You can e-mail the author with questions or comments: