CODEWITHSUNDEEP
javascriptimplementationred-black-tree
Hamster
Hamster

Reputation: 3132

Javascript: Need a decent red black tree implementation

Where can I find one ready for use? Or for that matter, a good collection of "standard" data structures, if you know of any?

Upvotes: 9

Views: 7782

Answers (5)

Zilong Yao
Zilong Yao

Reputation: 74

A javascript standard data structure library with reference to C++ STL, the full name is javascript standard data structure library

github link: https://github.com/ZLY201/js-sdsl

npm link: https://npmjs.com/js-sdsl

Contains various data structures such as Set, Map and hash table implemented using RB-tree, with extremely complete unit tests and performance tests and complete api documentation

It supports CommonJS and ES modules, and supports the introduction of browser script tags. It is written in typescript and has rigorous type inference, making development more efficient.

Upvotes: 1

samvv
samvv

Reputation: 2134

Just adding my own implementation for reference. I've created a package called scl that contains many different data structures. It's fully TypeScript-compatible and the API of different collections is largely the same. Though not perfect, there are some automated unit tests to make sure things keep working.

import { RBTreeIndex } from "scl"

interface Person {
  name: string;
  email: string;
  age: number;
}

const people = new RBTreeIndex<Person, number>([
  {
    name: 'Bob',
    email: '[email protected]',
    age: 45,
  },
  {
    name: 'Fred',
    email: '[email protected]',
    age: 33,
  },
  {
    name: 'Lisa',
    email: '[email protected]',
    age: 37,
  }
]);

// Lisa is the oldest person who is at the very most 40 years old.
const lisa = people.getGreatestLowerBound(40);

// Bob is the youngest person older than Lisa
const bob = lisa.next();

// No one is older than Bob
assert(bob.next() === null);

You can find the repository here and the source code of the Red/Black tree implementation here. The package is also on npm over here.

Upvotes: 0

vadimg
vadimg

Reputation: 592

I wrote a red-black tree in javascript, available here: https://github.com/vadimg/js_bintrees or as bintrees in npm. Unlike the other implementations, it has unit tests.

Upvotes: 12

Thomas
Thomas

Reputation: 81

This library has red-black trees

Upvotes: 2

Justin Niessner
Justin Niessner

Reputation: 245429

A quick check o' the Interwebs turned up a ready-to-use implementation from Kevin Lindsey (scroll down to Red-Black Trees):

KevLinDev - Utilities

Unfortunately I don't know of a site that has a repository of ready made complex data structures.

I'm guessing they're a tad rare since people rarely use JavaScript for the kind of heavy lifting that would necessitate those kinds of complex structures...but I could be wrong.

Upvotes: 1

Related Questions