• Public
  • Public/Protected
  • All

A tree-like data structure that uses node coloring and a few specific rules to provide fast insertion, deletion and lookup of nodes.

You can use trees as an alternative to hashing. Binary search trees have the added bonus that their elements are sorted, so if you add 1, 4, 3, 2 into an red-black tree in that order the elements will be returned as 1, 2, 3, 4.

⚠️ If you don't require the elements to be sorted hashing might be faster.

The following table lists the performance characteristics of the most commonly used methods of a Red/Black tree:

Property name Worst case
add() O(log(n))
clear() O(1)
equalKeys() O(log(n))
delete() O(log(n))
deleteAll() O(log(n))
deleteAt() O(log(n))
size O(1)


Constructing red-black trees and adding elements

You create a new red-black tree by using the new keyword. Use add to insert elements into the tree.

import { RBTreeIndex } from "scl";

const index = new RBTreeIndex();


Alternatively, you can pass any Iterable as the first argument. So the above is equivalent to the following:

const index = new RBTreeIndex([

Choosing the key and determining how to detect duplicates

Deterministic finite automatons are frequently used in computer science to model all kinds of computations. In this example, we store the mapping from one state of the automaton to another. For the sake of this example, we want the transitions to be sorted on the character is accepted. By definition, multiple transitions with the same character are not allowed.

import { ResolveAction, RBTreeIndex } from "scl"

interface DFAState {
  id: string;
  isFinal: boolean;
  nextStates: RBTreeIndex<DFAStateTransition, string>;

interface DFAStateTransition {
  character: string;
  nextState: DFAState;

const nextStates = new RBTreeIndex<DFAStateTransition, string>({
  getKey: transition => transition.character,
  compareKeys: (a, b) => a.charCodeAt(0) < b.charCodeAt(0),
  isEqual: (a, b) => a.nextState.id === b.nextState.id,

const s1: DFAState = {
  id: 1,
  isFinal: false,

Allowing multiple elements with the same key

In this example, we index people based on their age. However, many people may have the same age, so we have to allow duplicate keys in order to remedy this. For the sake of the example, we simply ignore people that have already been added.

interface Person {
  firstName: string;
  email: string;
  age: number;

const index = new RBTreeIndex({
  getKey: person => person.age,
  compareKeys: (a, b) => a < b,
  onDuplicateKeys: ResolveAction.Insert,
  onDuplicateElements: ResolveAction.Ignore,

// OK, will be added to the index
  firstName: 'Bob',
  email: 'thebobman@gmail.com',
  age: 34,

// OK, will return the existing element
const [didAdd, cursor] = index.add({
  firstName: 'Bob',
  email: 'thebobman@gmail.com',
  age: 12,

console.log(`Bob still is ${cursor.value.age}`)

// This will print the following result:
// - Bob (aged 17)
// - Jessie (aged 25)
// - Jack (aged 34)
// - Anna (aged 58)
for (const person of personsSortedByAge) {
  console.log(`- ${person.fullName} (aged ${person.age})`);

Subclassing RBTreeIndex

In the second example, it might become cumbersome to create many of the same type of indices. Therefore, we have made it possible to subclass the red-black tree and initialize it with your own configuration each time a new tree is constructed.

import { isIterable, RBTreeIndexOptions, RBTreeIndex } from "scl";

class DFATransitionMap extends RBTreeIndex<DFAStateTransition, string> {

  constructor(opts: Iterable<DFAStateTransition> | RBTreeIndexOptions<DFAStateTransition, string>) {

    // We want to be able to pass in just a simple Iterable object, so we
    // need to add some extra logic
    if (isIterable(opts)) {
      opts = { elements: opts }

    // Initialize our RBTreeIndex with user-provided options and override
    // some options specific to DFATransitionMap
      getKey: transition => transition.character,
      compareKeys: (a, b) => a.charCodeAt(0) < b.charCodeAt(0),
      isEqual: (a, b) => a.nextState.id === b.nextState.id,



const nextStates = new DFATransitionMap([
  { character: 'a', nextState: s2 }

Type parameters

  • T

    The type of element that will be stored

  • K = T

    The type of key used to index






  • Construct a new red-black tree index by providing a list of elements that should be stored inside the index or a more complex object detailing e.g. how the keys of the elements should be extracted and how to comare individual elements.

    See the examples on the top of this page for more information on how to construct a new index of this type.



    Type parameters

    • T

    • K = T


    Returns RBTreeIndex<T, K>



getKey: (element: T) => K

Type declaration

    • (element: T): K
    • Parameters

      • element: T

      Returns K


isEqual: (a: T, b: T) => boolean

Type declaration

    • (a: T, b: T): boolean
    • Parameters

      • a: T
      • b: T

      Returns boolean


isKeyLessThan: (a: K, b: K) => boolean

Type declaration

    • (a: K, b: K): boolean
    • Parameters

      • a: K
      • b: K

      Returns boolean


onDuplicateElements: ResolveAction


onDuplicateKeys: ResolveAction



  • get size(): number
  • Count the amount of elements in the collection.

    ⚠️ In most cases, this should be an O(1) operation. However, there are cases where this can be an O(n) operation. Therefore, it is recommended to always cache the result in a local variable.

    Returns number



  • [Symbol.iterator](): Generator<T, void, unknown>
  • Returns an object which is able to sift through the values in this collection.

    The order by which the elements are traversed depends on the kind of collection. For unordered collections, the iteration order is unspecified and may even differ between two iterations on the same collection.

    Returns Generator<T, void, unknown>


  • add(element: T, hint?: unknown): AddResult<T>
  • Add a new element to the index. Whether the element is ignored, replaced or whether an error is thrown depends on the value passed to onDuplicateKeys and onDuplicateElements.

    This operation takes O(log(n)) time.

    The function will first attempt to apply onDuplicateElements and if that didn't do anything special it will continue with onDuplicateKeys.

    The return value of the function depends on whether element was added, ignored or replaced:

    • The element was added to the index. The method returns true with a cursor pointing to the newly added element.
    • The element was replaced. The method returns true with a cursor pointing to the location where the element was replaced.
    • The element was ignored. The method returns false with a cursor pointing to the location of the element in the index that forced this element to be ignored.





    • element: T
    • Optional hint: unknown

      A transparent object obtained with RBTreeIndex.getAddHint that can speed up the insertion process.

    Returns AddResult<T>


  • areKeysEqual(a: K, b: K): boolean


  • begin(): null | BSNode<T>


  • clear(): void
  • Remove all elements from this collection, effectively setting the collection to the empty collection.

    Returns void


  • Make a shallow copy of this tree so that the new tree contains the exact same elements but inserting and removing elements will not change the original tree.

    import { RBTreeIndex } from "scl";
    const index = new RBTreeIndex<number>([1, 2, 3]);
    const cloned = index.clone();
    assert(cloned.size === 2);
    assert(index.size === 3);

    This method currently takes O(n.log(n)) time.

    Returns RBTreeIndex<T, K>


  • delete(element: T): boolean


  • deleteAll(element: T): number


  • deleteAt(node: RBNode<T>): void
  • Delete an element from the tree by providing its location in the tree with an RBTreeIndexCursor.

    This method takes O(log(n)) time. It is slightly faster than deleting the element by key due to the fact that a search for the node has already been done.


    • node: RBNode<T>

    Returns void


  • deleteKey(key: K): number


  • end(): null | BSNode<T>


  • equalKeys(key: K): BSNodeRange<T>
  • Get a range of elements that contain the given key. The range may be empty if no elements with the requested key were found.

    const aged32 = personsSortedByAge.equalKeys(32);
    // There are no people who are exactly 32 years old
    assert(aged32.size === 0);
    for (const person of personsSortedByAge.equalKeys(17)) {
      console.log(`${person.firstName} is 17 years old.`);


    • key: K

      The key that should be searched for

    Returns BSNodeRange<T>

    A range of elements that contain the given key


  • findKey(key: K): null | BSNode<T>
  • This method always returns the topmost node that contains the given key, which means that calling next() on the result will always return a node with the same key if there is any.

    This method takes O(log(n)) time.


    • key: K

      The key to search for.

    Returns null | BSNode<T>


  • getAddHint(element: T): unknown


  • getGreatestLowerBound(key: K): null | BSNode<T>


  • getLeastUpperBound(key: K): null | BSNode<T>


  • getNearest(key: K): null | BSNode<T>


  • has(element: T): boolean


  • hasKey(key: K): boolean


  • toRange(): BSNodeRange<T>


  • Property
  • Method
  • Accessor
  • Property
  • Method
  • Inherited property
  • Inherited method

Generated using TypeDoc