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.
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.