JavaScript：需要一个不错的红黑树实现

Question

我该在哪里找到可直接使用的数据结构？如果您知道任何好的“标准”数据结构集合，也请告诉我。

- Hamster

---

为什么需要红黑树，当JavaScript对象字面量可以做同样的事情，并且很可能在C中实现为红黑树呢？（也可以实现为哈希表，其性能特征相似）。 - slebetman

有点严谨地说：红黑树即使在最坏的情况下也保证具有对数行为，但哈希表并不提供这种保证。另一个区别是，红黑树可以被设计成函数式工作，这可能取决于应用程序而有用。 - dyoo

Answer 1

我在JavaScript中编写了一棵红黑树，可以在https://github.com/vadimg/js_bintrees或npm中使用bintrees获得。与其他实现不同的是，它具有单元测试。

- vadimg

Answer 2

这个库有红黑树

- Thomas

Answer 3

在互联网上进行快速检查后，我找到了Kevin Lindsey的现成实现（向下滚动至“Red-Black Trees”）:

KevLinDev - Utilities

不幸的是，我不知道是否有一个网站拥有现成的复杂数据结构仓库。

我猜它们可能有点罕见，因为人们很少使用JavaScript进行那种需要这些复杂结构的重型工作......但我可能错了。

- Justin Niessner

---

我很好奇为什么它们很少见，考虑到Javascript在一般情况下是如此普遍... - Hamster

这个实现其实是 AVL 树，但错误地标为了红黑树！不过时间复杂度仍然是 O(log n)。 - smilingthax

Answer 4

一款基于C++ STL的JavaScript标准数据结构库，全称为JavaScript标准数据结构库。

Github链接：https://github.com/ZLY201/js-sdsl

NPM链接：https://npmjs.com/js-sdsl

包含各种数据结构，如使用RB树实现的Set、Map和哈希表，具有极其完整的单元测试和性能测试以及完整的API文档。

它支持CommonJS和ES模块，并支持引入浏览器脚本标签。它是用TypeScript编写的，具有严格的类型推断，使开发更加高效。

- Zilong Yao

Answer 5

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

import { RBTreeIndex } from "scl"

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

const people = new RBTreeIndex<Person, number>([
  {
    name: 'Bob',
    email: '[e-mail]',
    age: 45,
  },
  {
    name: 'Fred',
    email: '[e-mail]',
    age: 33,
  },
  {
    name: 'Lisa',
    email: '[e-mail]',
    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获取。

- samvv