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

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

我现在正在学习红黑树，并且我了解它的特性，可以使树保持平衡。但是，我很难理解其插入和删除过程。

我了解在插入新节点时，我们将该节点标记为红色(因为红色是我们最好的方法，以避免破坏较少的红黑树定律)。新的红色节点仍可能违反“无连续红色节点法则”。然后我们通过以下方式修复它:

检查其叔叔的颜色(如果为红色)，然后将其 parent 和叔叔标记为黑色，然后去祖 parent 那里。

如果是正确的 child ，则向左旋转其父

将其父项标记为黑色，将其祖 parent 标记为红色，然后右旋转其祖 parent 。

完成(基本上与上面类似)。

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

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

我真的很想了解，因此在1年后，我可以自己实现Red-Black树，而无需阅读本书。

谢谢

最佳答案

忽略我(现在已删除)的评论-我认为冈崎的代码将为您提供帮助。如果您有这本书(“纯功能数据结构”)，请看第26页上的文字和图3.5(第27页，封面)。没有比这更清晰的了。

不幸的是the thesis available on-line没有这部分。

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

[更新]看来您可以在亚马逊上看到此内容。转到the book's page，将鼠标悬停在图片上，然后在搜索框中输入“红黑”。这会为您提供包含第25页和第26页的结果，但是您需要登录才能看到它们(显然-我没有尝试登录进行检查)。