mourner / bbtree

Balanced Binary Search Tree experiments

This repo contains several simple balanced binary search tree JavaScript implementations to experiment, benchmark and play with.

• bbtree.js: Andersson tree (based on Arne Andersson's Balanced Search Trees Made Simple paper and Julienne Walker's tutorial)
• bsarray.js: pseudo-BBST internally stored as a simple JS array
• llrb.js: Sedgewick's Left-Leaning Red-Black Tree

Benchmarks contain comparisons with functional-red-black-tree and js_bintrees.

The goal is to create the fastest and at the same time the simplest JS balanced binary search tree library.

Example usage of trees:

// create a tree using a custom compare function
var tree = bbtree(function (a, b) { return a - b; });

// insert items
tree.insert(1, 'foo');
tree.insert(5, {bar: 2});

// find an item
var node = tree.find(3);
console.log(node.key, node.value);

// TODO remove & other methods