Javascript: Need a decent red black tree implementation

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

---

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.

---

This library has red-black trees

---

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.

---

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: 'thebobman@gmail.com',
    age: 45,
  },
  {
    name: 'Fred',
    email: 'fred@outlook.com',
    age: 33,
  },
  {
    name: 'Lisa',
    email: 'lisa.turner@gmail.com',
    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.

---

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.