在哪些编程语言中，使用红黑树而不是哈希表实现关联数组？

Question

在哪些编程语言中，使用红黑树而不是哈希表实现关联数组？

3

在维基百科中：http://en.wikipedia.org/wiki/Red-black_tree#Applications_and_related_data_structures 红黑树是一种自平衡的二叉搜索树，是计算机科学中使用的一种数据结构，通常用于实现关联数组。

有人知道使用红黑树实现关联数组的编程语言吗？

- Howard

3

随便说一句：并不是所有语言都保证容器的实现方法；其中一些只保证运行时。 - San Jacinto

5个回答

3

C++中的std::map通常被实现为红黑树，是基本的关联数组。另一个（新的）是std::unordered_map，实际上是一个哈希表。

- Klaim

2

C# 中的 SortedDictionary 是使用红黑树实现的，而 Dictionary 使用哈希表实现，SortedList 基本上是一个带有二分查找的键值对列表。

- digEmAll

1

我不知道它是否是红黑树，但Haskell的Data.Map是一棵平衡二叉树：

Map的实现基于大小平衡二叉树（或有界平衡树），如下所述：

Stephen Adams，“高效集合：一个平衡的行为”，《函数编程杂志》3（4）：553-562，1993年10月，http://www.swiss.ai.mit.edu/~adams/BB/。

J. Nievergelt和E.M. Reingold，“有界平衡二叉搜索树”，SIAM计算机杂志2（1），1973年3月。

Ocaml 在哈希表的基础上拥有映射类型和二叉树。

- user395760

该用户已经死亡。 - user13831085

1

Scala的scala.collection.immutable.TreeMap是使用红黑树实现的。

- missingfaktor

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mohsen · Accepted Answer

java.util.TreeMap 是 Java 中红黑树的一种实现。