Trees: SplayTree

Splay tree is a data structure that represents a binary search tree. It is a self-balancing binary search tree that is useful when the tree is very large and the number of operations is large. It allows to perform typical operations in O(log n) time. Additionally, it has a caching property that can be used to improve performance: recently accessed nodes are moved to the top of the tree.

This document describes the API of splay trees and their individual implementations.

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 cache size
  • O(log n) - logarithmic time
  • O(k) - linear time proportional to the argument size

tree/splay-tree.js

This is the implementation of the SplayTree class.

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

Class SplayTreeNode

SplayTreeNode is used to represent nodes in the splay tree. It defines the following properties:

• value — the value of the node
• left — the left child of the node
• right — the right child of the node
• parent — the parent of the node

And the following methods:

• getMin() — get the minimum node in the subtree
• getMax() — get the maximum node in the subtree

Class SplayTree

This class represents a splay tree. It provides the following 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)

As a convenience, the following static methods are also available:

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

Notes on properties and methods

In general, a splay tree is a self-balancing binary search tree. But it doesn't enforce any balancing factor. In some cases it can be a linear structure with O(n) complexity. Yet its amortized complexity is O(log n).

splay() makes its argument the root of the splay tree.

find() does not change the position of the found note. promote() is effectively find() with splay() the found node.

splitMaxTree() splits the splay tree at the maximum node with the specified value. After it is done, nodes with values greater than the specified value are returned in a new splay tree. The original splay tree is left only with nodes with values less than the specified value.

join() joins the specified splay tree with the splay tree. It is especially efficient when the argument tree contains values greater than the maximum value in the original tree. If this condition is not satisfied, all values from the argument tree are inserted into the original tree. The argument tree is cleared after the operation.

Exports

SplayTree is the default export. Both SplayTree and SplayTreeNode are exported by names.