rbts

Red-Black Tree in Typescript

A red-black tree is a data structure for sorted storage of key-value pairs. Items are stored in tree nodes and sorted after a criterium (LessOp). Search, insertion, deletion and traversal are performed in $O(\log n)$ time. This implementation has the same interface as JavaScript's built-in type Map, so it can be used as replacement for Map, however iteration is sorted according to the lessOp parameter in the constructor.

The implementation seems to be rather efficient. I had a short stint with profiling. Adding a million entries with a case-insensitive sort using (a, b) => a.toUpperCase() < b.toUpperCase() needed 5 seconds on my MacBook Air 13inch early 2015. About half of that was inside C++ (internal String to uppercase) and the other half in JavaScript, and of that about 7% in the raw insert of the tree. I am no expert but this seems good to me. Have a look at the profiler's output here.

Documentation

Is in the directory docs. (Something went wrong with typedoc's Markdown theme and I had to fix it manually for the moment, and because I am not a robot there might be broken links and other mistakes.)

Example

import { Tree } from 'rbts'
 
interface Person { name: string, age: number }
 
const store = new Tree<string, Person>(
  [
    [ 'bDe7', { name: 'Jane Doe', age: 47 } ],
    [ 'O3lE', { name: 'John Doe', age: 46 } ],
    [ 'fX4z', { name: 'Billy Brown', age: 33 } ],
    [ 'Tuac', { name: 'Vera Brown', age: 30 } ],
    [ '5S0o', { name: 'Zoe Brown', age: 8 } ],
  ], (a, b) => a.toUpperCase() < b.toUpperCase(),
)
 
// tslint:disable: no-console
 
// 30
console.log(store.get('Tuac')!.age)
 
// Zoe Brown
// Jane Doe
// Billy Brown
// John Doe
// Vera Brown
for (const person of store.values())
  console.log(person.name)
 
// true
console.log(store.delete('bDe7'))
 
// false
console.log(store.delete('bDe7'))
 
// false
console.log(store.delete('TUAC'))
 
// 4
console.log(store.size)