Implementation of binary search trees and red black trees
npm install bin-treesThis is an implementation of BST and RBT using the theory explained in
Introduction to Algorithms relative to this structures. This first version
of the package only support numeric values for tree nodes, in future releases
this can be changed and object as values can be used ;)
``js
const { createRBT } = require('bin-trees');
const newRBT = createRBT();
newRBT.insert(2);
newRBT.insert([23, -1, 4]); // the tree now has 2,23,-1,4
newRBT.contain(2); // true
newRBT.find(2); // Node Structure with 2 as key value
newRBT.remove(2).insert(10);
newRBT.contain(10); // true
newRBT.contain(2); // false
newRBT.contain(2, 10); // false,only true if the tree contain all values
newRBT.max(); // 23
newRBT.min(); // -1
`
The module exposes as main functions createBST for binary search treescreateRBT
creation and for red black trees as well, regardless of the type of
tree created they have the same API.
`js
const { createRBT } = require('bin-trees');
// create empty tree
const emptyTree = createRBT();
// init tree with some values
const treeWithValues = createRBT(3, 2, 14);
// values can be specified using array
const anotherTree = createRBT([3, 2, 5]);
// array and values can be mixed on tree creation
const newTree = createRBT(1, [4, 5], 2, 0);
`
`js
const newTree = createRBT(4, 3, 6, 10);
newTree.insert(5); // new value inserted
newTree.insert(2, 4, 8); // inserting more than one value
newTree.insert([1, 9]); // inserting more than one value using arrays
newTree.insert(11);
newTree.insert(11); // the 11 value is just inserted one time so the tree remain unchanged
newTree.insert(20, [21, 23], 22); // here arrays and value can be missed as well
newTree
.insert([12, 13])
.insert(14)
.insert(15, 16); // insert call can be chained
`
`js
const newTree = createRBT(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
newTree.remove(3); // 3 value remove from the tree;
newTree.remove(100); // nothing occur the tree remain without any change
newTree.remove(2, 4, 5); // removing various elements in one single call
newTree.remove([7, 8]); // removing various elements using array as argument
newTree
.remove(9)
.remove(10)
.insert(11); // remove call can be chained
`
Sometimes when a search is did against the tree we receive as result a node and
to get the node value we must call the getValue function to esxtract correctlycontain
the value.Search in the tree can be done using the following functions,find,the first return a boolean to tell if the tree contain he valueundefined
and the latter return the node with the value specified or if the
tree not contain the value, if any of this functions is called without any
argument then and error is throw.Examples:
`js
const newTree = createBST(1, 3, 5, 7, 9, 2, 4, 6, 8, 10);
// asking if the value are in the tree
newTree.contain(3); // true
newTree.contain(100); // false
// using contain with several values only return true if all values are in the tree
newTree.contain(3, 5, 7); // true
newTree.contain(1, 2, 3, 100); // false
// retrieving nodes,check the use of getValue function
newTree.find(3).getValue(); // 3
newTree.find(100); // undefined;
//retrieving various nodes in one single call
newTree.find(1, 2, 3); // [Node(1),Node(2),Node(3)]
newTree.find(1, 35); // [Node(1)] not present values are ignored
newTree.find([4, 5]); // [Node(4),Node(5)]
newTree.find(1, [2, 3], 4, [10], 25); // [Node(1),Node(2),Node(3),Node(4)]
`
We can know at any time the node with the max value in the tree or the node that
contain the min value,if the node it not the desired result then we can know
only the maximum or minimum value
`js
const newRBT = createRBT(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
newRBT.max(); // Node 10
newRBT.min(); // Node 1
console.log(newRBT.maxValue()); // print 10
console.log(newRBT.minValue()); // print 1
`
Every tree has a function iterator that can be used to build a iterator from
the tree, when this new iterator is consumed the tree values are returned in
order
`js
const newTree = createRBT(1, 2, 3);
const iterator = newTree.iterator();
console.log(iterator.next()); // {value: 1,done: false};
console.log(iterator.next()); // {value: 2,done: false};
console.log(iterator.next()); // {value: 3,done: false};
console.log(iterator.next()); // {value: undefined,done: true};
// if we call next again when the iterator has finished the same object is returned
console.log(iterator.next()); // {value: undefined,done: true};
`
The tree also implement the especial Symbol.iterator so it can be used with any of the standard consumer that used this symbol
`js
const newTree = createRBT(1,2,3);
// the following for print the tree values in order
for(let value of newTree){
console.log(value);
}
`
#### Reduce
We can use reduce over one tree created just like we do with standard arrays:
`js
const newTree = createRBT(1,2,3,4,5);
const sum = (acc,val) => acc + val;
const product = (acc,val) => acc * val;
const treeTotal = newTree.reduce(sum);
const treeFactorial = newTree.reduce(product);
console.log(treeTotal); // 15
console.log(treeFactorial); // 120
`
#### Filter
The filter function is also available, this function is similar to the filter function of the arrays with the difference that a new tree is not created after the filtering process but the existing tree is modified:
`js``
const newTree = createRBT(4, 10, 3, 11, 2, 6, 1, 9);
newTree.filter(v => v % 2 === 0 && v % 3 === 0); // after this the tree only has the value 6
newTree.filter(v => v === 1); // now the tree is empty