-
Notifications
You must be signed in to change notification settings - Fork 98
Red Black Tree List
This type of data structure is a normal red black tree but each node has a reference to his successor and predecessor. This change improve the operation for scanning the tree. While searching for a single element is better access from the route in O(log n) time, search a sequence of elements costs in practice more because predecessor and successor operations cost O(log n). With this data structure these operations takes O(1) time improving the speed of the searches that don't start form the root.
var tree = new RBTreeList(); //an empty treeThis 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 RBTreeList();
var it = tree.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.
This method insert the item into the tree. The item could be whatever you want.
var tree = new RBTreeList();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2This 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 RBTreeList();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.search(0); //8
tree.search(0, tree.maximum()); //undefinedIf 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 RBTreeList();
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); //2In this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var tree = new RBTreeList();
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); //itemAThis 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 RBTreeList();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.minimum(); //8
tree.minimum(tree.maximum()); //2This 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 RBTreeList();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.maximum(); //2
tree.maximum(tree.minimum()); //8This 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 RBTreeList();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.successor(tree.minimum()); //2
tree.successor(tree.maximum()); //nullThis 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 RBTreeList();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.successor(tree.maximum()); //8
tree.successor(tree.minimum()); //nullThis method delete the node from the tree.
var tree = new RBTreeList();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.deleteNode(tree.maximum()); //tree contains 2This 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 RBTreeList();
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()); // falseIf 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 RBTreeList();
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); //trueIn this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var tree = new RBTreeList();
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); //trueThis 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 RBTreeList();
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); //trueThis method returns the size of the tree so the number of nodes stored.
var tree = new RBTreeList();
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.getSize(); //3This method returns a clone of the tree. The items inside the node are cloned only if there's a method clone() to invoke, otherwise they will be shared with the old tree. This problem there is not if items are not object.
var tree = new RBTreeList();
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 clone = tree.clone(); // clone contains 8, 2, 7This method returns a clone of the treecontaining only one copy of the same node. The items of the nodes are cloned only if there's a method cloneDistinct() to invoke or at least a method clone(), otherwise they will be shared with the old tree. This problem there is not if items are not object.
var tree = new RBTreeList();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(1, 2); //tree contains 8, 2, 2
tree.insert(2, 7); //tree contains 8, 2, 2, 7
tree.insert(3, 7); //tree contains 8, 2, 2, 7, 7
tree.insert(3, 9); //tree contains 8, 2, 2, 7, 7, 9
var clone = tree.cloneDistinct(); //clone contains 8, 2, 7, 7, 9m: the number of distinct elements stored in the tree. The time required depends strongly from the number of nodes duplicated. If the number of nodes duplicated is very high, then m tend to be near log n (when the tree contains only one distinct node) so complexity will be O(n·log n). If the number of nodes duplicated is very low, then m tend to be near n (when the tree doesn't contain any duplicated nodes) so complexity will be O(n2).
This method returns an array that contains the items of the tree.
var tree = new RBTreeList();
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.toArray(); //[8, 2, 7]This method empty the tree.
var tree = new RBTreeList();
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.clear(); //the tree is emptyThis method checks if the tree is empty or not.
var tree = new RBTreeList();
tree.isEmpty(); //true
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.isEmpty(); //falseThis method execute the callback function for each node stored in the tree. The callback must accept the item of the node the iteration is working on. The callback must also return a value to assign to the item.
var tree = new RBTreeList();
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(item) { //this function returns the square for each item
return item * item;
};
tree.execute(callback); //tree contains 64, 4, 49In this example we deal with more complex items.
var tree = new RBTreeList();
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(item) { //this function encapsulate each item into an object
return {x: item, y: item + 2};
};
tree.execute(callback); //tree contains {x: 8, y: 10}, {x: 2, y: 4}, {x: 7, y: 9}This method returns all the items of the nodes that satisfies the condition represented by the callback. The callback must accept the item the iteration is working on.
var tree = new RBTreeList();
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 5); //tree contains 8, 2, 5
var callback = function(item) { //this function checks if the item is lower than 4 or greater than 6
return item < 4 || item > 6;
};
tree.filter(callback); //[8, 2];In this example we deal with more complex items.
var itemA = {parent: null, item: 0};
var itemB = {parent: itemA, item: 1};
var itemC = {parent: itemB, item: 2};
var itemD = {parent: null, item: 3};
var tree = new RBTreeList();
tree.insert(0, itemA); //tree contains itemA
tree.insert(1, itemB); //tree contains itemB
tree.insert(2, itemC); //tree contains itemC
tree.insert(3, itemD); //tree contains itemD
var callback = function(item) { //this function checks if itemA is in the same hierarchy of the item
while(item.parent || item === itemA)
item = item.parent;
return item === itemA;
};
tree.filter(callback); //[itemC, itemB, itemA]This method returns the first position of the item that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method returns the first position where the item is stored. If nothing has been found, the method returns -1.
var tree = new RBTreeList();
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.indexOf(2); //1
tree.indexOf(9); //-1If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item of the node the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.
var tree = new RBTreeList();
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(item) { //this function checks if there is a number lower than 5.
return item < 5;
};
tree.indexOf(null, callback); //1In this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var tree = new RBTreeList();
tree.insert(0, itemA); //tree contains itemA
tree.insert(1, itemB); //tree contains itemA, itemB
var callback = function(item) { //this function checks if there is an item whose parent is itemA
return item.parent === itemA;
};
tree.indexOf(null, callback); //1This method returns the last position of the item that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method returns the last position where the item is stored. If nothing has been found, the method returns -1.
var tree = new RBTreeList();
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.insert(3, 2); //tree contains 8, 2, 7, 2
tree.insert(4, 8); //tree contains 8, 2, 7, 2, 8
tree.insert(5, 6); //tree contains 8, 2, 7, 2, 8, 6
tree.insert(6, 2); //tree contains 8, 2, 7, 2, 8, 6, 2
tree.lastIndexOf(2); //6
tree.lastIndexOf(5); //-1If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item of the node the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.
var tree = new RBTreeList();
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.insert(3, 2); //tree contains 8, 2, 7, 2
tree.insert(4, 8); //tree contains 8, 2, 7, 2, 8
tree.insert(5, 6); //tree contains 8, 2, 7, 2, 8, 6
tree.insert(6, 2); //tree contains 8, 2, 7, 2, 8, 6, 2
var callback = function(item) { //this function checks if there is a number greater than 7.
return item > 7;
};
tree.lastIndexOf(null, callback); //4In this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var tree = new RBTreeList();
tree.insert(0, itemA); //tree contains itemA
tree.insert(1, itemB); //tree contains itemA, itemB
tree.insert(2, itemB); //tree contains itemA, itemB, itemB
var callback = function(item) { //this function checks if there is an item whose parent is itemA
return item.parent === itemA;
};
tree.lastIndexOf(null, callback); //2This method returns all the positions of the items that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method returns all the positions where the item is stored.
var tree = new RBTreeList();
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.insert(3, 2); //tree contains 8, 2, 7, 2
tree.insert(4, 8); //tree contains 8, 2, 7, 2, 8
tree.insert(5, 6); //tree contains 8, 2, 7, 2, 8, 6
tree.insert(6, 2); //tree contains 8, 2, 7, 2, 8, 6, 2
tree.allIndexesOf(2); //[1, 3, 6]
tree.allIndexesOf(5); //[]If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item of the node the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.
var tree = new RBTreeList();
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.insert(3, 2); //tree contains 8, 2, 7, 2
tree.insert(4, 8); //tree contains 8, 2, 7, 2, 8
tree.insert(5, 6); //tree contains 8, 2, 7, 2, 8, 6
tree.insert(6, 2); //tree contains 8, 2, 7, 2, 8, 6, 2
var callback = function(item) { //this function checks if there is a number lower than 5.
return item < 7;
};
tree.allIndexesOf(null, callback); //[1, 3, 5, 6]In this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var tree = new RBTreeList();
tree.insert(0, itemA); //tree contains itemA
tree.insert(1, itemB); //tree contains itemA, itemB
tree.insert(2, itemB); //tree contains itemA, itemB, itemB
var callback = function(item) { //this function checks if there is an item whose parent is itemA
return item.parent === itemA;
};
tree.allIndexesOf(null, callback); //[1, 2]This method returns the item at position index of the tree.
var tree = new RBTreeList();
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.getItem(0); //8
tree.getItem(1); //2