红黑树与多层树

Question

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

关于以下引述，我有一个问题：

“红黑树唯一地存储密钥，并将一个DataValue绑定到每个键上”

1. 以上陈述属实吗？
2. 如果是这样的话，我们如何使用红黑树来实现multimap (就像C++ STL那样)？

Answer 1

1)不，不是真的。

2)修改单个映射红色黑树以将键映射到多个值是非常简单的。它只需要使用第二个数据结构和映射键->集合即可。

例如，您可以将字符串映射到int向量，而不是从字符串映射到int和int。或指向ints链接列表的字符串。或者一个字符串到单个映射RBT。例如:)。

重新查看#1:从技术上讲，这仍然是将键映射到单个值，只是值不是直接映射的类型。根据您认为是"DataValue“的内容，是的，该语句是正确的。

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

例如：

      5
   3     7
 3

Answer 2

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