bintrees

What is bintrees?

The bintrees npm package provides data structures for binary search trees, including Red-Black trees and Splay trees. These structures are useful for efficiently storing and retrieving ordered data.

What are bintrees's main functionalities?

Red-Black Tree

This feature allows you to create and manipulate a Red-Black tree, which is a balanced binary search tree. The code sample demonstrates how to create a Red-Black tree, insert elements, and find an element.

const { RBTree } = require('bintrees');

const tree = new RBTree((a, b) => a - b);
tree.insert(5);
tree.insert(3);
tree.insert(7);
console.log(tree.find(3)); // Output: 3
console.log(tree.size); // Output: 3

Splay Tree

This feature allows you to create and manipulate a Splay tree, which is a self-adjusting binary search tree. The code sample demonstrates how to create a Splay tree, insert elements, and find an element.

const { SplayTree } = require('bintrees');

const tree = new SplayTree((a, b) => a - b);
tree.insert(5);
tree.insert(3);
tree.insert(7);
console.log(tree.find(3)); // Output: 3
console.log(tree.size); // Output: 3

Other packages similar to bintrees

avl

The avl package provides an implementation of AVL trees, which are another type of self-balancing binary search tree. Compared to bintrees, avl focuses specifically on AVL trees, which may offer different performance characteristics depending on the use case.

js-sdsl

The js-sdsl package offers a variety of data structures, including Red-Black trees and other balanced trees. It provides a more comprehensive set of data structures compared to bintrees, which focuses specifically on Red-Black and Splay trees.

functional-red-black-tree

The functional-red-black-tree package provides an immutable Red-Black tree implementation. This package is useful for functional programming paradigms, offering immutability features that bintrees does not provide.

README

Binary Trees

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.