Object buckets.BSTree

Binary search trees keep their elements in sorted order, so that lookup and other operations can use the principle of binary search. In a BST the element in any node is larger than the elements in the node's left sub-tree and smaller than the elements in the node's right sub-tree.

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;
}

Object Summary
Constructor Name and Description
buckets.BSTree(compareFunction)
Creates an empty binary search tree.
Method Summary
Method Name and Description
buckets.BSTree.add(element)
Inserts the specified element into the tree if it's not already present.
buckets.BSTree.clear()
Removes all the elements from the tree.
buckets.BSTree.contains(element)
Returns true if the tree contains the specified element.
buckets.BSTree.equals(other)
Returns true if the tree is equal to another tree.
buckets.BSTree.forEach(callback)
Executes the provided function once per element present in the tree in in-order.
buckets.BSTree.height()
Returns the height of the tree.
buckets.BSTree.inorderTraversal(callback)
Executes the provided function once per element present in the tree in in-order.
buckets.BSTree.isEmpty()
Returns true if the tree contains no elements.
buckets.BSTree.levelTraversal(callback)
Executes the provided function once per element present in the tree in level-order.
buckets.BSTree.maximum()
Returns the maximum element of the tree.
buckets.BSTree.minimum()
Returns the minimum element of the tree.
buckets.BSTree.postorderTraversal(callback)
Executes the provided function once per element present in the tree in post-order.
buckets.BSTree.preorderTraversal(callback)
Executes the provided function once per element present in the tree in pre-order.
buckets.BSTree.remove(element)
Removes the specified element from the tree.
buckets.BSTree.size()
Returns the number of elements in the tree.
buckets.BSTree.toArray()
Returns an array containing all the elements in the tree in in-order.
Object 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
<static> {boolean} buckets.BSTree.add(element)
Inserts the specified element into the tree if it's not already present.
Parameters:
{Object} element
The element to insert.
Returns:
{boolean} True if the tree didn't already contain the element.
<static> buckets.BSTree.clear()
Removes all the elements from the tree.
<static> {boolean} buckets.BSTree.contains(element)
Returns true if the tree contains the specified element.
Parameters:
{Object} element
Element to search for.
Returns:
{boolean} True if the tree contains the element, false otherwise.
<static> {boolean} buckets.BSTree.equals(other)
Returns true if the tree is equal to another tree. Two trees are equal if they have the same elements.
Parameters:
{buckets.BSTree} other
The other tree.
Returns:
{boolean} True if the tree is equal to the given tree.
<static> buckets.BSTree.forEach(callback)
Executes the provided function once per element present in the tree in in-order. Equivalent to inorderTraversal.
Parameters:
{function(Object):*} callback
Function to execute, it's invoked with an element argument. To break the iteration you can optionally return false in the callback.
<static> {number} buckets.BSTree.height()
Returns the height of the tree.
Returns:
{number} The height of the tree or -1 if it's empty.
<static> buckets.BSTree.inorderTraversal(callback)
Executes the provided function once per element present in the tree in in-order.
Parameters:
{function(Object):*} callback
Function to execute, invoked with an element as argument. To break the iteration you can optionally return false in the callback.
<static> {boolean} buckets.BSTree.isEmpty()
Returns true if the tree contains no elements.
Returns:
{boolean} True if the tree contains no elements.
<static> buckets.BSTree.levelTraversal(callback)
Executes the provided function once per element present in the tree in level-order.
Parameters:
{function(Object):*} callback
Function to execute, invoked with an element as argument. To break the iteration you can optionally return false in the callback.
<static> {*} buckets.BSTree.maximum()
Returns the maximum element of the tree.
Returns:
{*} The maximum element of the tree or undefined if the tree is empty.
<static> {*} buckets.BSTree.minimum()
Returns the minimum element of the tree.
Returns:
{*} The minimum element of the tree or undefined if the tree is empty.
<static> buckets.BSTree.postorderTraversal(callback)
Executes the provided function once per element present in the tree in post-order.
Parameters:
{function(Object):*} callback
Function to execute, invoked with an element as argument. To break the iteration you can optionally return false in the callback.
<static> buckets.BSTree.preorderTraversal(callback)
Executes the provided function once per element present in the tree in pre-order.
Parameters:
{function(Object):*} callback
Function to execute, invoked with an element as argument. To break the iteration you can optionally return false in the callback.
<static> {boolean} buckets.BSTree.remove(element)
Removes the specified element from the tree.
Parameters:
element
Returns:
{boolean} True if the tree contained the specified element.
<static> {number} buckets.BSTree.size()
Returns the number of elements in the tree.
Returns:
{number} The number of elements in the tree.
<static> {Array} buckets.BSTree.toArray()
Returns an array containing all the elements in the tree in in-order.
Returns:
{Array} An array containing all the elements in the tree in in-order.