An AVL tree implementation that supports node streams.
npm install avltree
var Tree = require('avltree');
var es = require('event-stream');
var tree = new Tree({
compareWith: function(obja, objb) {
return obja.date - objb.date;
}
});
var events = [
{ event: 'Shays\' Rebellion', date: -5785664400000 },
{ event: 'Declaration of Independence', date: -6106035600000 },
{ event: 'Operation Desert Storm', date: 664099200000 },
{ event: 'Mexican–American War', date: -3847190400000 }
];
var reader = es.readArray(events);
reader.pipe(tree.createWriteStream());
reader.on('end', function() {
console.log(tree.min().event);
// Declaration of Independence
console.log(tree.max().event);
// Operation Desert Storm
});
compareWith
(optional): afunction
that takes two arguments that correspond to tree node values. The return of this function is 0, less than 0, or greater than 0. If the value returned is less than zero, the first argument is less than the second argument. If the value returned is 0, the two arguments are equal. If the value returned is greater than 0, the second argument is greater than the first argument. Defaults to:function(a, b) { return a - b; }
value
(optional): If acompareWith
function is provided, thevalue
property of the optionsObject
will be the value of the root node.
var tree = new Tree({
compareWith: function(a, b) {
return b - a;
},
value: 10
});
// or
var otherTree = new Tree(10);
// or
var stillAnotherTree = new Tree();
Returns a readable stream of the tree's values. Outputs values in sorted order.
min
(optional): The minimum value or starting point of the stream.max
(optional): The maximum value or ending point of the stream.
var tree = new Tree();
[1,2,3,4,5,6,7,8,9,10].forEach(tree.insert, tree);
var read = tree.createReadStream({min: 5, max: 10});
read.on('data', console.log);
// 5
// 6
// ...
// 10
Returns a writeable stream for populating the tree.
var es = require('event-stream');
var tree = new Tree();
var read = es.readArray([1,2,3,4,5]);
read.pipe(tree.createWriteStream());
read.on('end', function() {
console.log(tree.walk());
// [1,2,3,4,5]
});
Returns an Iterator
object that you can call next()
or previous()
on to walk the tree incrementally.
var tree = new Tree();
[1,2,3,4,5,6,7,8,9,10].forEach(tree.insert, tree);
var iterator = tree.createIterator();
console.log(iterator.next());
// 1
console.log(iterator.next());
// 2
console.log(iterator.prev());
// 1
console.log(iterator.prev());
// undefined
var iterator2 = tree.createIterator();
console.log(iterator.prev());
// 10
console.log(iterator.prev());
// 9
console.log(iterator.next());
// 10
Returns the minimum value in the tree.
var tree = new Tree();
[1,2,3,4,5,6,7,8,9,10].forEach(tree.insert, tree);
console.log(tree.min());
// 1
Returns the maximum value in the tree.
var tree = new Tree();
[1,2,3,4,5,6,7,8,9,10].forEach(tree.insert, tree);
console.log(tree.max());
// 10
Walks the tree in order, returning an array of values.
var tree = new Tree();
[1,2,3,4,5,6,7,8,9,10].forEach(tree.insert, tree);
console.log(tree.walk());
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Walks the tree in order, asynchronously, passing an array of values via a callback.
var tree = new Tree();
[1,2,3,4,5,6,7,8,9,10].forEach(tree.insert, tree);
tree.walkAsync(function(err, values) {
console.log(values);
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
});
Removes the given value from the tree if it exists. Returns a boolean
if a removal occurred.
var tree = new Tree();
[1,2,3,4,5,6,7,8,9,10].forEach(tree.insert, tree);
console.log(tree.remove(8));
// true
console.log(tree.walk());
// [1, 2, 3, 4, 5, 6, 7, 9, 10]
console.log(tree.move(400));
// false
Returns a copy of the tree.
var tree = new Tree();
[1,2,3,4,5,6,7,8,9,10].forEach(tree.insert, tree);
var treeClone = tree.clone();
console.log(tree.remove(10));
// true
console.log(treeClone.walk());
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
console.log(tree.walk());
// [1, 2, 3, 4, 5, 6, 7, 8, 9]
Clones the tree asynchronously, passing a new tree via a callback.
var tree = new Tree();
[1,2,3,4,5,6,7,8,9,10].forEach(tree.insert, tree);
tree.cloneAsync(function(err, treeClone) {
console.log(tree.remove(10));
// true
console.log(treeClone.walk());
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
console.log(tree.walk());
// [1, 2, 3, 4, 5, 6, 7, 8, 9]
});