BST

BST

Binary search tree representation

Constructor

new BST(comparator)

Implements:
Example
const bst = new Collections.BST();
// FOR ALL EXAMPLES BELOW. ASSUME bst IS CLEARED BEFORE EACH EXAMPLE
Parameters:
Name Type Description
comparator function @see Global#defaultComp for examples

Methods

clear() → {undefined}

Implements:
Empties the BST
Returns:
Type
undefined

contains(key) → {boolean}

Implements:
Determines if the BST contains the given key
Example
bst.put(1, 5).put(5, 10);
bst.contains(5); // returns true
bst.contains(67); // returns false
Parameters:
Name Type Description
key * The key to search for
Returns:
True if the BST contains @param key and false otherwise
Type
boolean

getVal(key) → {*|undefined}

Implements:
Finds the value associated with the given key
Example
bst.put(1, 5).put(5, 10);
bst.find(5); // returns 10
bst.find(67); // returns undefined
Parameters:
Name Type Description
key * The key to search for in the BST
Returns:
The value associated with @param key or undefined if not found.
Type
* | undefined

inorder() → {Array}

Gives the inorder traversal of the BST
Returns:
Array of objects representing the BST
Type
Array

keyRange(lower, upper) → {Array}

Returns an array of all keys in the given range
Parameters:
Name Type Description
lower * The lower bound
upper * The upper bound
Returns:
An array containing the keyRange [lower, upper]
Type
Array

keys() → {Array}

Implements:
Gives the keys in the BST
Returns:
The key set
Type
Array

keysGreater(value) → {Array}

Returns all keys greater than the given key in the BST
Parameters:
Name Type Description
value * The value used as the lower bound
Returns:
Array of keys greater than @param key
Type
Array

keysLess(value) → {Array}

Returns all keys less than the given key in the BST
Parameters:
Name Type Description
value * The value used as the upper bound
Returns:
Array of keys less than @param key
Type
Array

max() → {*}

Returns the greatest value in the tree according to it's ordering function
Returns:
The greatest value in the BST
Type
*

min() → {*}

Returns the smallest value in the BST according to it's ordering function
Returns:
The smallest value in the BST
Type
*

put(keyopt, valueopt) → {BST}

Implements:
puts the given key and value into the BST
Example
bst.put("ed", "jones").put("george", "james").put("ed", "kane");
// ed now maps to kane because ed already existed before.
Parameters:
Name Type Attributes Default Description
key * <optional>
 null The key to insert into the BST
value * <optional>
 null The value that is mapped to by @param key
Returns:
The instance that this method was called with
Type
BST

remove(key) → {boolean}

Implements:
Removes the given key and its associated value from the BST
Example
bst.put(1, 5).put(5, 10);
bst.remove(1); // 1 and it's associated value are removed from BST
bst.remove("dog");// this call fails silently as dog never existed in BST
Parameters:
Name Type Description
key * The key to search fo
Returns:
True if the key existed before and false otherwise
Type
boolean

size() → {number}

Implements:
Reports the number of elements in the BST
Returns:
Number of elements in the BST
Type
number

values() → {Array}

Implements:
Gives the values in the BST
Returns:
The value set
Type
Array