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: