Class BTree
Defined in: DataStructures.js.
| Constructor Attributes | Constructor Name and Description |
|---|---|
|
BTree(minimumDegree)
Class for managing a B-Tree.
|
| Field Attributes | Field Name and Description |
|---|---|
|
The root of the tree.
|
|
|
The number of items stored in the tree.
|
|
|
The minimum number of the keys of a node.
|
| Method Attributes | Method Name and Description |
|---|---|
|
allIndexesOf(item, callback)
Returns all the position in which the item has been found in the tree.
|
|
|
augmentChild(node, index)
Augments the number of keys stored in the node preserving the order.
|
|
|
clear()
Removes all the items stored in the tree.
|
|
|
clone()
Clones the tree into a new tree.
|
|
|
Clones the tree into a new tree without cloning duplicated items.
|
|
|
contains(key, callback)
Checks if the tree contains the key.
|
|
|
deleteKey(key)
Deletes the key from the tree.
|
|
|
deleteMax(node, index)
Deletes a node that have the maximum number of keys for node.
|
|
|
deleteNonMin(node, key)
Deletes a node that's a number of keys greater than the minimum for a node.
|
|
|
execute(callback)
Executes the callback function for each item of the tree.
|
|
|
filter(callback)
Returns the items that satisfy the condition determined by the callback.
|
|
|
fullContains(callback)
Checks if the tree contains a node that satisfy the condition represented by the
callback function.
|
|
|
getItem(index)
Returns the item at the position index.
|
|
|
Returns the iterator relative to the aggregate.
|
|
|
getSize()
Returns the size of the tree.
|
|
|
indexOf(item, callback)
Returns the first position of the item in the tree.
|
|
|
insert(key, item)
Inserts the item relatives to the key value in the tree.
|
|
|
insertNonFull(node, key, item)
Inserts the new node in the right position if the node is not full.
|
|
|
isEmpty()
Checks if the tree is empty.
|
|
|
lastIndexOf(item, callback)
Returns the last position of the item in the tree.
|
|
|
maximum()
Gets the item relatives to the maximum key stored in the tree.
|
|
|
Gets the maximum key stored in the tree.
|
|
|
minimum()
Gets the item relatives to the minimum key stored in the tree.
|
|
|
Gets the minimum key stored in the tree.
|
|
|
predecessor(key, node)
Gets the key previous to the param key.
|
|
|
search(key, node, callback)
Searches the item relatives to the key that satisfy the condition represented by the
callback function.
|
|
|
splitChild(node, index)
Splits the child of the node at the position index.
|
|
|
successor(key, node)
Gets the key next to the param node key.
|
|
|
toArray()
Transforms the tree into an array without preserving keys.
|
Class Detail
BTree(minimumDegree)
Class for managing a B-Tree.
- Parameters:
- minimumDegree
- {number} The minimum number of keys of a node.
Field Detail
root
The root of the tree.
size
The number of items stored in the tree.
t
The minimum number of the keys of a node.
Method Detail
{Array}
allIndexesOf(item, callback)
Returns all the position in which the item has been found in the tree.
- Parameters:
- item
- {*} The item to search.
- callback Optional, Default: function(item){return(it===item);}
- The condition to satisfy. The callback must accept the current item to check.
- Returns:
- {Array
} The positions in which the item has been found.
{void}
augmentChild(node, index)
Augments the number of keys stored in the node preserving the order.
- Parameters:
- node
- {BNode} The node to delete.
- index
- {number} The index of the position to augment.
- Returns:
- {void}
{void}
clear()
Removes all the items stored in the tree.
- Returns:
- {void}
{BTree}
clone()
Clones the tree into a new tree.
- Returns:
- {BTree} The tree cloned from this tree.
{BTree}
cloneDistinct()
Clones the tree into a new tree without cloning duplicated items.
- Returns:
- {BTree} The tree cloned from this tree.
{boolean}
contains(key, callback)
Checks if the tree contains the key.
- Parameters:
- key
- {number} The key to find.
- callback Optional, Default: function(node,index){return(node.keys[index]===key);}
- The condition to satisfy. The callback must accept the current node to check and optionally the position of the key.
- Returns:
- {boolean} True if the tree contains the key.
{void}
deleteKey(key)
Deletes the key from the tree.
- Parameters:
- key
- {*} The key to delete.
- Returns:
- {void}
{void}
deleteMax(node, index)
Deletes a node that have the maximum number of keys for node.
- Parameters:
- node
- {BNode} The node to delete.
- index
- {number} The key to delete in the node.
- Returns:
- {void}
{void}
deleteNonMin(node, key)
Deletes a node that's a number of keys greater than the minimum for a node.
- Parameters:
- node
- {BNode} The node to delete.
- key
- {number} The key to delete.
- Returns:
- {void}
{void}
execute(callback)
Executes the callback function for each item of the tree.
This method modifies the tree so if you don't need to modify it you must return the same item of the array.
- Parameters:
- callback
- {function} The function to execute for each item. The function must accept the current item on which execute the function.
- Returns:
- {void}
{Array<*>}
filter(callback)
Returns the items that satisfy the condition determined by the callback.
- Parameters:
- callback
- {function} The function that implements the condition.
- Returns:
- {Array<*>} The array that contains the items that satisfy the condition.
{boolean}
fullContains(callback)
Checks if the tree contains a node that satisfy the condition represented by the callback function.
This method check all the tree avoiding the binary search.
- Parameters:
- callback
- {function} The condition to satisfy. The callback must accept the current node to check.
- Returns:
- {boolean} True if the tree contains the node that satisfy the condition, false otherwise.
{*}
getItem(index)
Returns the item at the position index.
- Parameters:
- index
- {number} The position of the item.
- Returns:
- {*} The item at the position. It's undefined if index isn't in the tree bounds.
{Iterator}
getIterator()
Returns the iterator relative to the aggregate.
- Returns:
- {Iterator} The iterator.
{number}
getSize()
Returns the size of the tree.
- Returns:
- {number} The size of the tree.
{number}
indexOf(item, callback)
Returns the first position of the item in the tree.
- Parameters:
- item
- {*} The item to search.
- callback Optional, Default: function(item){return(it===item);}
- The condition to satisfy. The callback must accept the current item to check.
- Returns:
- {number} The first position of the item.
{void}
insert(key, item)
Inserts the item relatives to the key value in the tree.
- Parameters:
- key
- {number} The key to store.
- item
- {*} The item to store.
- Returns:
- {void}
{void}
insertNonFull(node, key, item)
Inserts the new node in the right position if the node is not full.
- Parameters:
- node
- {BNode} The node from which start to check the insertion.
- key
- {number} The key to store.
- item
- {*} The item to store.
- Returns:
- {void}
{boolean}
isEmpty()
Checks if the tree is empty.
- Returns:
- {boolean} True if the tree is empty, false otherwise.
{number}
lastIndexOf(item, callback)
Returns the last position of the item in the tree.
- Parameters:
- item
- {*} The item to search.
- callback Optional, Default: function(item){return(it===item);}
- The condition to satisfy. The callback must accept the current item to check.
- Returns:
- {number} The last position of the item.
{node}
maximum()
Gets the item relatives to the maximum key stored in the tree.
- Returns:
- {node} The item found.
{number}
maximumKey()
Gets the maximum key stored in the tree.
- Returns:
- {number} The key found.
{number}
minimum()
Gets the item relatives to the minimum key stored in the tree.
- Returns:
- {number} The item found.
{number}
minimumKey()
Gets the minimum key stored in the tree.
- Returns:
- {number} The key found.
{number}
predecessor(key, node)
Gets the key previous to the param key.
- Parameters:
- key
- {number} The key of which search the predecessor.
- node Optional, Default: root
- The node from start the search of the predecessor.
- Returns:
- {number} The key found.
{*}
search(key, node, callback)
Searches the item relatives to the key that satisfy the condition represented by the callback function.
- Parameters:
- key
- {Number} The key to find.
- node Optional, Default: root
- {RBNode} The node from which start the search.
- callback Optional, Default: function(node,index){return(node.keys[index]===key);}
- The condition to satisfy. The callback must accept the current node to check and optionally the position of the key.
- Returns:
- {*} The item found or undefined if there isn't the key in the tree.
{void}
splitChild(node, index)
Splits the child of the node at the position index.
- Parameters:
- node
- {BNode} The parent of the child to split.
- index
- {number} The position of the child to split.
- Returns:
- {void}
{number}
successor(key, node)
Gets the key next to the param node key.
- Parameters:
- key
- {number} The key of which search the successor.
- node Optional, Default: root
- The node from start the search of the successor.
- Returns:
- {number} The key found.
{Array<*>}
toArray()
Transforms the tree into an array without preserving keys.
- Returns:
- {Array<*>} The array that represents the tree.