Class buckets.BSTree
A binary search tree is a binary tree in which each internal node stores an element such that the elements stored in the left subtree are less than it and the elements stored in the right subtree are greater.
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 nodes with elements less than the node's element
- The right subtree of a node contains only nodes with 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 of the elements from this tree.
|
|
contains(element)
Returns true if this tree contains the specified element.
|
|
forEach(callback)
Executes the provided function once for each element present in this tree in inorder.
|
|
height()
Returns the height of this tree.
|
|
inorderTraversal(callback)
Executes the provided function once for each element present in this tree in
in-order.
|
|
isEmpty()
Returns true if this tree contains no elements.
|
|
levelTraversal(callback)
Executes the provided function once for each 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 for each element present in this tree in post-order.
|
|
preorderTraversal(callback)
Executes the provided function once for each 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 of 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 for each element present in this tree in inorder.
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 is empty.
inorderTraversal(callback)
Executes the provided function once for each 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.
{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 for each 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.
{*}
maximum()
Returns the maximum element of this tree.
- Returns:
- {*} the maximum element of this tree or undefined if this tree is is empty.
{*}
minimum()
Returns the minimum element of this tree.
- Returns:
- {*} the minimum element of this tree or undefined if this tree is is empty.
postorderTraversal(callback)
Executes the provided function once for each 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 for each 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.
{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.