这是很容易充分理解标准的二叉搜索树及其操作。由于这种认识，我甚至不需要记住这些插件的实现，删除，查询操作。

It is quite easy to fully understand standard Binary Search Tree and its operations. Because of that understanding, I even don't need to remember the implementations of those insert, delete, search operations.

我学习红黑树，现在，我理解它的性能保持平衡的树。不过，我觉得很难理解它的插入和删除程序。

I am learning Red-Black Tree now and I understand its properties for keeping the tree balanced. However I feel very hard to understand its insert and delete procedures.

据我所知插入一个新的节点时，我们纪念节点为红色（因为红色是最好的，我们能做些什么来避免破坏较少的红黑树的法律）。新的红点可能仍然打破了没有连续红色节点法。然后，我们通过解决这个问题：

I understand when inserting a new node, we mark the node as red (because red is the best we can do to avoid breaking less Red-Black tree laws). The new red node may still break the "no continuous red nodes law". Then we fix it via:

检查其叔叔的颜色，如果红，则标志着其母公司和叔叔为黑色，并转到祖父母。

check its uncle's colour, if red, then mark its parent and uncle as black, and go to grandparent.

如果它是正确的孩子，左旋转其父

if it is right child, left rotate its parent

标记其父为黑色和红色祖父母，然后用鼠标右键旋转的祖父母。

mark its parent as black and its grandparent as red, then right rotate its grandparent.

完成（基本上像上图）。

done (basically like above).

很多地方描述像上面红黑树的插入。他们只是告诉你如何做到这一点。但是，为什么这些步骤可以解决树？为什么第一次离开旋转，然后用鼠标右键旋转？

Many places describes Red-Black tree's insert like above. They just tell you how to do it. But why those steps can fix the tree? Why first left rotate, and then right rotate?

任何人都可以解释为什么我更清楚，甚至比CLRS更清楚了吗？什么是旋转的魔力呢？

Can anyone explains why to me more clearly, even more clear than CLRS? What's the magic of rotation?

我真的希望1年后明白的话，我可以自己实现红黑树没有审查一本​​书。

I really wish to understand so after 1 year, I can implement Red-Black tree by myself without review a book.

感谢

推荐答案

忽略我（现已删除）注释 - 我认为okasaki的code会帮助你。如果你有这本书（纯功能数据结构），看26页的文字和图3.5（面对，第27页）。很难比这更清晰。

ignore my (now deleted) comment - i think okasaki's code is going to help you. if you have the book ("purely functional data structures"), look at the text on page 26 and figure 3.5 (facing, p 27). it's hard to get clearer than that.

不幸的是论文可在线没有这一部分。

unfortunately the thesis available on-line doesn't have that part.

我不会去复制它，因为图中是很重要的，但它表明，所有不同的情况下，基本上是同样的事情，它给了一些非常简单的ML code表示锤的那家。

i'm not going to copy it out because the diagram is important, but it shows that all the different cases are basically the same thing, and it gives some very simple ML code that hammers that home.

[更新]它看起来像你可以看到这个在亚马逊。去书的页面，鼠标在图像，并在搜索中输入红黑框。 ，让您的结果，其中包括25和26页，但您需要登录到看到他们。（很明显 - 我还没有尝试登录检查）

[update] it looks like you may be able to see this on amazon. go to the book's page, mouse over the image and enter "red black" in the search box. that gives you results that include pages 25 and 26, but you need to be logged on to see them (apparently - i haven't tried logging in to check).