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	The root of the splay tree.	O(1)
size	number	The number of nodes in the splay tree.	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	Get the minimum node in the splay tree.	O(log n)
getMax()	SplayTreeNode	Get the maximum node in the splay 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(log n)
join(tree)	this	Join the specified splay tree with the splay tree.	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 methods:

Member	Return type	Description	O
from(values, options)	SplayTree	Create a splay tree from an iterable.	O(k)

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