Package Exports

rb-binary-search-tree
rb-binary-search-tree/index.js

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (rb-binary-search-tree) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

Overview

An implementation of a Red/Black Binary Search Tree.

Originally created in 2014, this library has been thouroughly tested and battle hardened.

Binary search trees exhibit the following characteristics: Insertion: O(log n) Removal: O(log n) Search: O(log n)

Thanks go to those responsible for this lecture which was supremely helpful: https://youtu.be/hm2GHwyKF1o?si=-WemyU80lZiaae_4

Example Usage:

const BinarySearchTree = require("rb-binary-search-tree");

const bst = new BinarySearchTree();

bst.insert(1, "Apple");
bst.insert(2, "Pear");
bst.insert(3, "Orange");

console.log(bst.find(1));   //Apple
console.log(bst.find(2));   //Pear
console.log(bst.find(3));   //Orange

console.log(bst.length());  //3
console.log(bst.min());     //1
console.log(bst.max());     //3

bst.remove(2);
console.log(bst.find(2)); //null


//To iterate over all entries use either inOrderTraverse() or reverseOrderTraverse()
//To iterate over a subset, use rangeTraverse()
bst.inOrderTraverse(console.log);   //Output:
                                    //1   Apple
                                    //3   Orange

bst.empty();

Methods

This library contains a class with the following methods:

instance.insert(key, data)

Adds an entry to the BST.

instance.remove(key)

Removes an entry from the BST.

instance.find(key)

Returns an entry from the BST.

instance.length()

Returns the number of entries in the BST.

instance.min()

Returns the lowest key value.

instance.max()

Returns the highest key value.

instance.inOrderTraverse(callBack)

Calls callback for every entry in the BST starting from the lowest key value up to the highest.

The arguments key and data shall be passed to the call back function.

instance.reverseOrderTraverse(callBack)

Calls callback for every entry in the BST starting from the highest key value down to the lowest.

The arguments key and data shall be passed to the call back function.

instance.rangeTraverse(from, to, callBack)

Calls callback for every entry in the BST starting from the highest key value down to the lowest.

The arguments key and data shall be passed to the call back function.

empty()

Removes all entries from the BST.