GitHub - mourner/bbtree: Self-balancing Binary Search Trees in JavaScript (original) (raw)

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 andJulienne 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