26 | 红黑树（下）：掌握这些技巧，你也可以实现一个红黑树

我看到老师说道要我举个例子，我不太清楚是我说的那个问题还是关于红黑树的理解，这里也分个区 一：我说的case3的情况是表示老师的画的那个图，case3图的例子根节点到左边叶子节点只经过2个黑色节点，到右边叶子节点却经过了3个黑色节点。 二：我这里就大概说下吧（一家之言，自己的一点经验，也希望别的同学来一起讨论）： 1.左旋右旋这个，个人还是认为要画图，不画图我自己也写不出那个代码……哈哈。 2.说到插入删除的算法，我说用到了递推，就比如插入的CASE1的情况，CASE1的处理之后，关注节点从本身变成了他的祖父节点（红色节点），这就是往根节点递推。不过我认为CASE1处理过一次之后，不一定会进入case2或者case3，是有可能还在case1的。 换句话说，就是可以在case1的情况下，一直往根节点走，因为当前节点永远是红色，所以在最后要把根节点涂黑。同时，只要进入到case2,case3的情况，就是变成平衡二叉树的单旋和双旋的情况，双旋的处理逻辑就是把双旋变成单旋（比如先右后左旋就是把树变成“左撇子”）。这个就变成了单左旋能一步到位处理的平衡了，这个就是归纳。把未知情况转化为已知，如果我没有记错的话，数学归纳法的核心思想就是递推和归纳。 3.其实我们只要记住，除了关注的节点所在的子树，其他的子树本身都是一颗红黑树，他们是满足红黑树的所有特征的。当关注节点往根节点递推时，这个时候关注节点的子树也已经满足了红黑树的定义，我们就不用再去特别关注子树的特征。只要注意关注节点往上的部分。这样就能把问题简化，思考的时候思路会清晰一些。 4.再说到删除算法，我看到很多同学没理解为什么要红-黑，黑-黑节点的出现。这里我的看法是，红黑树最不好控制的其实是最后一个的性质4（每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点），因为你永远不知道别的子树到底有多少个黑色节点。这里加入红-黑，黑-黑节点就可以控制红黑树满足性质4，到时候要恢复颜色，只要去掉多余的黑色即可。 接下来的处理思路就是要满足：1.每个节点不是红的就是黑的，2.相邻节点不能是红的。这个思路计时变复杂为简单。 删除的case1情况，并没有真正处理，而且为了进入接下来的case2,case3,case4，这里又是之前说到的归纳思想。case2的情况又是一个递推思路，关注节点往根节点递推，让其左右子树都满足红黑树的定义。因为往上推，右子树多了一个黑色节点，就把关注节点的兄弟节点变红，使其满足性质4. 删除的case3是为了进入case4，提前变色的原因和case2是一样的，都是为了满足性质4。同样是归纳推理的思路。都要记住一点，各种case下的其他子树节点都满足红黑树的定义，需要分类讨论的，都在这几种case情况中了。 4.最后的建议，其实说了这么多，很多的表达都不太清楚，但是个人感觉，数学基础好的同学，理解红黑树会好一些，学习的时候多画画图，人对图形的敏感肯定比文字高，另外的就是大家可以去看看源码，本人是做java开发的，jdk1.8的treemap就是用红黑树实现的，跟着源码多看看，跟着老师的说明或者百度上的教程思考，动笔画画图，都能理解的。我自己看jdk源码的也是看了将近两个月才大概明白（因为也在上班，只有晚上有一些时间来看看代码）。学习的过程中要耐心，学习红黑树本身也不是为了“默写”，而是去学习思想，锻炼思维，复杂问题简单化，新问题转化为已解决过的问题等等。其实说到最后，都是用到了数学的思维，这些思维都会在潜移默化中影响到自己。 ps:本人并不是什么大牛，不会的东西也是很多很多，上面只是自己的一点感想。老师的建议很多，不要太去扣细节，我们要在一个整体的角度上去看红黑树是怎么处理的，知道他的应用场景，什么时候要用他，什么时候该用他，为什么要用他。这几个地方弄清楚，大部分就够了，我们要有的放矢，抓准学习的核心内容。

回到家我又翻看了《算法导论》中红黑树章节，又似乎加了点理解。 虽然里面时间复杂度依旧是用数学推导出来的，我看不懂，不过里面讲的红黑树5个性质： 1.每个节点不是红色就是黑色 2.根节点是黑色 3.每个叶子结点（NIL）是黑色的 4.如果一个节点是红色的，则他的两个子节点都是黑色的 5.对每个子结点，从该结点到其所有后代叶子结点的简单路劲上，均包含相同数目的黑色结点 后面讲到的3种情况都是为了满足这5点特性而做出的相应的变化 老师在讲解左右旋的时候一张图就概括了，说实话我第一时间真没看懂，花了大量时间这方面的理解，后来在《算法导论》中居然找到了浅显易懂的中文描述左右旋的过程，我概述为3点 1.左右旋操作中，只有指针的改变，其他所有属性都保持不变 2.左旋的过程与右旋的过程是对称的（伪代码也是对称的） 3.左旋为例，以x结点左旋，那么y成为该子树的跟结点，x成为y的左子结点，y的左子结点成为x的右子结点（所以右旋就是反过来的） 那么当多层级的呢，也就是文中case3中的右旋过程，因为是a的曾祖父结点来进行右旋，所以文中的“c”就是x，“a和b”就是y，那么右旋用文字描述就是“y（a,b）成为跟结点，x（c）成为y的右结点，y的右结点成为x的左结点，其他指针不变” 得到的子树结构然后根据前面说的5个特性（同老师说的4点特征）再做出响应的颜色变化 ～～～～ 唉，真是智商捉急

老师你好，本次实现代码有在git上存吗？

先提一个问题：老师，插入的case3情况是不是不满足红黑树的第四个条件？根节点到左边的叶子节点只经过两个黑色节点，但是根节点到右边的却经过三个黑色节点。 学习红黑树在于理解他的思想，比如为什么要旋转，是因为高度不平衡。为什么有双旋，因为单旋没法一步到位，所以把一个新问题转化为已经解决过的问题。旋转的学习其实自己画一下图，一步步走，数形结合的思想用上就好。插入的核心思想就是，把红色节点往根节点递推，然后把根节点涂黑。删除同样是往根节点递推，转化成处理过的情况因为越靠近根节点，节点关系也就越清晰。其实红黑树的处理也有动态规划的思想，只有处理的这个节点子树是可能破坏的，而其他节点子树都是红黑树，都满足红黑树的定义。用数学归纳法的思路来想这些问题，感觉就不会被复杂的情况搞得头晕。

关于红黑树的插入看完这篇文章回头再看老师写的插入的三种case就会明白很多 https://blog.csdn.net/wan198809/article/details/48602921

这部分感觉只是简单罗列，知其然不知其所以然，个人认为没讲好

添加的case2中一开始就不满足红黑球的定义了，根节点到右子节点经历过的黑色节点数比经过左边可到答节点数要多1

到这里终于蒙圈了

老师，准备写一篇博客，讲解红黑树的，是否可以引用您讲解的部分观点，会注明观点出处

git上红黑谁的代码没见到， 王老师发下链接