Splay tree
Published , updated
The splay tree is a type of self-adjusting binary search tree like the red-black tree. What makes the splay tree special is its ability to access recently accessed elements faster. Whenever an operation is performed, the tree performs an operation called splaying which pulls the element to the top of the tree.
The worst case height of a splay tree is n, this could be the case if all nodes were accessed in ascending order for example.
This makes the worst case complexity of the splay tree’s operations O(n). Since all operations also splay the tree on the node, the tree ends up roughly balancing itself, this results in a O(\log n) amortised worst case time complexity for all operations.
The splay tree is a particularly good choice as a data structure when it’s likely that the same nodes will be accessed multiple times in a short period. This is where the real power in the splay tree lies, in its ability to hoist nodes up to the root when they are accessed, giving speedy access for nearby successive accesses.
This article assumes knowledge of the binary search tree (BST) data structure.
Complexity
| Operation | Description | Complexity |
|---|---|---|
| Delete | Deletes a node given a key | O(\log n)* |
| Insert | Inserts a node with an associated key | O(\log n)* |
| Search | Searches for and returns a node using its key | O(\log n)* |
| Splay | Reorganises the tree, moving a particular node to the top | O(\log n)* |
* Amortised
Representation
There are two main ways of representing a binary tree. The first is using node objects that have references to their children.
The second is using a regular array and manipulating the index of the node to find its children. The index of the left child of a node is 2i + 1 and the index of the right is 2i + 2 where i is the index of the parent.
The index of node's parent can also be retrieved with \lfloor(i - 1) / 2\rfloor.
Parallelism
Due to the splay tree adjusting itself even after a “read-only” operation, the splay tree is probably not ideal in a multi-threaded application. If parallelism is desired, additional guards need to be put in place to protect against race conditions.
Operations
Rotation
The generic tree rotation operation is used to perform the below splaying operations. Here is an illustration of the process.
Splay(a)
The splay operation is performed to bring the node a that is being worked on to the root of the tree. It performs a series of operations called zig, zig-zig and zig-zag depending on the characteristics of a. Each operation has two variants depending on whether a or its parent are left or right children.
Zig(a)
This operation is performed when the parent of a is the root of the tree. A left or right rotate is performed to bring a to the root of the tree.
Zig-zig(a)
This operation is performed when a and its parent are the same child type as each other (both left children or both right children). It performs either two right rotations or two left rotations depending on the side. Its name is derived from the fact that the rotations performed are of the same type.
Zig-zag(a)
This operation is performed when a is a different child type to its parent. It performs a rotation of both types (left then right, or right then left) depending on the child type of a.
Delete(a)
Delete can be implemented two different ways:
- by performing a regular BST delete on the node a and then splaying the tree on what was a’s parent, or
- by splaying the node a and then performing a regular BST delete on the a.
Insert(a)
Insert performs a regular BST insert and then splays the tree on the node a, adjusting the tree so that the inserted node is at the root of the tree.
Search(a)
Search performs a regular BST search and then splays the tree on the node a, adjusting the tree so that the searched node is at the root of the tree.
Which binary search tree is best?
The AVL tree, red-black tree and splay tree are all self-adjusting binary search trees, so which one is better in which situation? And when is it better to use a regular BST?
A paper by Ben Pfaff of Stanford University performs an in-depth study of the performance characteristics of each tree under various circumstances. Each data structure excels based on runtime patterns in the input and the calling of operations. It comes to the following conclusions:
- Regular BSTs excel when randomly ordered input can be relied upon.
- Splay trees excel when data is often inserted in a sorted order and later accesses are sequential or clustered.
- AVL trees excel when data is often inserted in a sorted order and later accesses are random.
- Red-black trees excel when data is often inserted in random order but occasional runs of sorted order are expected.
Code
public class SplayTree<T extends Comparable<T>> {
private SplayTreeNode<T> root;
public SplayTree() { }
private void splay(SplayTreeNode<T> node) {
while (node.parentExists()) {
SplayTreeNode parent = node.getParent();
if (!parent.parentExists()) {
if (parent.getLeft() == node) {
rotateRight(parent);
} else {
rotateLeft(parent);
}
} else {
SplayTreeNode gparent = parent.getParent();
if (parent.getLeft() == node && gparent.getLeft() == parent) {
rotateRight(gparent);
rotateRight(node.getParent());
} else if (parent.getRight() == node &&
gparent.getRight() == parent) {
rotateLeft(gparent);
rotateLeft(node.getParent());
} else if (parent.getLeft() == node &&
gparent.getRight() == parent) {
rotateRight(parent);
rotateLeft(node.getParent());
} else {
rotateLeft(parent);
rotateRight(node.getParent());
}
}
}
}
private void rotateLeft(SplayTreeNode<T> x) {
SplayTreeNode y = x.getRight();
x.setRight(y.getLeft());
if (y.getLeft() != null) {
y.getLeft().setParent(x);
}
y.setParent(x.getParent());
if (x.getParent() == null) {
root = y;
} else {
if (x == x.getParent().getLeft()) {
x.getParent().setLeft(y);
} else {
x.getParent().setRight(y);
}
}
y.setLeft(x);
x.setParent(y);
}
private void rotateRight(SplayTreeNode<T> x) {
SplayTreeNode y = x.getLeft();
x.setLeft(y.getRight());
if (y.getRight() != null) {
y.getRight().setParent(x);
}
y.setParent(x.getParent());
if (x.getParent() == null) {
root = y;
} else {
if (x == x.getParent().getLeft()) {
x.getParent().setLeft(y);
} else {
x.getParent().setRight(y);
}
}
y.setRight(x);
x.setParent(y);
}
public void insert(T key) {
if (root == null) {
root = new SplayTreeNode(key, null);
return;
}
insert(key, root);
search(key);
}
private void insert(T key, SplayTreeNode<T> node) {
if (key.compareTo( node.getKey() ) < 0) {
if (node.leftExists()) {
insert(key, node.getLeft());
} else {
node.setLeft(new SplayTreeNode(key, node));
}
}
if (key.compareTo(node.getKey())>0) {
if (node.rightExists()) {
insert(key, node.getRight());
} else {
node.setRight(new SplayTreeNode(key, node));
}
}
}
public void delete(T key) {
if (root == null) {
return;
}
search(key);
delete(key, root);
}
private void delete(T key, SplayTreeNode<T> node) {
if (key.compareTo(node.getKey())< 0) {
if (node.leftExists()) {
delete(key, node.getLeft());
}
if (node.getLeft().isDeleted()) {
node.setLeft(null);
}
return;
}
if (key.compareTo(node.getKey()) > 0) {
if (node.rightExists()) {
delete(key, node.getRight());
}
if (node.getRight().isDeleted()) {
node.setRight(null);
}
return;
}
delete(node);
}
private void delete(SplayTreeNode<T> node) {
if (!(node.leftExists() || node.rightExists())) {
node.setDeleted(true);
return;
}
if (node.leftExists() && !node.rightExists()) {
node.setKey(node.getLeft().getKey());
if (node.getLeft().rightExists()) {
node.setRight(node.getLeft().getRight());
}
if (node.getLeft().leftExists()) {
node.setLeft(node.getLeft().getLeft());
} else {
node.setLeft(null);
}
return;
}
if (node.rightExists() && !node.leftExists()) {
node.setKey(node.getRight().getKey());
if (node.getRight().leftExists()) {
node.setLeft(node.getLeft().getLeft());
}
if (node.getRight().rightExists()) {
node.setRight(node.getLeft().getRight());
} else {
node.setRight(null);
}
return;
}
// both exist, replace with minimum from right sub-tree
T min = findMin(node.getRight());
node.setKey(min);
}
private T findMin(SplayTreeNode<T> node) {
if (!node.leftExists()) {
node.setDeleted(true);
return node.getKey();
}
T min = findMin(node.getLeft());
if (node.getLeft().isDeleted()) {
node.setLeft(null);
}
return min;
}
public boolean search(T key) {
if (root == null) {
return false;
}
SplayTreeNode<T> node = search(key, root);
splay(node);
return node != null;
}
private SplayTreeNode<T> search(T key, SplayTreeNode<T> node) {
if (key == node.getKey()) {
return node;
}
if (key.compareTo(node.getKey()) < 0) {
if (!node.leftExists()) {
return null;
}
return search(key, node.getLeft());
}
if (key.compareTo(node.getKey()) > 0) {
if (!node.rightExists()) {
return null;
}
return search(key, node.getRight());
}
return null;
}
public String toString() {
return root.toString();
}
}
public class SplayTreeNode<T extends Comparable<T>> {
private final String nullNodeString = "_";
private SplayTreeNode<T> left;
private SplayTreeNode<T> right;
private SplayTreeNode<T> parent;
private T key;
private boolean isDeleted = false;
public SplayTreeNode(T key, SplayTreeNode<T> parent) {
this.key = key;
this.parent = parent;
}
@Override
public String toString() {
return key + " : { " +
(leftExists() ? left.toString() : nullNodeString) + " , " +
(rightExists() ? right.toString() : nullNodeString) + " }";
}
public boolean leftExists() {
return left != null;
}
public boolean rightExists() {
return right != null;
}
public boolean parentExists() {
return parent != null;
}
public T getKey() {
return key;
}
public void setKey(T key) {
this.key = key;
}
public SplayTreeNode<T> getLeft() {
return left;
}
public void setLeft(SplayTreeNode<T> left) {
this.left = left;
}
public SplayTreeNode<T> getRight() {
return right;
}
public void setRight(SplayTreeNode<T> right) {
this.right = right;
}
public boolean isDeleted() {
return isDeleted;
}
public void setDeleted(boolean isDeleted) {
this.isDeleted = isDeleted;
}
public SplayTreeNode<T> getParent() {
return parent;
}
public void setParent(SplayTreeNode<T> parent) {
this.parent = parent;
}
}// file: splay-tree.js
var BaseBinaryTree = require('./base-binary-tree');
var BinaryTreeNode = require('./binary-tree-node');
/**
* Creates a splay tree.
*
* @constructor
* @param {function} customCompare An optional custom node comparison
* function.
*/
var SplayTree = function (customCompare) {
BaseBinaryTree.call(this);
this.nodeCount = 0;
if (customCompare) {
this.compare = customCompare;
}
};
SplayTree.prototype = Object.create(BaseBinaryTree.prototype);
SplayTree.prototype.constructor = SplayTree;
/**
* Adds a key to the tree.
*
* @param {Object} key The key to add.
* @return {boolean} Whether the node was added.
*/
SplayTree.prototype.add = function (key) {
if (!this.root) {
this.root = new BinaryTreeNode(key);
this.nodeCount++;
return true;
}
var wasAdded = insertInternal(this, key, this.root);
this.contains(key);
return wasAdded;
};
/**
* Determines whether the tree contains a key.
*
* @param {Object} key The key to check.
* @return {boolean} Whether the node contains the key.
*/
SplayTree.prototype.contains = function (key) {
if (!this.root) {
return false;
}
var node = containsInternal(this, key, this.root);
if (node) {
splay(this, node);
}
return !!node;
};
/**
* @return {Object} The maximum key of the tree.
*/
SplayTree.prototype.findMaximum = function () {
if (!this.root) {
return undefined;
}
var current = this.root;
while (true) {
if (current.right) {
current = current.right;
} else {
return current.key;
}
}
};
/**
* @return {Object} The minimum key of the tree.
*/
SplayTree.prototype.findMinimum = function () {
if (!this.root) {
return undefined;
}
var current = this.root;
while (true) {
if (current.left) {
current = current.left;
} else {
return current.key;
}
}
};
/**
* @return {boolean} Whether the tree is empty.
*/
SplayTree.prototype.isEmpty = function () {
return !this.root;
};
/**
* Removes a key from the tree.
*
* @param {Object} key The key to remove.
* @return {boolean} Whether the key was removed.
*/
SplayTree.prototype.remove = function (key) {
if (!this.root) {
return false;
}
this.contains(key);
return removeInternal(this, key, this.root);
};
/**
* @return The size of the tree.
*/
SplayTree.prototype.size = function () {
return this.nodeCount;
};
/**
* Compares two nodes with each other.
*
* @param {Object} a The first key to compare.
* @param {Object} b The second key to compare.
* @return -1, 0 or 1 if a < b, a == b or a > b respectively.
*/
SplayTree.prototype.compare = function (a, b) {
if (a > b) {
return 1;
}
if (a < b) {
return -1;
}
return 0;
};
/**
* Rotates a node in a tree left.
*
* a b
* / \ / \
* c b -> rotateLeft(a) -> a e
* / \ / \
* d e c d
*
* @param {SplayTree} tree The splay tree.
* @param {BinaryTreeNode} x The node being rotated.
*/
function rotateLeft(tree, x) {
var y = x.right;
x.right = y.left;
if (y.left) {
y.left.parent = x;
}
y.parent = x.parent;
if (!x.parent) {
tree.root = y;
} else {
if (x === x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
}
y.left = x;
x.parent = y;
}
/**
* Rotates a node in a tree right.
*
* b a
* / \ / \
* a e -> rotateRight(b) -> c b
* / \ / \
* c d d e
*
* @param {SplayTree} tree The splay tree.
* @param {BinaryTreeNode} x The node being rotated.
*/
function rotateRight(tree, x) {
var y = x.left;
x.left = y.right;
if (y.right) {
y.right.parent = x;
}
y.parent = x.parent;
if (!x.parent) {
tree.root = y;
} else {
if (x === x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
}
y.right = x;
x.parent = y;
}
/**
* Inserts a key into the tree rooted on a particular node.
*
* @param {SplayTree} tree The tree to insert into.
* @param {Object} key The key to insert.
* @param {BinaryTreeNode} node The tree's node to insert until.
*/
function insertInternal(tree, key, node) {
if (tree.compare(key, node.key) < 0) {
if (node.left) {
return insertInternal(tree, key, node.left);
} else {
node.left = new BinaryTreeNode(key, node);
tree.nodeCount++;
return true;
}
}
if (tree.compare(key, node.key) > 0) {
if (node.right) {
return insertInternal(tree, key, node.right);
} else {
node.right = new BinaryTreeNode(key, node);
tree.nodeCount++;
return true;
}
}
return false;
}
function containsInternal(tree, key, node) {
if (key === node.key) {
return node;
}
if (tree.compare(key, node.key) < 0) {
if (!node.left) {
return undefined;
}
return containsInternal(tree, key, node.left);
}
if (tree.compare(key, node.key) > 0) {
if (!node.right) {
return undefined;
}
return containsInternal(tree, key, node.right);
}
return undefined;
}
function removeInternal(tree, key, node) {
if (tree.compare(key, node.key) < 0) {
if (node.left) {
return removeInternal(tree, key, node.left);
}
return false;
}
if (tree.compare(key, node.key) > 0) {
if (node.right) {
return removeInternal(tree, key, node.right);
}
return false;
}
return removeInternal2(tree, node);
}
function removeInternal2(tree, node) {
if (!node.left && !node.right) {
removeNodeWithNoChildren(tree, node);
return true;
}
if (node.left && !node.right) {
removeNodeWithLeftOnly(tree, node);
return true;
}
if (node.right && !node.left) {
removeNodeWithRightOnly(tree, node);
return true;
}
// both exist, replace with node minimum from right sub-tree and delete the
// node from the right sub-tree
var minParent = findParentOfMinimum(node.right, node);
var minNode = minParent.left ? minParent.left : minParent.right;
var newKey = minNode.key;
removeInternal2(tree, minNode);
node.key = newKey;
return true;
}
/**
* Removes a node with no children.
*
* @param {SplayTree} tree The tree to remove the node from.
* @param {BinaryTreeNode} node The node to remove.
*/
function removeNodeWithNoChildren(tree, node) {
if (node.parent) {
node.parent.removeChild(node);
} else {
tree.root = undefined;
}
tree.nodeCount--;
}
/**
* Removes a node with a left child only, moving the left child in to the
* node's place.
*
* @param {SplayTree} tree The tree to remove the node from.
* @param {BinaryTreeNode} node The node to remove.
*/
function removeNodeWithLeftOnly(tree, node) {
node.key = node.left.key;
node.right = node.left.right;
if (node.right) {
node.right.parent = node;
}
node.left = node.left.left;
if (node.left) {
node.left.parent = node;
}
tree.nodeCount--;
}
/**
* Removes a node with a right child only, moving the right child in to the
* node's place.
*
* @param {SplayTree} tree The tree to remove the node from.
* @param {BinaryTreeNode} node The node to remove.
*/
function removeNodeWithRightOnly(tree, node) {
node.key = node.right.key;
node.left = node.right.left;
if (node.left) {
node.left.parent = node;
}
node.right = node.right.right;
if (node.right) {
node.right.parent = node;
}
tree.nodeCount--;
}
/**
* Splay the tree on a node, bringing it to the root using a series of
* rotation operations.
*
* @param {SplayTree} tree The tree being splayed.
* @param {BinaryTreeNode} node The node being splayed on.
*/
function splay(tree, node) {
while (node.parent) {
var parent = node.parent;
if (!parent.parent) {
if (parent.left === node) {
rotateRight(tree, parent);
} else {
rotateLeft(tree, parent);
}
} else {
var gparent = parent.parent;
if (parent.left === node && gparent.left === parent) {
rotateRight(tree, gparent);
rotateRight(tree, node.parent);
} else if (parent.right === node && gparent.right === parent) {
rotateLeft(tree, gparent);
rotateLeft(tree, node.parent);
} else if (parent.left === node && gparent.right === parent) {
rotateRight(tree, parent);
rotateLeft(tree, node.parent);
} else {
rotateLeft(tree, parent);
rotateRight(tree, node.parent);
}
}
}
}
/**
* @return {BinaryTreeNode} The parent of the minimum key node in the tree.
*/
function findParentOfMinimum(node, parent) {
if (!node.left) {
return parent;
}
return findParentOfMinimum(node.left, node);
}
module.exports = SplayTree;
// file: base-binary-tree.js
/**
* Creates a base binary tree.
* @constructor
*/
var BaseBinaryTree = function () {
/**
* The root of the tree.
* @protected
*/
this.root = undefined;
};
/**
* Performs a pre-order traversal, calling a function on each node.
*
* @param {function} visit A function that takes a node's key.
*/
BaseBinaryTree.prototype.traversePreOrder = function (visit) {
if (!this.root) {
return;
}
var parentStack = [];
parentStack.push(this.root);
do {
var top = parentStack.pop();
visit(top.key);
if (top.right) {
parentStack.push(top.right);
}
if (top.left) {
parentStack.push(top.left);
}
} while (parentStack.length);
};
/**
* Performs a in-order traversal, calling a function on each node.
*
* @param {function} visit A function that takes a node's key.
*/
BaseBinaryTree.prototype.traverseInOrder = function (visit) {
var parentStack = [];
var node = this.root;
while (parentStack.length || node) {
if (node) {
parentStack.push(node);
node = node.left;
} else {
node = parentStack.pop();
visit(node.key);
node = node.right;
}
}
};
/**
* Performs a post-order traversal, calling a function on each node.
*
* @param {function} visit A function that takes a node's key.
*/
BaseBinaryTree.prototype.traversePostOrder = function (visit) {
var parentStack = [];
var node = this.root;
var lastVisitedNode;
while (parentStack.length || node) {
if (node) {
parentStack.push(node);
node = node.left;
} else {
var nextNode = parentStack[parentStack.length - 1];
if (nextNode.right && lastVisitedNode !== nextNode.right) {
// if right child exists AND traversing node from left child, move
// right
node = nextNode.right;
} else {
parentStack.pop();
visit(nextNode.key);
lastVisitedNode = nextNode;
}
}
}
};
module.exports = BaseBinaryTree;
// file: binary-tree-node.js
/**
* Creates a binary tree node.
*
* @constructor
* @param {Object} key The key of the node.
* @param {BinaryTreeNode} parent The parent of the node.
*/
function BinaryTreeNode(key, parent) {
/**
* The key of the node.
* @public
*/
this.key = key;
/**
* The parent of the node.
* @public
*/
this.parent = parent;
/**
* The left child of the node.
* @public
*/
this.left = undefined;
/**
* The right child of the node.
* @public
*/
this.right = undefined;
}
/**
* Removes a child from the node. This will remove the left or right node
* depending on which one matches the argument.
*
* @param {Object} node The node to remove.
*/
BinaryTreeNode.prototype.removeChild = function (node) {
if (this.left === node) {
this.left = undefined;
}
if (this.right === node) {
this.right = undefined;
}
};
module.exports = BinaryTreeNode;// file: splayTree.ts
import { CompareFunction, ISplayTree, INode } from './types';
import { Node } from './node';
export class SplayTree<K, V> implements ISplayTree<K, V> {
protected _root?: Node<K, V>;
private _size = 0;
private _compare: CompareFunction<K> = defaultCompare;
constructor(
customCompare?: CompareFunction<K>
) {
if (customCompare) {
this._compare = customCompare;
}
}
public get size(): number {
return this._size;
}
public get isEmpty(): boolean {
return this._size === 0;
}
/**
* Inserts a key into the tree.
*
* @param key The key to insert.
* @return Whether the node was inserted.
*/
public insert(key: K, value?: V): boolean {
if (!this._root) {
this._root = new Node(key, value);
this._size++;
return true;
}
const result = this._insert(key, value, this._root);
if (result) {
// Splay tree
this.search(key);
}
return result;
}
/**
* Inserts a key into the tree rooted on a particular node.
*
* @param key The key to insert.
* @param node The current node insertion is being considered on.
* @return Whether the node was inserted.
*/
private _insert(key: K, value: V | undefined, node: Node<K, V>): boolean {
if (this._compare(key, node.key) < 0) {
if (node.left) {
return this._insert(key, value, node.left);
}
node.left = new Node(key, value, node);
this._size++;
return true;
}
if (this._compare(key, node.key) > 0) {
if (node.right) {
return this._insert(key, value, node.right);
}
node.right = new Node(key, value, node);
this._size++;
return true;
}
return false;
}
/**
* Searches the tree for a particular key.
*
* @param key The key to check.
* @return The node that was found or undefined.
*/
public search(key: K): INode<K, V> | undefined {
if (!this._root) {
return undefined;
}
const node = this._search(key, this._root);
if (node) {
this._splay(node);
}
return node;
}
/**
* Searches a node for a particular key.
*
* @param key The key to check.
* @param node The current node insertion is being considered on.
* @return The node that was found or undefined.
*/
private _search(key: K, node: Node<K, V>): Node<K, V> | undefined {
const result = this._compare(key, node.key);
if (result < 0) {
if (!node.left) {
return undefined;
}
return this._search(key, node.left);
}
if (result > 0) {
if (!node.right) {
return undefined;
}
return this._search(key, node.right);
}
return node;
}
/**
* @return The maximum key of the tree.
*/
public findMaximum(): INode<K, V> | undefined {
if (!this._root) {
return undefined;
}
let current = this._root;
while (true) {
if (current.right) {
current = current.right;
} else {
return current;
}
}
}
/**
* @return The minimum key of the tree.
*/
public findMinimum(): INode<K, V> | undefined {
if (!this._root) {
return undefined;
}
let current = this._root;
while (true) {
if (current.left) {
current = current.left;
} else {
return current;
}
}
}
/**
* Deletes a key from the tree.
*
* @param key The key to delete.
* @return Whether the key was deleted.
*/
public delete(key: K): boolean {
if (!this._root) {
return false;
}
// Splay tree
this.search(key);
return this._delete(key, this._root);
}
/**
* Deletes a key under a node.
*
* @param key The key to delete.
* @param node The current node to delete under.
* @return Whether the key was deleted.
*/
private _delete(key: K, node: Node<K, V>): boolean {
const result = this._compare(key, node.key);
if (result < 0) {
if (node.left) {
return this._delete(key, node.left);
}
return false;
}
if (result > 0) {
if (node.right) {
return this._delete(key, node.right);
}
return false;
}
this._delete2(node);
return true;
}
/**
* Deletes a node, adjusting children and parent links as appropriate.
*
* @param node The node being deleted.
* @return Whether the key was deleted.
*/
private _delete2(node: Node<K, V>): void {
if (!node.left && !node.right) {
this._deleteNodeWithNoChildren(node);
return;
}
if (node.left && !node.right) {
this._deleteNodeWithLeftOnly(node);
return;
}
if (node.right && !node.left) {
this._deleteNodeWithRightOnly(node);
return;
}
// both exist, replace with node minimum from right sub-tree and delete the
// node from the right sub-tree
const minParent = this._findParentOfMinimum(node.right!, node);
// The min node is guaranteed to be the left node not the right as this can
// only occur when the node has both children and if the parent of the
// minimum comes from the right sub-tree the parent must have a left node
const minNode = minParent.left!;
const newKey = minNode.key;
const newValue = minNode.value;
this._delete2(minNode);
node.key = newKey;
node.value = newValue;
}
/**
* Deletes a node with no children.
*
* @param tree The tree to delete the node from.
* @param node The node to delete.
*/
private _deleteNodeWithNoChildren(node: Node<K, V>): void {
if (node.parent) {
node.parent.removeChild(node);
} else {
this._root = undefined;
}
this._size--;
}
/**
* Deletes a node with a left child only, moving the left child in to the
* node's place.
*
* @param node The node to delete.
*/
private _deleteNodeWithLeftOnly(node: Node<K, V>): void {
node.key = node.left!.key;
node.value = node.left!.value;
node.right = node.left!.right;
if (node.right) {
node.right.parent = node;
}
node.left = node.left!.left;
if (node.left) {
node.left.parent = node;
}
this._size--;
}
/**
* Deletes a node with a right child only, moving the right child in to the
* node's place.
*
* @param node The node to delete.
*/
private _deleteNodeWithRightOnly(node: Node<K, V>): void {
node.key = node.right!.key;
node.value = node.right!.value;
node.left = node.right!.left;
if (node.left) {
node.left.parent = node;
}
node.right = node.right!.right;
if (node.right) {
node.right.parent = node;
}
this._size--;
}
/**
* Splay the tree on a node, bringing it to the root using a series of
* rotation operations.
*
* @param node The node being splayed on.
*/
private _splay(node: Node<K, V>): void {
while (node.parent) {
const parent = node.parent;
if (!parent.parent) {
if (parent.left === node) {
this._rotateRight(parent);
} else {
this._rotateLeft(parent);
}
} else {
const gparent = parent.parent;
if (parent.left === node && gparent.left === parent) {
this._rotateRight(gparent);
this._rotateRight(node.parent);
} else if (parent.right === node && gparent.right === parent) {
this._rotateLeft(gparent);
this._rotateLeft(node.parent);
} else if (parent.left === node && gparent.right === parent) {
this._rotateRight(parent);
this._rotateLeft(node.parent);
} else {
this._rotateLeft(parent);
this._rotateRight(node.parent);
}
}
}
}
/**
* @return The parent of the minimum key node in the tree.
*/
private _findParentOfMinimum(node: Node<K, V>, parent: Node<K, V>): Node<K, V> {
if (!node.left) {
return parent;
}
return this._findParentOfMinimum(node.left, node);
}
/**
* Rotates a node in a tree left.
*
* a b
* / \ / \
* c b -> rotateLeft(a) -> a e
* / \ / \
* d e c d
*.
* @param x The node being rotated.
*/
private _rotateLeft(x: Node<K, V>): void {
const y = x.right!;
x.right = y.left;
if (y.left) {
y.left.parent = x;
}
y.parent = x.parent;
if (!x.parent) {
this._root = y;
} else {
if (x === x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
}
y.left = x;
x.parent = y;
}
/**
* Rotates a node in a tree right.
*
* b a
* / \ / \
* a e -> rotateRight(b) -> c b
* / \ / \
* c d d e
*
* @param x The node being rotated.
*/
private _rotateRight(x: Node<K, V>): void {
const y = x.left!;
x.left = y.right;
if (y.right) {
y.right.parent = x;
}
y.parent = x.parent;
if (!x.parent) {
this._root = y;
} else {
if (x === x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
}
y.right = x;
x.parent = y;
}
}
/**
* Compares two nodes with each other.
* @param a The first key to compare.
* @param b The second key to compare.
* @return -1, 0 or 1 if a < b, a == b or a > b respectively.
*/
function defaultCompare<K>(a: K, b: K): number {
if (a > b) {
return 1;
}
if (a < b) {
return -1;
}
return 0;
}
// file: node.ts
import { INode } from './types';
export class Node<K, V> implements INode<K, V> {
/**
* The left child of the node.
*/
public left?: Node<K, V>;
/**
* The right child of the node.
*/
public right?: Node<K, V>;
/**
* Creates a binary tree node.
*
* @param key The key of the node.
* @param parent The parent of the node.
*/
constructor(
public key: K,
public value?: V,
public parent?: Node<K, V>
) {
}
/**
* Removes a child from the node. This will remove the left or right node
* depending on which one matches the argument.
*
* @param node The node to remove.
*/
public removeChild(node: Node<K, V>): void {
if (this.left === node) {
this.left = undefined;
}
if (this.right === node) {
this.right = undefined;
}
}
}
// file: types.d.ts
export type CompareFunction<K> = (a: K, b: K) => number;
export interface INode<K, V> {
readonly key: K;
readonly value?: V;
}
export interface ISplayTree<K, V> {
readonly isEmpty: boolean;
readonly size: number;
insert(key: K, value?: V): boolean;
search(key: K): INode<K, V> | undefined;
findMaximum(): INode<K, V> | undefined;
findMinimum(): INode<K, V> | undefined;
delete(key: K): boolean;
}Textbooks
Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.
