javascript - Javascript：需要一个像样的红黑树实现

Question

我在哪里可以找到一个可以使用的？或者就此而言，如果你知道的话，一个很好的“标准”数据结构集合？

Answer 1

我用 javascript 写了一个红黑树，可以在这里找到：https ://github.com/vadimg/js_bintrees或bintrees在 npm 中。与其他实现不同，它具有单元测试。

Answer 2

这个图书馆有红黑树

Answer 3

快速检查一下 Interwebs，发现 Kevin Lindsey 提供了一个现成的实现（向下滚动到红黑树）：

KevLinDev - 实用程序

不幸的是，我不知道有哪个网站拥有现成的复杂数据结构的存储库。

我猜它们有点少见，因为人们很少使用 JavaScript 来完成需要这些复杂结构的繁重工作……但我可能是错的。

Answer 4

只需添加我自己的实现以供参考。我创建了一个名为的包scl，其中包含许多不同的数据结构。它完全兼容 TypeScript，并且不同集合的 API 基本相同。虽然并不完美，但有一些自动化的单元测试可以确保一切正常。

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);
 

您可以在此处找到存储库，并在此处找到红/黑树实现的源代码。该软件包也在 npm上。