A search tree that moves what you use to the top.

A self-adjusting binary search tree for JavaScript and TypeScript. Every lookup rotates the key to the root, so the keys you use often stay a few steps away. Click a node to look it up.

D. D. Sleator, R. E. Tarjan. Self-adjusting binary search trees. Journal of the ACM 32(3), 652–686, 1985.

click
search path  often used    
2 KBminified and gzipped
0dependencies
100%test coverage: lines, branches and functions
No recursiontop-down splaying, safe on deep trees

A sorted map with a comparator

Keys can be anything your comparator orders. Nodes carry a key and a data field. insert keeps duplicates, add skips keys that are already there.

npm install splaytree
<script src="https://unpkg.com/splaytree">
import SplayTree from "splaytree";

const tree = new SplayTree<number, string>();
tree.insert(5, "five");
tree.insert(-10, "minus ten");
tree.insert(33, "thirty-three");
tree.insert(2, "two");

tree.keys();          // [-10, 2, 5, 33]
tree.find(5)?.data;   // "five", and 5 is now the root
tree.root?.key;       // 5

// Keys in [0, 10], in order
tree.range(0, 10, (node) => { console.log(node.key); }); // 2, 5

// Any key type, with your own ordering: SplayTree<Date, unknown>
const byDate = new SplayTree((a: Date, b: Date) => a.getTime() - b.getTime());

API

Methods marked splays restructure the tree around the key they touch. The others only read it, so they leave its shape as it is.


        

Benchmarks

Operations per second, higher is better, against the avl and bintrees red-black tree. Uniformly random reads are the worst case for a splay tree: every lookup reshapes the tree. It pays off when some keys are read much more often than others.

Apple M3, Node 24.21, 1,000 or 10,000 distinct random integer keys from a fixed seed. Reproduce with npm run bench.