Red Black Tree

A red–black tree is a data structure which is a type of self-balancing binary search tree.

Balance is preserved by painting each node of the tree with one of two colors (typically called 'red' and 'black') in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently.

The balancing of the tree is not perfect but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time.

Wikipedia

var tree = new RBTree(); //an empty tree

Methods

getIterator()

This method returns an iterator for scanning the tree. The iterator is useful in order to get a full decoupling in your classes. This avoid, to the class that uses the iterator, to know what type of data structure stores the data.

var tree = new RBTree();
var it = list.getIterator();
for(it.first(); !it.isDone(); it.next()) {
  var item = it.getItem();
  //do something
}

The iterator starts from the most left item of the tree.

Complexity: O(1)

insert(key, item)

This method insert the item into the tree. The item could be whatever you want.

var tree = new RBTree();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2

Complexity: O(log n)

search(key, node, callback)

This method search the item relatives to the key in the tree that satisfy the condition represented by the callback function. The search could start from a desired node of the tree but this parameter could be omitted. The search returns undefined if the key there isn't in the tree.

var tree = new RBTree();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.search(0); //8
tree.search(0, tree.maximum()); //undefined

If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the node the iteration is working on.

var tree = new RBTree();
var callback = function(node) { //this function checks if there is a number lower than 5.
  return node.item < 5;
};
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.search(1, null, callback); //2

In this example we deal with more complex items.

var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var tree = new RBTree();
tree.insert(0, itemA);
tree.insert(1, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA 
  return item.parent === itemA;
};
tree.contains(1, null, callback); //itemA

Complexity: O(log n)

minimum(node)

This method returns the node relatives to the minimum key of the tree. The parameter node is optional, but it's necessary if you desire the minimum key of the tree represented by the node as root.

var tree = new RBTree();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.minimum(); //8
tree.minimum(tree.maximum()); //2

Complexity: O(log n)

maximum(node)

This method returns the node relatives to the maximum key of the tree. The parameter node is optional, but it's necessary if you desire the maximum key of the tree represented by the node as root.

var tree = new RBTree();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.maximum(); //2
tree.maximum(tree.minimum()); //8

Complexity: O(log n)

successor(node)

This method returns the node that's the successor in the tree. If the node correspond with the maximum, null will be returned.

var tree = new RBTree();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.successor(tree.minimum()); //2
tree.successor(tree.maximum()); //null

Complexity: O(log n)

predecessor(node)

This method returns the node that's the predecessor in the tree. If the node correspond with the minimum, null will be returned.

var tree = new RBTree();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.successor(tree.maximum()); //8
tree.successor(tree.minimum()); //null

Complexity: O(log n)

deleteNode(node)

This method delete the node from the tree.

var tree = new RBTree();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.deleteNode(tree.maximum()); //tree contains 2

Complexity: O(log n)

contains(key, node, callback)

This method checks if the tree contains a node whose key satisfies the condition represented by the callback function. The callback could be omitted. In this case the method checks if the node key is simply equal to the key parameter. The search starts from the root if the node parameter is not specified. Otherwise could be useful to pass a node for check if the tree contains the node in a specific branch.

var tree = new RBTree();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
tree.contains(2); //true
tree.contains(5); //false
tree.contains(2, tree.maximum()); // false

If you desire a more complex research of a node you need to pass also the callback parameter. The callback must accept the node the iteration is working on. In that case the key parameter could be omitted because it won't be used to evaluate the condition.

var tree = new RBTree();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
var callback = function(node) { //this function checks if there is a node with a item whose value is lower than 5.
  return node.item < 5;
};
tree.contains(null, null, callback); //true

In this example we deal with more complex items.

var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var tree = new RBTree();
tree.insert(0, itemA); //tree contains itemA
tree.insert(1, itemB); //tree contains itemA, itemB
var callback = function(node) { //this function checks if there is an item whose parent is itemA 
  return node.item.parent === itemA;
};
tree .contains(null, null, callback); //true

Complexity: O(log n)

fullContains(callback)

This method checks if the tree contains a node that satisfies the callback. The search avoid to check the key of the node so the search is made in the entire tree. This affect the performance because the search doesn't reach directly the node. The callback must accept the node the iteration is working on.

var tree = new RBTree();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
var callback = function(node) { //this function checks if there is a node with a item whose value is lower than 5.
  return node.item === 2;
};
tree.fullContains(callback); //true

Complexity: O(n)