红黑树和多图

在许多编译器中，像Set,Map和Multimap这样的标准数据结构在后面使用红黑树，而multimap存储多个和重复的密钥。红黑树和多图

我有一个低于报价的问题：

“独特的红黑树商店键和结合只是一个DataValue到每个键”

是上述声明真实？
如果这是真的，我们如何使用红黑树实现multimap（正如C++ STL所做的那样）？

2012-11-23 deepmax

你看看Wintellect的Power Collections http://powercollections.codeplex.com/它包括MultiDictionary，OrderedMultiDictionary和一个在OrderedMultiDictionary中使用的内部RedBlack类。顺便说一下.Net的SortedDictionary是使用红黑树（SortedSet）实现的。您可以在这里找到源代码http://referencesource.microsoft.com/netframework.aspx –

1）不是，不正确。

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

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

重温＃1：从技术上讲，将仍然被映射键来单个值，只是值不会是直接映射的类型。根据你认为的“DataValue”，那么是的，这个陈述是真实的。

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

例如：

 5 
    3  7 
3

来源

2012-11-23 08:12:28 Corbin

但是，在C++中'multimap'可以存储重复的对。例如，如果我插入<1,"First">三次。 'multimap'有三个相同的对。 – deepmax

正是。一个multimap存储一个数据结构，每个节点可以保存多个值。请注意，二叉树主要是关于*键*，而不是*值*。 – Philipp

只是写了一条评论，但yup，Philipp钉了它:)。 – Corbin

你允许在一个节点两侧孩子包含比大于母既不是少，也没有更大的按键。你需要让双方平等，否则你可能会失去平衡 - 由n个相同键组成的树会有高度n。

来源

2012-11-23 08:34:29 tmyklebu

红黑树和多图

回答

相关问题