多次使用相同键的红黑树:将集合存储在节点中还是将它们存储为多个节点? [英] A red black tree with the same key multiple times: store collections in the nodes or store them as multiple nodes?
问题描述
显然，您可以执行任何一种操作，但是前者更常见.
Apparently you could do either, but the former is more common.
您为什么选择后者?它如何工作?
Why would you choose the latter and how does it work?
我读了这篇文章: http://www.drdobbs.com/cpp/stls-red-black-trees/184410531 ;这让我认为他们做到了.它说:
I read this: http://www.drdobbs.com/cpp/stls-red-black-trees/184410531; which made me think that they did it. It says:
insert_always是一个状态变量，它告诉rb_tree是否允许使用同一键值的多个实例.此变量由构造函数设置，STL使用它来区分set和multiset以及map和multimap. set和map只能出现一次特定键，而multiset和multimap可以多次出现.
insert_always is a status variable that tells rb_tree whether multiple instances of the same key value are allowed. This variable is set by the constructor and is used by the STL to distinguish between set and multiset and between map and multimap. set and map can only have one occurrence of a particular key, whereas multiset and multimap can have multiple occurrences.
尽管现在我认为这并不一定意味着这一点.他们可能仍在使用容器.
Although now i think it doesnt necessarily mean that. They might still be using containers.
我认为所有具有相同键的节点都必须排成一行，因为您要么必须在右侧或左侧存储所有具有相同键的节点.因此，如果在右边存储相等的节点并插入1000个1和1个2，则基本上会有一个链表，这会破坏红黑树的属性.
I'm thinking all the nodes with the same key would have to be in a row, because you either have to store all nodes with the same key on the right side or the left side. So if you store equal nodes to the right and insert 1000 1s and one 2, you'd basically have a linked list, which would ruin the properties of the red black tree.
为什么我在它上找不到太多东西的原因，这只是一个坏主意?
Is the reason why i can't find much on it that it's just a bad idea?
推荐答案
在商店的下方是多个节点:
down side of store as multiple nodes:
-
扩大树的大小，这会使搜索变慢.
expands tree size, which make search slower.
如果要检索密钥K的所有值，则需要M * log(N)时间，其中N是密钥节点总数，M是密钥K的值数目，除非您引入了额外的代码(从而使数据结构变得复杂)，以实现这些值的链接列表. (如果存储集合，则时间复杂度仅需log(N)，实现起来很简单)
if you want to retrieve all values for key K, you need M*log(N) time, where N is number of total nodes, M is number of values for key K, unless you introduce extra code (which complicates the data structure) to implement linked list for these values. (if storing collection, time complexity only take log(N), and it's simple to implement)
删除操作成本更高.使用多节点方法，您需要在每次删除时都删除节点，但是对于集合存储，只需要在删除键K的最后一个值时删除节点K.
more costly to delete. with multi-node method, you'll need to remove node on every delete, but with collection-storage, you only need to remove node K when the last value of key K is deleted.
想不到多节点方法的任何好处.
Can't think of any good side of multi-node method.
这篇关于多次使用相同键的红黑树:将集合存储在节点中还是将它们存储为多个节点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
