红黑树和Multimap

Question

在许多编译器中,标准数据结构类似于Set,Map并Multimap在后面使用Red-Black-Trees,并multimap存储多个和重复的键.

我有一个关于以下引用的问题:

"红黑树唯一地存储密钥,并且只为每个密钥绑定一个DataValue"

Answer 1

1)不,不是真的.

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

例如,您可以从字符串映射到int的向量,而不是从字符串映射到int.或者是一个链接的整数列表的字符串.或者是单映射RBT的字符串.所以:).

重温#1:从技术上讲,仍然会将键映射到单个值,只是值不是直接映射的类型.根据您认为的"DataValue",然后是,该语句为真.

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

例如:

      5
   3     7
 3

究竟.multimap在每个节点中存储一个可以容纳多个值的数据结构.请注意,二叉树主要是*键*,而不是*值*. (2认同)
二叉树由其**键**组织。表示多重映射的树中的键是唯一的。但是除了用于查找节点在树中的位置的键之外，每个节点还保存一个与树布局无关的**值**。在映射中，该值是单个变量。在多重映射中，该值是变量列表。您可以将 multimap<int, int> 视为 map<int, list<int>>。 (2认同)

Answer 2

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