问题标签 [red-black-tree]

我有一个用 c++ 实现的红黑树。它支持 STL 映射的功能。树节点包含键和映射的值。我想为此编写一个迭代器类，但我不知道该怎么做。我应该让它成为Tree 类的内部类吗？谁能给我一些关于如何编写它的指南+一些资源？

谢谢你！！

我需要一组排序的对象，目前正在使用TreeSet. 我的问题是compareTo对象经常会返回0，这意味着这两个对象的顺序保持不变。TreeMap（TreeSet默认情况下使用）然后将它们视为同一个对象，这是不正确的。

我可以使用什么替代品TreeMap？

用例：我有一组可显示的对象。我想按 Y 坐标对它们进行排序，以便它们以正确的顺序呈现。当然，两个对象很可能具有相同的 Y 坐标。

OCaml 标准库有一个很棒的Set实现，它使用一种非常有效的分治算法来计算union两个集合。我相信它从一组中获取整个子树（不仅仅是单个元素）并将它们插入到另一组中，并在必要时重新平衡。

我想知道这是否需要 OCaml 使用的 AVL 树中保存的高度信息，或者这是否也适用于红黑树。例如，与简单地遍历第二棵树并将其元素附加到第一棵树的末尾相比，是否可以更有效地连接一对红黑树？

有没有一种简单的方法可以记住红黑树的旋转方法？

我很想知道使用自平衡树技术存储项目而不是使用哈希表的原因是什么。

我看到哈希表无法维护插入顺序，但我总是可以在顶部使用链表来存储插入顺序序列。

我看到对于少量值，哈希函数会增加成本，但我总是可以将哈希函数与键一起保存以加快查找速度。

我知道哈希表比直接实现红黑树更难实现，但在实际实现中，难道不想多花点功夫吗？

我看到对于哈希表，发生冲突是正常的，但是对于允许将键保存在哈希表本身中的双哈希等开放寻址技术，问题并没有减少到不倾斜的效果对于这样的实现，走向红黑树？

我很好奇我是否完全遗漏了哈希表的一个缺点，它仍然使红黑树在实际应用程序（如文件系统等）中非常可行的数据结构。

在 a 上插入的最坏情况运行时间red-black tree是O(lg n)，如果我in-order walk在树上执行 a，我基本上会访问每个节点，因此打印排序集合的总最坏情况运行时间将是 O(n lg n)

我很好奇，为什么red-black trees不首选排序quick sort（其平均案例运行时间为O(n lg n).

我看到这可能是因为red-black trees没有就地排序，但我不确定，所以也许有人可以提供帮助。

我正在自己写红黑树。但是当我测试涉及要旋转的根的旋转时，它在某种程度上失去了参考。

树结构：

旋转逻辑说：“以 45（根）为顶部，在提升 X（即 40）的方向上旋转”

所以这意味着右旋转，结果应该如下所示：

假设节点 45 是祖父节点，7 是父节点，41 是当前节点。（我知道顺序没有意义但请忽略，这是因为我已经旋转了一次）

代码：

但不知何故，这段代码不起作用。当我测试时：

所以我认为结果实际上是：

谁能给我提示我的轮换代码有什么问题？

在红黑树中，当旋转时，您需要知道谁是特定节点的父节点。但是，该节点仅具有对右子或左子的引用。

我想给一个节点实例变量“父级”，但正是出于这个原因，我认为这样做不值得，而且每次旋转更改父级引用也太复杂了。

所以，我的解决方案是编写 findParent() 方法，使用搜索来查找父级。我想知道是否有其他方法可以找到节点的父节点？

我的解决方案：

样本树：

如果你想找到节点 25 的父节点，你可以传递如下内容：

它返回node50。

我试图澄清一些有关 TreeSet 某些操作的复杂性的事情。在javadoc上它说：

“此实现为基本操作（添加、删除和包含）提供有保证的 log(n) 时间成本。”

到现在为止还挺好。我的问题是 addAll()、removeAll() 等会发生什么。这里 Set 的 javadoc 说：

“如果指定的集合也是一个集合，那么 addAll 操作会有效地修改这个集合，使其值是两个集合的并集。”

它只是解释操作的逻辑结果还是暗示了复杂性？我的意思是，如果这两个集合由例如红黑树表示，那么以某种方式加入树比将一个的每个元素“添加”到另一个要好。

无论如何，有没有办法将两个 TreeSet 组合成一个复杂度为 O(logn) 的树集？

先感谢您。:-)

伙计们，我正在尝试为红黑树实现删除算法，但我在理解该算法的第三行时遇到问题（来自“算法简介”第二版一书）：

1 如果 left[z] = nil[T] or right[z] = nil[T]
2 then y ← z
3 else y ← TREE-SUCCESSOR(z)
4 if left[y] ≠ nil[T]
5 then x ← left[y]
6 else x ← right[y]
7 p[x] ← p[y]
8 if p[y] = nil[T]
9 then root[T] ← x
10 else if y = left[p [y]]
11 then left[p[y]] ← x
12 else right[p[y]] ← x
13 if y 3≠ z
14 then key[z] ← key[y]
15 复制 y 的卫星数据到 z
16 如果 color[y] = BLACK
17 然后 RB-DELETE-FIXUP(T, x)
18 返回 y

首先，这本书中没有任何地方解释了 TREE-SUCCESSOR 应该是什么样子（没有算法），但我找到了这个页面：如果我用 11、2、1、7、5、8 输入这个算法,14,15,4 然后尝试删除 7 它找到前任，但如果我尝试删除 11 它找到后继。那是我无法理解的。为什么有时需要前任，有时需要继任者？做出此决定时考虑了哪些标准？节点的颜色？
谢谢你。

PS我也不太明白第13行写的是什么。这是否意味着如果y有三种颜色（既不是黑色也不是红色）或其他颜色？