Red-Black Tree
Wikipedia entry for Red-Black Trees
RBTree API
tree = new RBTree(cmp)
cmp is a funtion is a function to compare your keys to determine ordering.
The function will take two of your key type (whatever that will be) and
return -1, 0, xor 1. For cmp(a,b), it returns -1 if a < b, 0
if a == b and 1 if a > b.
tree.nelts
Number of entries in tree.
tree.put(key, value)
Insert key:value pair. It will over-write a pre-existed entry for key.
value = tree.get(key)
Warning: value is undefined if the key was not found. However, you could
have inserted undefined as the value of a key:value pair. Try not to do
that as it lessens the effectivity of this method.
removed = tree.delete(key)
Returns a boolean; true if deleted, false otherwise.
RBTree Criteria
- All nodes are either RED or BLACK
- The root node is BLACK
- All leaves (nulls) are considered BLACK
- Both children of RED nodes must be BLACK
- Every path from a node to the leaves (inclusive) have the same number of BLACK nodes.
Running Tests and Test-coverage
To run tests: npm test
To run test coverage:
npm run-script test-cov
open jscov.html