Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Javascript implementation of binary search trees
branch: master

This branch is 16 commits behind vadimg:master

Fetching latest commit…

Cannot retrieve the latest commit at this time

Failed to load latest commit information.
dist
examples
lib
test
.gitignore
.travis.yml
LICENSE
Makefile
README.md
index.js
package.json

README.md

Binary Trees Build Status

This package provides Binary and Red-Black Search Trees written in Javascript. It is released under the MIT License.

Binary Search Trees are a good way to store data in sorted order. A Red-Black tree is a variation of a Binary Tree that balances itself.

Algorithms were taken from Julienne Walker: http://eternallyconfuzzled.com/jsw_home.aspx

Trees

  • BinTree - Binary Search Tree
  • RBTree - Red-Black Tree

Quickstart

node.js:

npm install bintrees
var Tree = require('bintrees').RBTree;

var tree = new RBTree(function(a, b) { return a - b; });

tree.insert(2);
tree.insert(-3);

see examples/node.js for more info

In the browser:

<script src="/path/to/rbtree.js"></script>
<script>
    var tree = new RBTree(function(a, b) { return a - b });
    tree.insert(0);
    tree.insert(1);
</script>

see examples/client.html for more info

Constructor

Requires 1 argument: a comparator function f(a,b) which returns:

  • 0 if a == b
  • >0 if a > b
  • <0 if a < b

Methods

  • insert(item)
  • remove(item)
  • clear()
  • find(item)
  • min()
  • max()
  • each(f)
  • reach(f)
  • iterator()

See the comments inside the lib directory for more info.

Iterators

tree.iterator() will return a null-iterator. On a null iterator,

  • next() will return the first element in the tree
  • prev() will return the last element in the tree

Otherwise,

  • next() will return the next element
  • prev() will return the previous element

When iteration reaches the end, the iterator becomes a null-iterator again.

Forward iteration example:

var it=tree.iterator(), item;
while((item = it.next()) !== null) {
    // do stuff with item
}

If you are iterating forward through the tree, you can always call prev() to go back, and vice versa.

Something went wrong with that request. Please try again.