Sign Up for Free

RunKit +

Try any Node.js package right in your browser

This is a playground to test code. It runs a full Node.js environment and already has all of npm’s 1,000,000+ packages pre-installed, including functional-red-black-tree2 with all npm packages installed. Try it out:

var functionalRedBlackTree2 = require("functional-red-black-tree2")

This service is provided by RunKit and is not affiliated with npm, Inc or the package authors.

functional-red-black-tree2 v1.1.0

A fully persistent balanced binary search tree. Typed version

functional-red-black-tree2

A fully persistent red-black tree rewritten in 100% TypeScript. Works both in node.js and in the browser via browserify.

Functional (or fully persistent) data structures allow for non-destructive updates. So if you insert an element into the tree, it returns a new tree with the inserted element rather than destructively updating the existing tree in place. Doing this requires using extra memory, and if one were naive it could cost as much as reallocating the entire tree. Instead, this data structure saves some memory by recycling references to previously allocated subtrees. This requires using only O(log(n)) additional memory per update instead of a full O(n) copy.

Some advantages of this is that it is possible to apply insertions and removals to the tree while still iterating over previous versions of the tree. Functional and persistent data structures can also be useful in many geometric algorithms like point location within triangulations or ray queries, and can be used to analyze the history of executing various algorithms. This added power though comes at a cost, since it is generally a bit slower to use a functional data structure than an imperative version. However, if your application needs this behavior then you may consider using this module.

Install

npm install functional-red-black-tree2

Example

Here is an example of some basic usage:

//Load the library
import {createRBTree as makeTree} from '../rbtree';

//Create a tree
var tree1 = createTree();

//Insert some items into the tree
var tree2 = tree1.insert(1, "foo");
var tree3 = tree2.insert(2, "bar");

//Remove something
var tree4 = tree3.remove(1);

API

Tree API reference

Tree Iterator API reference

Globals

Fork

This repo is a fork of the functional-red-black-tree repository;

The idea is to provide the same functionality, but well-typed.

I did not change any logic with a few exceptions I can count by fingers on my one hand.

Version History

1.0.1 - Relese functional-red-black-tree2 (typed red-black-tree version) 1.1.0 - Updated documentation, version history. Linter added.

RunKit is a free, in-browser JavaScript dev environment for prototyping Node.js code, with every npm package installed. Sign up to share your code.
Sign Up for Free