Class RBTree
Defined in: DataStructures.js.
| Constructor Attributes | Constructor Name and Description |
|---|---|
|
RBTree()
Class for managing a red-black tree.
|
| Field Attributes | Field Name and Description |
|---|---|
|
The root of the tree.
|
|
|
The number of items stored in the tree.
|
| Method Attributes | Method Name and Description |
|---|---|
|
allIndexesOf(item, callback)
Returns all the position in which the item has been found in the tree.
|
|
|
clear()
Removes all the items stored in the tree.
|
|
|
clone()
Clones the queue into a new queue.
|
|
|
Clones the tree into a new tree without cloning duplicated items.
|
|
|
contains(key, callback)
Checks if the tree contains a key or a node that satisfy the condition represented by
the callback function.
|
|
|
deleteFixUp(node, parent)
Preserves the properties of the tree after a deletion.
|
|
|
deleteNode(node)
Deletes the node from the tree.
|
|
|
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.
|
|
|
insertFixUp(node)
Preserves the properties of the tree after an insert.
|
|
|
isEmpty()
Checks if the tree is empty.
|
|
|
lastIndexOf(item, callback)
Returns the last position of the item in the tree.
|
|
|
leftRotate(node)
Rotates the node with its right child.
|
|
|
maximum(node)
Gets the item relatives to the maximum key stored in the tree.
|
|
|
minimum(node)
Gets the item relatives to the minimum key stored in the tree.
|
|
|
predecessor(node)
Gets the node with the key previous to the param node key.
|
|
|
rightRotate(node)
Rotates the node with its left child.
|
|
|
search(key, node, callback)
Searches the item relatives to the key and to the nodes that satisfy the condition
represented by the callback function.
|
|
|
successor(node)
Gets the node with the key next to the param node key.
|
|
|
toArray()
Transforms the tree into an array without preserving keys.
|
Field Detail
root
The root of the tree.
size
The number of items stored in the tree.
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}
clear()
Removes all the items stored in the tree.
- Returns:
- {void}
{RBTree}
clone()
Clones the queue into a new queue.
- Returns:
- {RBTree} The tree cloned from this queue.
{RBTree}
cloneDistinct()
Clones the tree into a new tree without cloning duplicated items.
- Returns:
- {RBTree} The tree cloned from this tree.
{boolean}
contains(key, callback)
Checks if the tree contains a key or a node that satisfy the condition represented by the callback function.
This method avoid to search in branches where the key won't be found.
- Parameters:
- key
- {*} The key to find.
- callback Optional, Default: function(node){return(node.key===key);}
- The condition to satisfy. The callback must accept the current node to check.
- Returns:
- {boolean} True if the tree contains the key or a node that satisfy the condition, false otherwise.
{void}
deleteFixUp(node, parent)
Preserves the properties of the tree after a deletion.
- Parameters:
- node
- {RBNode} The node to delete.
- parent
- {RBNode} The parent of the node.
- Returns:
- {void}
{void}
deleteNode(node)
Deletes the node from the tree.
- Parameters:
- node
- {RBNode} The node 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 stored.
- 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}
insertFixUp(node)
Preserves the properties of the tree after an insert.
- Parameters:
- node
- {RBNode} The node to insert.
- 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.
{void}
leftRotate(node)
Rotates the node with its right child.
- Parameters:
- node
- {RBNode} The node to rotate.
- Returns:
- {void}
{RBNode}
maximum(node)
Gets the item relatives to the maximum key stored in the tree.
- Parameters:
- node Optional, Default: root
- {Node} The node from which start the search.
- Returns:
- {RBNode} The node found.
{RBNode}
minimum(node)
Gets the item relatives to the minimum key stored in the tree.
- Parameters:
- node Optional, Default: root
- {Node} The node from which start the search.
- Returns:
- {RBNode} The node found.
{RBNode}
predecessor(node)
Gets the node with the key previous to the param node key.
- Parameters:
- node
- {RBNode} The node of which search the predecessor.
- Returns:
- {RBNode} The node found.
{void}
rightRotate(node)
Rotates the node with its left child.
- Parameters:
- node
- {RBNode} The node to rotate.
- Returns:
- {void}
{*}
search(key, node, callback)
Searches the item relatives to the key and to the nodes 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){return(node.key===key);}
- The condition to satisfy. The callback must accept the current node to check.
- Returns:
- {*} The item found or undefined if there isn't the key in the tree.
{RBNode}
successor(node)
Gets the node with the key next to the param node key.
- Parameters:
- node
- {RBNode} The node of which search the successor.
- Returns:
- {RBNode} The node found.
{Array<*>}
toArray()
Transforms the tree into an array without preserving keys.
- Returns:
- {Array<*>} The array that represents the tree.