问题标签 [red-black-tree-insertion]

红黑树-插入-z的叔叔是红色的

为什么节点γ（gamma，最顶层节点）的黑色高度在操作后没有变化？

我知道如何解释为什么 T1 - T4 的黑色高度在操作后是相同的。但对于伽玛，我完全不知道。

有人有想法吗？

明显的区别是，与堆的 O(n) 移除相比，红黑树可以支持 O(logn) 移除。

但是，看起来红黑树的所有操作都更快/等于堆的操作。所以我的问题是，为什么我们会在红黑树上使用堆？在我看来，红黑树可以做任何堆可以做的事情，但更快/相等。

谢谢。

I am implementing a red-black tree. Currently stuck on tree rotations. When I rotate and assign the new left/right children, I crash and burn. The way I have learned to do left or right rotations on a binary tree is like so (in c++):

This works fine for an AVL tree.

Here is the RB-tree. I'll try to post the minimum it takes to reproduce this

From what I know, the tmp->left is a nullptr, thus when I am assigning it to the root->left it is normal to segfault. How do I overcome this and both execute this step and not terminate?

I have searched over SO and other internet corners and have seen that people use this approach and they do not complain of this segfault.

If I do a check if (tmp->right) root->left = tmp->right; then the code is not being executed and I am skipping over a critical algorithm step. With this if statement, I get a tree where some of the nodes point to themselves and it gets really messy.

Sample case

To get this situation, I insert 3(root)->1(go left of 3)->5(go right of 3)->7(go right of 5)->6(go left of 7). A balance must be made at 5->7->6. The logic is to do a Right-Left rotation. At the right rotation, this situation is happening

我正在阅读第三版算法简介（ISBN-10：9780262033848），其中包含在插入红色节点后“修复”红黑树的以下算法。

在第 3 行，它说将 y = 设置为“z 的父母的父母的右孩子”（z 的右叔叔）。我的问题是，如果 z 只是第三个插入并且它是左孩子的左孩子怎么办？是否不需要另一个案例来处理 z 没有右叔叔但其父母是红色左孩子？

我正在用 C++ 实现一棵红黑树，并且在插入后我一直在修复颜色违规。

我的左右旋转似乎工作正常，但树右分支的颜色永远无法正确修复。我想我在我的 fixViolation(Node*n) 方法中涵盖了所有情况，但也许我错了。

我还将感谢有关我的代码的所有其他建议和技巧。pastebin 链接到我的代码

我的代码：

所以我正在查看我发现的一些与我正在为学校工作的项目相关的代码，我发现了一个在返回值之前具有私有的函数实现，我希望有人可以向我解释它的目的和用途。我无法在网上找到任何关于它的信息，可能是因为我不完全确定如何在不被重定向到类定义或基本函数定义中的私有信息的情况下提出问题。

这是关于左倾红黑树的。提前致谢。

我正在实现红黑树，我似乎无法调试调用fixup()函数时发生的分段错误。下面提供了来自 gdb 的回溯。这些功能可以在回溯下方看到。将指针传递给fixup()函数是不正确的还是我需要取消引用这个节点？传递 Node 本身然后创建一个新的 Nodeptr 对象会更好吗？感谢您的时间。

我正在阅读有关红黑树的信息，并且我知道节点可以是红色或黑色。规则说：

1) 每个节点都有一种颜色——红色或黑色。

2）树的根总是黑色的。

3）没有两个相邻的红色节点（一个红色节点不能有一个红色的父节点或红色的孩子）

4) 从一个节点（包括根节点）到它的任何后代 NULL 节点的每条路径都有相同数量的黑色节点。

没有说明哪些节点应该编码为红色？我知道树可以有所有黑色节点，但我不明白的是我们什么时候应该将节点标记为红色？

我还想了解这种颜色编码背后的原因。我知道 RB 树基本上是一棵自平衡树，但我想了解这种二进制颜色编码对此有何帮助？

我怎样才能找到一个元素序列，如果插入到红/黑树中，将完全通过改变颜色而不是执行旋转来平衡？

我是一个新手，我正在尝试在 CI 中创建一个 rb 树，我设法从 CLRS 对算法和数据结构的介绍中制作了下面的代码伪代码。问题是无论我运行多少次，程序都会崩溃如果它尝试使用其中一个旋转功能。任何建议将不胜感激