4

显然你可以做任何一个，但前者更常见。

你为什么会选择后者，它是如何工作的？

我读到这个：http ://www.drdobbs.com/cpp/stls-red-black-trees/184410531 ；这让我觉得他们做到了。它说：

insert_always 是一个状态变量，它告诉 rb_tree 是否允许同一键值的多个实例。此变量由构造函数设置，并由 STL 用于区分 set 和 multiset 以及 map 和 multimap。set 和 map 只能出现一次特定键，而 multiset 和 multimap 可以出现多次。

虽然现在我认为这并不一定意味着。他们可能仍在使用容器。

我认为具有相同键的所有节点都必须排成一行，因为您必须将所有具有相同键的节点存储在右侧或左侧。因此，如果您将相等的节点存储在右侧并插入 1000 个 1 和一个 2，那么您基本上会有一个链表，这会破坏红黑树的属性。

为什么我找不到太多关于它的原因是它只是一个坏主意？

4

2 回答 2

2

商店的下侧作为多个节点：

  1. 扩大树的大小，使搜索变慢。

  2. 如果要检索键 K 的所有值，则需要 M*log(N) 时间，其中 N 是总节点数，M 是键 K 的值数，除非您引入额外的代码（这会使数据结构复杂化）为这些值实现链表。（如果存储集合，时间复杂度只取log(N)，实现简单）

  3. 删除成本更高。使用多节点方法，您需要在每次删除时删除节点，但使用集合存储，您只需要在删除键 K 的最后一个值时删除节点 K。

想不出多节点方法有什么好的方面。

于 2012-09-28T07:37:37.733 回答
2

根据定义，二叉搜索树不能包含重复项。如果您使用它们来生成排序列表，则丢弃重复项会产生不正确的结果。当我遇到重复问题时，我正在用 PHP 实现红黑树。我们将使用树进行排序和搜索。我正在考虑向节点数据类型添加一个出现值。当遇到重复时，只需增加出现次数。当遍历树以产生输出时，只需按出现次数重复该值。我想我仍然会有一个有效的 BST 并避免拥有一整串重复值来保留最佳搜索时间。

于 2014-08-13T17:11:59.333 回答