Functional left-leaning red-black trees in JavaScript
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.


Functional left-leaning red black trees in JavaScript

Danny Yoo (

A JavaScript implementation ported from:


I'm taking the code from Kazu Yamamoto's implementation:

and porting what I need from it to JavaScript.  It's not a complete
port: I don't think I need the height or removeMax/removeMin
implementations, so I haven't yet ported that code over.

The library provides a high-level interface in terms of a Map class,
and a lower-level interface in terms of functions.

Example of Map usage:

    // The following creates a map with the default key comparator
    // that uses string comparison.
    var t = LLRBTree.makeMap();
    t.isEmpty(); // true

    t = t.put("name", "Danny");
    t.isEmpty(); // false

    t.get("name"); // "Danny"
          function() { return "???"; }); // "???"

    t = t.put("email", "");
          function() { return "???"; }); // ""

    t = t.remove("email");
          function() { return "???"; }); // "???"

All operations are functional.


Low level API.

The name 'LLRBTree' is bound as a namespace with the following names:

LLRBTree.EMPTY : llrbtree

    The empty left-leaning red-black tree.

LLRBTree.insert : llrbtree X (X X -> Integer) -> llrbtree

    Insert an element into the llrbtree, according to the provided comparator.

LLRBTree.remove: llrbtree X (X X -> Integer) -> llrbtree

    Remove an element from the llrbtree, according to the provided comparator.

LLRBTree.find: llrbtree X (X X -> Integer) -> (U X undefined)

    Look for an element in the llrbtree.  Returns undefined if we can't find it.

LLRBTree.contains: llrbtree X (X X -> Integer) -> Boolean

    Returns true if the element's in the llrbtree, false otherwise.

LLRBTree.items: llrbtree -> (Arrayof X)

    Returns an array of all the items in the llrbtree.

High level Map API.

The operations are functional, and should allow me to build a nice
functional map abstraction out of the pieces.  I have a sample
implementation of such an associative array in the LLRBTree.makeMap

LLRBTree.makeMap: (Key Key -> number) -> Map

    Returns a Map object, using the key comparator to order the nodes
    in the internal tree.  If the comparator isn't provided, uses a
    default one that compares the keys lexicographically by string

This Map has the following methods:

    put: Key Value -> Map

        Creates a map with the new association.  If there's already a
        key/value binding, it's replaced.

    contains: Key -> Boolean

        Returns true if the key's in the Map, false otherwise.

    get: Key (-> X) -> (U Key X)

        Lookup.  If the key doesn't exist and a failure function
        hasn't been provided, raises an error.

    remove: Key -> Map

        Creates a map without the key/value binding.  If there's no
        key/value binding, the returned tree should be functionally
        the same.

    isEmpty: -> Boolean

        Returns true if the map is empty.

    keys: -> (Arrayof Key)

        Returns all the keys in the map.

    values: -> (Arrayof Value)

        Returns all the values in the map.

    items: -> (Arrayof (Array Key Value))

        Returns all the key/value pairs in the map.

all which do the standard associative array operations.  It also has a
few functions to navigate the tree structure:

    left: -> Map
    right: -> Map
    color: -> (U "R" "B")
    key: -> Key
    val: -> Value