Trees: SplayTree

Self-balancing binary search tree with amortized O(log n) operations. Recently accessed nodes are splayed to the root, providing a natural caching effect.

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

tree/splay-tree.js

Implementation of SplayTree.

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

Class SplayTreeNode

Properties: value, left, right, parent. 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)
promote(value)	SplayTreeNode or null	Find and promote 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.	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 the splay tree at the maximum node with the specified value.	O(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)
getReverseIterator()	iterator	Get an iterator for the splay tree in reverse order.	O(1)

Static members:

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

Notes on properties and methods

No strict balancing invariant — worst case is O(n), but amortized O(log n).

splay(node) rotates the node to root. find() does not splay; promote() = find() + splay().

splitMaxTree(value) moves nodes with values greater than value into a new tree — O(n): subtree sizes are recomputed by a recursive walk, which is also O(n) stack on degenerate (chain-shaped) trees. join(tree) merges tree into this; most efficient when tree values exceed the current maximum. The argument tree is cleared.

Exports

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