avltree

avltree

An AVL tree implementation that supports node streams.

Install

npm install avltree

Example

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

});

Constructor

Tree(options|value)

options (optional)

• compareWith (optional): a function 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 a compareWith function is provided, the value property of the options Object will be the value of the root node.

value (optional)

var tree = new Tree({
  compareWith: function(a, b) {
    return b - a;
  },
  value: 10
});

// or

var otherTree = new Tree(10);

// or

var stillAnotherTree = new Tree();

Methods

createReadStream(options)

Returns a readable stream of the tree's values. Outputs values in sorted order.

options (optional)

• min (optional): The minimum value or starting point of the stream.
• max (optional): The maximum value or ending point of the stream.

example

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

createWriteStream()

Returns a writeable stream for populating the tree.

example

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]
});

createIterator()

Returns an Iterator object that you can call next() or previous() on to walk the tree incrementally.

example

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

min()

Returns the minimum value in the tree

max()

Returns the maximum value in the tree

walk()

Walks the tree in order, returning an array of values