如何轻松记住红黑树的插入和删除？

Question

完全理解标准二进制搜索树及其操作非常容易.由于这种理解,我甚至不需要记住那些插入,删除,搜索操作的实现.

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

我理解在插入新节点时,我们将节点标记为红色(因为红色是我们可以做的最好的,以避免破坏较少的红黑树法则).新的红色节点可能仍然打破"没有连续的红色节点法则".然后我们通过以下方式解决

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

2. 如果它是正确的孩子,左转其父

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

完成(基本上像上面).

许多地方描述了如上所述的红黑树的插入.他们只是告诉你如何做到这一点.但为什么这些步骤可以修复树？为什么先左转,然后右转？

谁能更清楚地解释为什么对我更清楚,比CLRS更清楚？轮换的魔力是什么？

我真的希望这样理解,1年后,我可以自己实施红黑树,而无需查看书籍.

谢谢

Answer 1

为了其他人阅读此帖子的人的利益,他们无法访问接受的答案中提到的书籍,我希望这是一个可接受的描述性答案.

旋转使树处于满足重新着色标准的状态(子节点有一个红色的叔叔).有两个主要区别:

• 哪个节点是"子",哪个节点是"叔叔"已经改变;
• 而不是将父母和叔叔重新着色为黑色,将祖父母重新着色为红色,而是将父母重新着色为红色,将祖父母重新着色为黑色.

当子节点没有红色的叔叔时,你必须旋转,因为如果叔叔节点已经是黑色,那么使父黑色将仅在祖父母的一侧增加黑色高度1.这将违反红黑树的高度不变性并使树不平衡.

现在让我们看看旋转如何转换树,以便我们有一个带有红色叔叔的子节点,并且可以使用重新着色.我建议用它来完全理解它.

• 设x为红色父节点的当前红色节点.
• 设p在旋转之前是x的红色父项(如果父项是黑色的,我们已经完成了).
• 让y成为旋转之前x的黑色叔叔(如果叔叔是红色的,我们就不需要旋转.我们只需将父母和叔叔重新着色为黑色,将祖父母重新着色为红色).
• 设g是旋转前的x的黑色祖父母(因为父母是红色的,祖父母必须是黑色的;否则这不是一个红黑树开始.)
• 当你有一个左 - 左(LL)或右 - 右(RR)的情况(也就是说,x是p的左子,p是g的左子,x是x的右子,p是右子g)的一个孩子,经过一次轮换(如果是LL则为右,若RR为左),y成为孩子,x成为其叔叔.由于x是一个红色的叔叔,你现在有一个可以重新着色的情况.因此,将孩子的父母(因为孩子现在是y,其父母是g)重新着色为红色,将孩子的祖父母(现在是p)重新着色为黑色.
• 当你有一个LR(x是左子或p和p是g的右子)或RL情况(x是p的右子,p是g的左子),经过双重旋转(右)左边是LR,左边再右边,如果RL),y成为孩子,p成为它的叔叔.由于p是一个红色的叔叔,你再次有一个可以重新着色的情况.因此,将父级(因为孩子现在为y,其父级为g)重新着色为红色,将子级的祖父母(现为x)重新着色为黑色.

在旋转和重新着色之前,你有一个黑色的祖父母,在A面(左边或右边)有2个红色节点和0个黑色节点,在B面有一个黑色节点(与A面相反).在旋转和重新着色之后,你有一个黑色祖父母,在A面有1个红色节点和0个黑色节点,在B面有1个红色节点和1个黑色节点.所以你基本上将其中一个红色节点移动到另一个子树祖父母不增加任何子树的黑色高度.

这是轮换的魔力.它允许您将额外的红色节点移动到另一个分支而不更改黑色高度,并且仍然保留二叉搜索树的排序遍历属性.

Answer 2

逻辑很简单.假设z为红色且z的父级为红色:如果z的叔叔为红色,则执行步骤1向上推动有问题的节点,直到(1)父级成为根.然后只需将根标记为黑色.完成或(2)z的叔叔是黑色的.

在情况(2)中,(a)z是其父节点的左子节点,则步骤3将是最后一步,因为满足了BST的所有属性.完成.或(b)z是其父母的正确子女.第2步将问题转换为案例(a).然后做第3步.完成.

因此,逻辑是试图达到案例(1)和(2a),以先到者为准.这些是我们了解解决方案的情况.

Answer 3

忽略我的（现已删除）评论 - 我认为冈崎的代码会对你有所帮助。如果你有这本书（“纯函数数据结构”），请查看第 26 页上的文本和图 3.5（面向，第 27 页）。很难比这更清楚了。

不幸的是，网上提供的论文没有这一部分。

我不会将其复制出来，因为该图很重要，但它表明所有不同的情况基本上都是同一件事，并且它提供了一些非常简单的 ML 代码，足以说明这一点。

[更新] 看来你可以在亚马逊上看到这个。转到该书的页面，将鼠标悬停在图像上，然后在搜索框中输入“红黑”。这将为您提供包含第 25 页和第 26 页的结果，但您需要登录才能查看它们（显然 - 我还没有尝试登录来检查）。