- Notifications
You must be signed in to change notification settings - Fork55
B Tree
In computer science, a B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children. Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. It is commonly used in databases and filesystems.
For each node are stored at leastd keys and at most2d keys.
Wikipedia
vartree=newBTree(5);//an empty tree with 5 minimum keys for each node
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.
vartree=newBTree(5);varit=tree.getIterator();for(it.first();!it.isDone();it.next()){varitem=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.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2
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.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.search(0);//8tree.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.
vartree=newBTree(5);varcallback=function(node){//this function checks if there is a number lower than 5.returnnode.item<5;};tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.search(1,null,callback);//2
In this example we deal with more complex items.
varitemA={parent:null; key:0};varitemB={parent:itemA; key:1};vartree=newBTree(5);tree.insert(0,itemA);tree.insert(1,itemB);varcallback=function(item){//this function checks if there is an item whose parent is itemAreturnitem.parent===itemA;};tree.contains(1,null,callback);//itemA
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.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.minimum();//8tree.minimum(tree.maximum());//2
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.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.maximum();//2tree.maximum(tree.minimum());//8
This method returns the minimum key of the tree.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.minimum();//0
This method returns the maximum key of the tree.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.maximum();//1
This method returns the node that's the successor in the tree. If the node correspond with the maximum, null will be returned.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.successor(tree.minimum());//2tree.successor(tree.maximum());//null
This method returns the node that's the predecessor in the tree. If the node correspond with the minimum, null will be returned.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.successor(tree.maximum());//8tree.successor(tree.minimum());//null
This method delete the key from the tree.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.deleteNode(tree.maximum());//tree contains 2
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.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7tree.contains(2);//truetree.contains(5);//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.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7varcallback=function(node){//this function checks if there is a node with a item whose value is lower than 5.returnnode.item<5;};tree.contains(null,callback);//true
In this example we deal with more complex items.
varitemA={parent:null; key:0};varitemB={parent:itemA; key:1};vartree=newBTree(5);tree.insert(0,itemA);//tree contains itemAtree.insert(1,itemB);//tree contains itemA, itemBvarcallback=function(node){//this function checks if there is an item whose parent is itemAreturnnode.item.parent===itemA;};tree.contains(null,callback);//true
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.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7varcallback=function(node){//this function checks if there is a node with a item whose value is lower than 5.returnnode.item===2;};tree.fullContains(callback);//true
This method returns the size of the tree so the number of nodes stored.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7tree.getSize();//3
This method returns a clone of the tree. The items inside the node are cloned only if there's a methodclone() to invoke, otherwise they will be shared with the old tree. This problem there is not if items are not object.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7varclone=tree.clone();// clone contains 8, 2, 7
This 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 methodcloneDistinct() to invoke or at least a methodclone(), otherwise they will be shared with the old tree. This problem there is not if items are not object.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(1,2);//tree contains 8, 2, 2tree.insert(2,7);//tree contains 8, 2, 2, 7tree.insert(3,7);//tree contains 8, 2, 2, 7, 7tree.insert(3,9);//tree contains 8, 2, 2, 7, 7, 9varclone=tree.cloneDistinct();//clone contains 8, 2, 7, 7, 9
m: 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 logn (when the tree contains only one distinct node) so complexity will beO(n·logn). 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 beO(n2).
This method returns an array that contains the items of the tree.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7tree.toArray();//[8, 2, 7]
This method empty the tree.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7tree.clear();//the tree is empty
This method checks if the tree is empty or not.
vartree=newBTree(5);tree.isEmpty();//truetree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7tree.isEmpty();//false
This 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.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7varcallback=function(item){//this function returns the square for each itemreturnitem*item;};tree.execute(callback);//tree contains 64, 4, 49
In this example we deal with more complex items.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7varcallback=function(item){//this function encapsulate each item into an objectreturn{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.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,5);//tree contains 8, 2, 5varcallback=function(item){//this function checks if the item is lower than 4 or greater than 6returnitem<4||item>6;};tree.filter(callback);//[8, 2];
In this example we deal with more complex items.
varitemA={parent:null,item:0};varitemB={parent:itemA,item:1};varitemC={parent:itemB,item:2};varitemD={parent:null,item:3};vartree=newBTree(5);tree.insert(0,itemA);//tree contains itemAtree.insert(1,itemB);//tree contains itemBtree.insert(2,itemC);//tree contains itemCtree.insert(3,itemD);//tree contains itemDvarcallback=function(item){//this function checks if itemA is in the same hierarchy of the itemwhile(item.parent||item===itemA)item=item.parent;returnitem===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.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7tree.indexOf(2);//1tree.indexOf(9);//-1
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.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7varcallback=function(item){//this function checks if there is a number lower than 5.returnitem<5;};tree.indexOf(null,callback);//1
In this example we deal with more complex items.
varitemA={parent:null; key:0};varitemB={parent:itemA; key:1};vartree=newBTree(5);tree.insert(0,itemA);//tree contains itemAtree.insert(1,itemB);//tree contains itemA, itemBvarcallback=function(item){//this function checks if there is an item whose parent is itemAreturnitem.parent===itemA;};tree.indexOf(null,callback);//1
This 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.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7tree.insert(3,2);//tree contains 8, 2, 7, 2tree.insert(4,8);//tree contains 8, 2, 7, 2, 8tree.insert(5,6);//tree contains 8, 2, 7, 2, 8, 6tree.insert(6,2);//tree contains 8, 2, 7, 2, 8, 6, 2tree.lastIndexOf(2);//6tree.lastIndexOf(5);//-1
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.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7tree.insert(3,2);//tree contains 8, 2, 7, 2tree.insert(4,8);//tree contains 8, 2, 7, 2, 8tree.insert(5,6);//tree contains 8, 2, 7, 2, 8, 6tree.insert(6,2);//tree contains 8, 2, 7, 2, 8, 6, 2varcallback=function(item){//this function checks if there is a number greater than 7.returnitem>7;};tree.lastIndexOf(null,callback);//4
In this example we deal with more complex items.
varitemA={parent:null; key:0};varitemB={parent:itemA; key:1};vartree=newBTree(5);tree.insert(0,itemA);//tree contains itemAtree.insert(1,itemB);//tree contains itemA, itemBtree.insert(2,itemB);//tree contains itemA, itemB, itemBvarcallback=function(item){//this function checks if there is an item whose parent is itemAreturnitem.parent===itemA;};tree.lastIndexOf(null,callback);//2
This 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.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7tree.insert(3,2);//tree contains 8, 2, 7, 2tree.insert(4,8);//tree contains 8, 2, 7, 2, 8tree.insert(5,6);//tree contains 8, 2, 7, 2, 8, 6tree.insert(6,2);//tree contains 8, 2, 7, 2, 8, 6, 2tree.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.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7tree.insert(3,2);//tree contains 8, 2, 7, 2tree.insert(4,8);//tree contains 8, 2, 7, 2, 8tree.insert(5,6);//tree contains 8, 2, 7, 2, 8, 6tree.insert(6,2);//tree contains 8, 2, 7, 2, 8, 6, 2varcallback=function(item){//this function checks if there is a number lower than 5.returnitem<7;};tree.allIndexesOf(null,callback);//[1, 3, 5, 6]
In this example we deal with more complex items.
varitemA={parent:null; key:0};varitemB={parent:itemA; key:1};vartree=newBTree(5);tree.insert(0,itemA);//tree contains itemAtree.insert(1,itemB);//tree contains itemA, itemBtree.insert(2,itemB);//tree contains itemA, itemB, itemBvarcallback=function(item){//this function checks if there is an item whose parent is itemAreturnitem.parent===itemA;};tree.allIndexesOf(null,callback);//[1, 2]
This method returns the item at position index of the tree.
vartree=newBTree(5);tree.insert(0,8);//tree contains 8tree.insert(1,2);//tree contains 8, 2tree.insert(2,7);//tree contains 8, 2, 7tree.getItem(0);//8tree.getItem(1);//2