@subspace/red-black-tree

v0.1.3

Published

3 years ago

This library provides advanced implementation of Red-black tree, which is a kind of self-balancing binary search tree for JavaScript

Downloads

0High
0Medium
0Low

red-black tree binary tree search tree self-balancing

Red-Black tree

This library provides advanced implementation of Red-black tree, which is a kind of self-balancing binary search tree for JavaScript.

Source code is written in TypeScript and should run both in Node.js and browsers (although, you will not be able to use disk-based implementation).

Why this project was created

Implementations of Red-black tree that were out there when this project was created had following drawbacks:

most were not written in strict typescript
not focused on performance or memory efficiency
do not allow custom implementation for storing nodes

This library aims to be the most complete and advanced implementation of Red-black tree available for JavaScript ecosystem.

Available features

Implementation provides following basic features one might expect from binary search tree:

node addition (key and value)
node deletion (value using key)
node lookup using key (returns key and value of the closest solution available)
focus on high performance and memory efficiency

Those features share the same mechanics of Red-black tree, but have different implementations on top. Implementations consist of nodes that hold key, value and internal Red-black tree properties (color and children) and node managers that can manipulate those nodes in order to provide basic features above and more.

Node managers and nodes are separate entities, which means you can select one of existing flavors from this library or use interfaces provided and make your own implementation from scratch.

Node managers plug in into tree implementation. There are 2 kinds of trees available: regular synchronous Tree and asynchronous TreeAsync. Asynchronous tree is currently only supported in combination with Disk-based node manager, which means you can have multi-terabytes trees on disk working with this implementation despite only having a small fraction of physical RAM.

Node managers: JavaScript

Supports any data type supported by JavaScript as key and value, there are 3 flavors available in this library that support following key types:

number
string
Uint8Array

Others can be easily written by extending NodeManagerJs class.

Advantages: fast and flexible Disadvantages: not very memory efficient, all nodes are kept in memory as objects all the time

Node managers: Binary Memory

Supports only Uint8Array both for keys and values. The whole tree is allocated in RAM as single continuous array of bytes.

Advantages: very high memory efficiency, especially on large number of keys (node objects are created only when working with tree and are cleaned up right after use) Disadvantages: requires specifying max number of nodes upfront, about 5x slower for keys insertion and about 3.5x slower retrieval comparing to JavaScript node manager

Node managers: Binary Disk

Supports only Uint8Array both for keys and values. The whole tree is only stored on disk, which allows to work with trees that are many times larger than amount of available RAM.

Advantages: supports large trees that don't fit into RAM (node objects are created only when working with tree and are cleaned up right after use) Disadvantages: requires specifying max number of nodes upfront, orders of magnitude slower than Binary Memory node manager (depending on disk performance)

How to install

npm install @subspace/red-black-tree

How to use

You need 2 things: node manager and tree itself (note that different node managers are constructed in a different way).

// Synchronous JavaScript node manager
import {NodeManagerJsString, Tree} from "@subspace/red-black-tree";

const nodeManager = new NodeManagerJsString<string>();
const tree = new Tree(nodeManager);
tree.addNode('string key1', 'string value');
console.log(tree.getClosestNode('string key1'));
tree.removeNode('string key1');

// Asynchronous JavaScript node manager
import {NodeManagerBinaryDisk, TreeAsync} from "@subspace/red-black-tree";

const nodeManager = await NodeManagerBinaryDisk.create('/path/to/file.bin', 300, 2, 1);
const tree = new TreeAsync(nodeManager);
await tree.addNode(Uint8Array.of(0, 1), Uint8Array.of(1));
console.log(await tree.getClosestNode(Uint8Array.of(0, 1)));
await tree.removeNode(Uint8Array.of(0, 1));
await nodeManager.close();

API: For out of the box use

redBlackTree.Tree<K, V>(nodeManager: INodeManager<K, V>)

Constructor, creates a new tree, K and V are key and value data types accordingly.

redBlackTree.Tree.addNode(key: K, value: V): void

Add a new node to the tree.

redBlackTree.Tree.removeNode(key: K): void

Remove node from the tree.

redBlackTree.Tree.getNodeValue(targetKey: K): V | null

Get the node value by target key, null if key if not found.

redBlackTree.Tree.getClosestNode(targetKey: K): [K, V] | null

Get closest node key/value to targetKey (can be exact match or not, please check if needed) or null if not found.