lib/splay-tree.js
/**
* @module lib/splay-tree
* @license MIT Copyright 2014 Daniel Imms (http://www.growingwiththeweb.com)
*/
'use strict';
if (typeof exports === 'object' && typeof define !== 'function') {
var define = function (factory) {
factory(require, exports, module);
};
}
define(function (require, exports, module) {
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;
});