A splay tree module for Python is provided.

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.


Hits: 7647
Timestamp: 2024-11-10 07:50:29 PST

Back to Dan's tech tidbits

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