Class buckets.BSTree
Formally, a binary search tree is a node-based binary tree data structure which has the following properties:
- The left subtree of a node contains only elements less than the node's element.
- The right subtree of a node contains only elements greater than the node's element.
- Both the left and right subtrees must also be binary search trees.
If the inserted elements are custom objects, a compare function must be provided at construction time, otherwise the <=, === and >= operators are used to compare elements. Example:
function compare(a, b) { if (a is less than b by some ordering criterion) { return -1; } if (a is greater than b by the ordering criterion) { return 1; } // a must be equal to b return 0; }
Defined in: <../buckets.js>.
Constructor Attributes | Constructor Name and Description |
---|---|
buckets.BSTree(compareFunction)
Creates an empty binary search tree.
|
Method Attributes | Method Name and Description |
---|---|
add(element)
Adds the specified element to this tree if it is not already present.
|
|
clear()
Removes all the elements from this tree.
|
|
contains(element)
Returns true if this tree contains the specified element.
|
|
forEach(callback)
Executes the provided function once per element present in this tree in in-order.
|
|
height()
Returns the height of this tree.
|
|
inorderTraversal(callback)
Executes the provided function once per element present in this tree in in-order.
|
|
isEmpty()
Returns true if this tree contains no elements.
|
|
levelTraversal(callback)
Executes the provided function once per element present in this tree in
level-order.
|
|
maximum()
Returns the maximum element of this tree.
|
|
minimum()
Returns the minimum element of this tree.
|
|
postorderTraversal(callback)
Executes the provided function once per element present in this tree in post-order.
|
|
preorderTraversal(callback)
Executes the provided function once per element present in this tree in pre-order.
|
|
remove(element)
Removes the specified element from this tree if it is present.
|
|
size()
Returns the number of elements in this tree.
|
|
toArray()
Returns an array containing all of the elements in this tree in in-order.
|
Class Detail
buckets.BSTree(compareFunction)
Creates an empty binary search tree.
- Parameters:
- {function(Object|Object):number=} compareFunction
- Optional function used to compare two elements. Must return a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.
Method Detail
{boolean}
add(element)
Adds the specified element to this tree if it is not already present.
- Parameters:
- {Object} element
- the element to insert.
- Returns:
- {boolean} true If this tree did not already contain the specified element.
clear()
Removes all the elements from this tree.
{boolean}
contains(element)
Returns true if this tree contains the specified element.
- Parameters:
- {Object} element
- Element to search for.
- Returns:
- {boolean} True if this tree contains the specified element, false otherwise.
forEach(callback)
Executes the provided function once per element present in this tree in in-order.
Equivalent to inorderTraversal.
- Parameters:
- {function(Object):*} callback
- function to execute, it is invoked with one argument: the element value, to break the iteration you can optionally return false.
{number}
height()
Returns the height of this tree.
- Returns:
- {number} The height of this tree or -1 if it's empty.
inorderTraversal(callback)
Executes the provided function once per element present in this tree in in-order.
- Parameters:
- {function(Object):*} callback
- function to execute, it is invoked with one argument: the element value, to break the iteration you can optionally return false inside the calback.
{boolean}
isEmpty()
Returns true if this tree contains no elements.
- Returns:
- {boolean} True if this tree contains no elements.
levelTraversal(callback)
Executes the provided function once per element present in this tree in
level-order.
- Parameters:
- {function(Object):*} callback
- function to execute, it is invoked with one argument: the element value, to break the iteration you can optionally return false inside the calback.
{*}
maximum()
Returns the maximum element of this tree.
- Returns:
- {*} The maximum element of this tree or undefined if this tree it's empty.
{*}
minimum()
Returns the minimum element of this tree.
- Returns:
- {*} The minimum element of this tree or undefined if this tree it' empty.
postorderTraversal(callback)
Executes the provided function once per element present in this tree in post-order.
- Parameters:
- {function(Object):*} callback
- function to execute, it is invoked with one argument: the element value, to break the iteration you can optionally return false.
preorderTraversal(callback)
Executes the provided function once per element present in this tree in pre-order.
- Parameters:
- {function(Object):*} callback
- function to execute, it is invoked with one argument: the element value, to break the iteration you can optionally return false inside the calback.
{boolean}
remove(element)
Removes the specified element from this tree if it is present.
- Parameters:
- element
- Returns:
- {boolean} True if this tree contained the specified element.
{number}
size()
Returns the number of elements in this tree.
- Returns:
- {number} The number of elements in this tree.
{Array}
toArray()
Returns an array containing all of the elements in this tree in in-order.
- Returns:
- {Array} An array containing all of the elements in this tree in in-order.