红黑树详细理解笔记

本科的时候就有仔细想过这个问题，但是那个时候说起来一方面杂事儿有点多，另一方面其实我的基础还没有那么牢固，这个问题看起来有点吃力。这个问题在算法导论上是单独开了一个章节来介绍。而在那本经典的数据结构与算法分析黑书中，则是列到了高级数据结构的归类。实际上，in my opinion, 这个数据结构应该算不上太高级或者说难以理解(虽然我理解了很久)，现有的问题其实是没有一个真正通俗易懂，或者说真正地能够挖掘到每一个细节的相关的材料，当然，

• 算法导论的讲解算是一个很详细的材料了，除了最后的删除那里讲得有些不太清晰；
• Sedgwick 的算法四也算一个，毕竟他是红黑树的发明者之一，不过，书中也不是讲得很详细，但是据网上的说法，似乎结合他的二三树来逐步理解会更加容易一些；
• 数据结构与算法分析，这个就有点过于简略了，甚至连一些基础的证明都没有给出。

最近恰好没什么其它要紧的事情，因此重新回来思考这个数据结构，该说，总算是吃到了腹中，也尤其值得回味。

ok，下面就结合算法导论记录一下我对红黑树的理解与实现。

首先，定义要摆出来，

一棵红黑树是满足下面红黑性质的二叉搜索树：

1. 每个节点要么是红色的，要么是黑色的。
2. 根节点是黑色的。
3. 每个叶节点(NIL)是黑色的。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
5. 对每个节点，从该节点到其所有后代节点的简单路径上，均包含相同数目的黑色节点。

按：

• 二叉搜索树的材料可以借助 Weiss 的《数据结构与算法分析》来回忆，书中的这一块儿还是写的很详细的。
• 其中简单路径的定义是从树上的某点开始沿树边走不重复的点到树上的另一点结束而形成的路径。

下面的三幅图显示了一个红黑树的例子。

按：注意这里的 T.nil，它指代的就是前面的定义中的叶节点(NIL)。整棵树只用了这一个 NIL。

然后，这里有一个引理来说明红黑树的高度所带来的效率。

引理：一棵有 n 个内部节点的红黑树的高度至多为 $2lg(n+1)$。

关于这个定理的详细证明可以看算法导论中的介绍(如下)，我认为这个对于我们理解红黑树并不重要，这里不作多讲。

红黑树的两个核心操作是插入和删除。一个辅助的操作是旋转，我想，这个大家应该都不陌生，左旋和右旋的操作的图示如下，

按：根据我的理解，所谓左旋，就是把水平方向处于左边的节点给拽下来，所谓右旋，就是把右边的节点给拽下来。(这样或许会更好记一点)

这个伪码写得挺清晰的，如果想更加形象地理解，可以看下面的这个图片例子，

未完待续…

博主有更重要的事情在处理中…