问题标签 [red-black-tree]

我从（Lafore）学习的教科书首先介绍了红黑树，并且不包含任何伪代码，尽管所介绍的相关算法似乎相当复杂，有许多独特的案例。

接下来，他介绍了 2-3-4 树，在我看来，这似乎更容易理解，我猜想，实现。他包含了一些非常清晰的实际 Java 代码。他似乎暗示 2-3-4 更容易实施，根据我目前所见，我会同意。

然而，维基百科却说相反……我认为这可能是不正确的：

http://en.wikipedia.org/wiki/2-3-4_tree

2-3-4 树是红黑树的等距，这意味着它们是等效的数据结构。换句话说，对于每棵2-3-4树，至少存在一棵数据元素顺序相同的红黑树。而且，对2-3-4树的插入和删除操作会导致节点扩展、分裂和合并，相当于红黑树中的颜色翻转和旋转。红黑树的介绍通常首先介绍 2-3-4 树，因为它们在概念上更简单。然而，2-3-4 树在大多数编程语言中可能难以实现，因为树上的操作涉及大量特殊情况。红黑树更容易实现，因此倾向于使用。

具体来说，关于“大量特殊情况”的部分对我来说似乎很落后（我认为是RB有大量特殊情况，而不是2-3-4）。但是，我仍在学习（老实说，我还没有完全了解红黑树），所以我很想听听其他意见。

作为旁注......虽然我同意 Lafore 所说的大部分内容，但我认为有趣的是，与维基百科所说的常见（RB 之前的 2-3-4）相比，他以相反的顺序呈现它们。我确实认为首先 2-3-4 会更有意义，因为 RB 更难以概念化。也许他选择了这个顺序，因为 RB 与他刚刚在上一章中完成的 BST 更密切相关。

我对红黑树和 2-3-4 树以及它们如何保持高度平衡以确保最坏情况下的操作为 O(n logn) 都有基本的了解。

但是，我无法理解来自维基百科的这段文字

2-3-4 树是红黑树的等距，这意味着它们是等效的数据结构。换句话说，对于每棵2-3-4树，至少存在一棵数据元素顺序相同的红黑树。而且，对2-3-4树的插入和删除操作会导致节点扩展、分裂和合并，相当于红黑树中的颜色翻转和旋转。

我看不出这些操作是如何等效的。维基百科上的这句话准确吗？怎么能看出这些操作是等价的呢？

我已经在 c 中完成了一棵红黑树，我发现很难按级别顺序打印它。我有一个打印顺序，但我无法想象我应该如何在控制台打印中将它显示为树。可行吗？我们可以在这里实现 BFS 或 DFS 吗？我在 wiki 中找到了一个算法，但我无法应用它。如果有人有 C 语言的代码，你能把它贴在这里以便我研究吗？来自维基：

我几乎完成了一棵红黑树，但我的删除出现故障。它可能会删除一个它可能不会删除的节点。在我删除根目录并按下打印选项后，我的屏幕上充斥着我在树中已有的节点。在测试树中，2,1,7,5,8,11,14,15,4如果我删除root=7并按我得到的按顺序打印2,4,5,8,1,2,4,5,8,1,.....等等，直到程序崩溃。如果我删除 2，程序会立即崩溃。节点 11 像 1-4-15 一样删除所有叶子。我试图通过调试找到问题，但一切似乎都正常。该代码基于 Cormen 对算法的介绍。谢谢！

我在家庭作业中被要求回答一个关于“红-红-黑”树的问题。红红黑树的描述（从互联网某处复制）是：

“红-红-黑树是满足以下条件的二叉搜索树：

1. 每个节点不是红色就是黑色
2. 每片叶子（零）都是黑色的
3. 如果一个节点是红色的，它的父节点是红色的，那么它的两个子节点都是黑色的
4. 从节点到后代叶子的每条简单路径都包含相同数量的黑色节点（树的黑色高度）”

有人问我，给定具有 n 个节点的红-红-黑树，黑色高度为 k 的最大内部节点数是多少？最小的数是多少？

我已经想了两个多小时了，但除了头痛之外，我一无所获。

谢谢！

完全理解标准二叉搜索树及其操作非常容易。因为有了这样的理解，我什至不需要记住那些插入、删除、搜索操作的实现。

我现在正在学习红黑树，我了解它保持树平衡的属性。但是我觉得很难理解它的插入和删除过程。

我知道在插入新节点时，我们将节点标记为红色（因为红色是我们能做的最好的事情，以避免破坏较少的红黑树法则）。新的红色节点仍有可能打破“无连续红色节点定律”。然后我们通过以下方式修复它：

1. 检查其叔叔的颜色，如果是红色，则将其父母和叔叔标记为黑色，然后去找祖父母。

2. 如果它是右孩子，左旋转它的父母

3. 将其父母标记为黑色，将其祖父母标记为红色，然后向右旋转其祖父母。

完成（基本上和上面一样）。

很多地方都像上面描述了红黑树的插入。他们只是告诉你如何去做。但是为什么这些步骤可以修复树呢？为什么先左旋，后右旋？

谁能比 CLRS 更清楚地向我解释为什么？旋转有什么魔力？

我真的很想明白，所以一年后，我可以自己实现红黑树，而无需复习一本书。

谢谢

I implemented in Red-Black trees in Python according to the pseudo code in Cormen's Introduction to Algorithms.

I wanted to see in my own eyes that my insert is really O(logn) so I plotted the time it takes to insert n=1, 10, 20, ..., 5000 nodes into the tree.

This is the result:

the x-axis is n and the y-axis is the time it took in milliseconds.

To me the graph looks more linear than logarithmic. What can explain that?

我在 stackoverflow 上看到了一个类似的问题，但没有（清楚地）回答。

我可以尝试构建这样的树（8 个黑色节点和 12 个红色节点），而不会使 5 个 RB 树中的任何一个无效（但到目前为止我还不能这样做）；

1. 节点是红色或黑色
2. 根是黑色的
3. 所有的叶子都是黑色的
4. 每个红色节点的两个孩子都是黑色的
5. 从给定节点到其任何后代叶子的每条简单路径都包含相同数量的黑色节点。

但我真的对更优雅的答案很感兴趣（除了尝试看看它是否有效）。

编辑：在叶子被算作黑色的情况下，很明显这样的树是不可能构建的。但是如果叶子不被算作黑色节点（8 个非叶子节点）呢？

删除功能不起作用。如果我删除一个节点，剩下的就是该节点的子树。

你认为这有什么问题？提前致谢。

当红黑树中新插入的节点具有红色父节点，黑色叔叔并且与祖父母（黑色）内联时，我知道如何处理这种情况（第 5 种情况）。例如，如果是这样的情况：
R2(当前节点，R1的左孩子)-----R1(左孩子)-----B0(根)----B1(右孩子)

对于上述情况，我应该围绕根节点（B0）旋转树，使其变为

R1----R2(新根节点)------B0(R2右孩子)-----B1(B0的右孩子)

然后将B0的颜色更改为红色，将R2的颜色更改为黑色

这是标准解决方案，但如果不是将 B0 的颜色更改为红色并将 R2的颜色更改为黑色，而是将 R1 的颜色更改为黑色，我看不到红黑树的任何属性被违反。

任何人都可以对此有所了解吗？谢谢 （：