Trees: SplayTree

Self-balancing binary search tree with amortized O(log n) splaying operations and subtree-size augmentation (order statistics). Recently accessed nodes are splayed to the root, providing a natural caching effect. Set semantics: duplicates are not stored.

Legend for tables

• API
  • options - an object with optional properties: less and compare:
    • less(a, b) - a function prototyped as a < b (the default)
    • compare(a, b) - a function prototyped as a - b. See Array.prototype.sort() for more info. Default: null.
      • If specified, it overrides less.
  • value - the value to be stored in the tree
  • range - an object with optional inclusive bounds: from and to
• Complexity
  • O - complexity of an operation
  • O(1) - constant time
  • O(n) - linear time proportional to the tree size
  • O(log n) - logarithmic time
  • O(k) - linear time proportional to the argument size
  • O(k log k) - linearithmic time proportional to the argument size

tree/splay-tree.js

Implementation of SplayTree.

import SplayTree from 'list-toolkit/tree/splay-tree.js';

Class SplayTreeNode

Properties: value, left, right, parent, size (subtree size: the node plus all descendants, maintained by the tree). Methods: getMin(), getMax() (subtree extremes).

Class SplayTree

Methods:

Member	Return type	Description	O
constructor(options)	SplayTree	Create a new splay tree.	O(1)
root	SplayTreeNode | null	The root of the splay tree.	O(1)
size	number	The number of nodes in the splay tree.	O(1)
compare	function | null	Comparator from options (or null if less was given instead).	O(1)
less	function	Less-than function (derived from compare if both are given).	O(1)
isEmpty	truthy/falsy	Checks if the splay tree is empty.	O(1)
length	number	The number of nodes in the splay tree. An alias of size.	O(1)
getMin()	SplayTreeNode | null	Minimum node, or null on empty tree.	O(log n) *
getMax()	SplayTreeNode | null	Maximum node, or null on empty tree.	O(log n) *
find(value)	SplayTreeNode or null	Find the node in the splay tree with the specified value.	O(log n) *
has(value)	boolean	Checks if the specified value is present.	O(log n) *
floor(value)	SplayTreeNode or null	The node with the greatest value ≤ value.	O(log n) *
ceil(value)	SplayTreeNode or null	The node with the smallest value ≥ value.	O(log n) *
at(index)	SplayTreeNode or null	The node at a position in sorted order. Negative indices count from the end.	O(log n) *
indexOf(value)	number	The position of the specified value in sorted order, or -1 if absent.	O(log n) *
promote(value)	SplayTreeNode or null	Find and promote (splay) the node in the splay tree with the specified value.	O(log n)
splay(node)	this	Splay the specified node in the splay tree to the top.	O(log n)
insert(value)	this	Insert the specified value into the splay tree. Duplicates are not stored.	O(log n)
remove(value)	this	Remove the specified value from the splay tree.	O(log n)
clear()	this	Clear the splay tree.	O(1)
splitMaxTree(value)	SplayTree	Split off values greater than the specified value into a new tree.	O(log n)
join(tree)	this	Join the specified splay tree with the splay tree.	O(log n)
joinMaxTreeUnsafe(tree)	this	Like join but skips the max-vs-min check; caller guarantees tree values exceed this's max.	O(log n)
[Symbol.iterator]()	iterator	Get an iterator for the splay tree.	O(1)
getIterator(range)	iterable	Ascending values within inclusive {from, to} bounds.	O(1)
getNodeIterator(range)	iterable	Ascending nodes within inclusive {from, to} bounds.	O(1)
getReverseIterator()	iterable	Get an iterator for the splay tree in reverse order.	O(1)

* Read-only: does not splay. The cost is O(depth) — O(log n) on a balanced shape, O(n) worst case on a degenerate one — and read-only lookups carry no amortized guarantee of their own. The unstarred O(log n) entries are amortized bounds of splaying operations.

Static members:

Member	Return type	Description	O
from(values, options)	SplayTree	Create a splay tree from an iterable.	O(k log k)
defaults	object	Default {less, compare} used when options are omitted.	O(1)

Notes on properties and methods

No strict balancing invariant — a single splaying operation is O(n) worst case, O(log n) amortized.

The amortized bound is maintained only by splaying accesses: promote(), insert(), remove(), splitMaxTree(), join(). find() and the other read-only lookups do not splay — a lookup-only workload on an adversarial shape stays O(n) per operation. Use promote() (= find() + splay()) when the access pattern should adapt the tree.

Set semantics: duplicates are not stored. insert() of an existing value splays its node to the root and leaves the tree unchanged.

Every node maintains its subtree size (node.size), which powers the order statistics (at(), indexOf()) and the O(log n) splitMaxTree() at a constant per-node space cost. Size maintenance makes rotations measurably more expensive (see bench/bench-trees.js: pure insert/remove churn is ~1.4x slower than an unaugmented tree, while split+join is orders of magnitude faster).

splitMaxTree(value) moves nodes with values greater than value into a new tree — amortized O(log n). join(tree) merges tree into this; most efficient (amortized O(log n)) when tree values exceed the current maximum, otherwise it falls back to per-value inserts. The argument tree is cleared.

Exports

SplayTree is the default export. SplayTreeNode is exported by name.