nalply/rbts

Typescript red-black tree

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)

rbts's Issues

More iteration tools

• iterate from and to
• pagination
• ...?

Invariant violated

rbts/test.ts

Line 98 in 822038a

isFalse(rbt._invariantViolated(), 'invariant violated')

produces:

AssertionError: invariant violated: expected 'left is smaller (at b with depth 1)' to be false

Minor refinement in test.ts: use ok() and nil()

rbts/test.ts

Lines 12 to 16 in 25e5a34

	const isNilNode = (value: any) =>
	chai.assert(value === Node.nil, 'not a nil Node')
	const isOkNode = (value: any) =>
	chai.assert(value.constructor !== Node || value !== Node.nil,
	'not an ok Node')

use ok() and nil() with isTrue() instead

need to add equality comparator

202 line's key !== node.key is acts like a reference comparison for an Object.
so, It is impossible to process a case where an object of the nature of a record is used as a key.

It would be better to add comparator like equalOp?: (a: K, b: K) => boolean in Tree<K, V> constructor parameter.

/** @internal */_findNode(
  key: K,
  node: Node<K, V> = this._root,
): Node<K, V> {
  while (node.ok && key !== node.key)
//                  ^^^^^^^^^^^^^^^^ --- here is problem
    node = this._less(key, node) ? node._left : node._right
  return node
}

Run and test in the browser environment

Profile

Profile both in Node and in the browser.

Installation fails

rbts/package.json

Line 8 in 589327d

"install": "tsc",

When installing you get tsc: command not found, probably due to the above.
https://docs.npmjs.com/cli/v8/using-npm/scripts#npm-install

deleteNode() throws

rbts/test.ts

Line 272 in 827af6c

rbt.deleteNode(node)

throws:

TypeError: Cannot assign to read only property '_black' of object '[object Object]'

Add repository badges

Following this Code Repository Badges Tutorial...