c# - 红黑树和多图

Question

在许多编译器中，标准数据结构如Set,Map并Multimap在后面使用红黑树，并且 amultimap存储多个和重复的键。

我对以下报价有疑问：

“红黑树唯一地存储键，每个键只绑定一个 DataValue”

1. 以上说法属实吗？
2. 如果这是真的，我们如何使用红黑树来实现multimap（就像 C++ STL 所做的那样）？

Answer 1

1）不，不是真的。

2）修改单个映射红黑树以将键映射到多个值将是微不足道的。它只需要使用第二个数据结构和映射键-> 集合。

例如，您可以从字符串映射到整数向量，而不是从字符串映射到整数。或字符串到整数的链接列表。或者一个单一映射 RBT 的字符串。很快 ：）。

---

重温#1：从技术上讲，这仍然会将键映射到单个值，只是该值不会是直接映射的类型。根据您认为的“DataValue”，是的，该陈述是正确的。

---

此外，辅助数据结构实际上并不是必需的。它只是简化了遍历。基本上为了适应重复，而不是严格小于/大于父/左和父/右之间的关系，你有一个方面也包括相等。

例如：

      5
   3     7
 3

Answer 2

您允许节点任一侧的子节点包含既不小于也不大于父节点的键。您需要允许两边相等，否则您可能会严重失去平衡 --- 由 n 个相等键组成的树的高度为 n。