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

精选留言(173)

• 

  沉睡的木木夕

  感觉看不下去了，多层级的左旋右旋过程能不能再详细说一下？还有新增，删除那里的case几种情况，是不是就是说红黑树操作只有这几种情况？这里面的左右旋真的没搞懂

  2018-11-19

   7

   121
• 

  失火的夏天

  我看到老师说道要我举个例子，我不太清楚是我说的那个问题还是关于红黑树的理解，这里也分个区
  一：我说的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:本人并不是什么大牛，不会的东西也是很多很多，上面只是自己的一点感想。老师的建议很多，不要太去扣细节，我们要在一个整体的角度上去看红黑树是怎么处理的，知道他的应用场景，什么时候要用他，什么时候该用他，为什么要用他。这几个地方弄清楚，大部分就够了，我们要有的放矢，抓准学习的核心内容。

  作者回复: 👍 倾佩

  2018-11-20

   1

   109
• 

  pplegend

  我决定了 放弃研究红黑树了，如果面试遇到算我倒霉，人生要学会放弃一些东西

  2019-03-20

   5

   75
• 

  凡

  文章还没看完，前面的就忘了

  2018-11-19

   3

   64
• 

  。。。

  红黑树是由2-3树演变过来的，父节点指向的节点是红节点，那么就认为这两个节点其实是2-3树里面的3节点。如果有一个黑节点链接了两个红节点，那么就认为这是一个4-节点，因为2-3树不允许4-节点所以要将其提取出来。所谓的旋转。对于2-3树来说节点并没有变化。因为 红节点和指向他的节点本来就被认为是一个节点。建议看《算法》。里面讲了红黑树的精髓。看完以后怎么旋转怎么写红黑树就都知道了

  2018-11-21

   2

   51
• 

  zixuan

  这个不是设计而是推导出来的，源自2-3树 https://blog.csdn.net/fei33423/article/details/79132930

  2018-11-19

  

   34
• 

  凉粉

  一脸懵

  2018-11-19

  

   31
• 

  沉睡的木木夕

  回到家我又翻看了《算法导论》中红黑树章节，又似乎加了点理解。
  虽然里面时间复杂度依旧是用数学推导出来的，我看不懂，不过里面讲的红黑树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点特征）再做出响应的颜色变化
  ～～～～
  唉，真是智商捉急

  作者回复: 👍

  2018-11-20

   1

   28
• 

  ban

  1、没看懂哪个节点跟哪个节点左旋或者右旋
  2、为什么要有红/黑节点，为什么要有红-黑 黑-黑，作用是什么

  2018-11-19

  

   22
• 

  iron_man

  红黑树是2-3树的变形，以2-3树的角度去理解红黑树就简单了，作者可以结合2-3数来讲讲红黑树插入删除节点时的各种操作

  2018-11-19

  

   18
• 

  Andylee

  看到删除的部分突然懵了，什么时候多了一个红黑，黑黑，一个节点两个颜色的概念了……

  2018-11-19

  

   14
• 

  xiao皮孩。。

  说实话，前几章都看懂了，这个真没懂

  2019-02-15

  

   11
• 

  任旭东

  老师能讲一下调整策略是怎么推出来的么？就像数学公式一样，只知道公式，不知道推理过程很难理解😂

  2018-11-19

  

   11
• 

  qinggeouye

  试着理解了一下「实现红黑树的基本思想」图例 1 中左旋和右旋的概念，可以将图例 1 中的树看作一个定滑轮：
  
  围绕节点 X 的左旋：
  拉住节点 X 左边的 a 子树，向下拉，将节点 Y 拉到节点 X 的位置，a 子树仍是节点 X 的左子树，而节点 X 成为了节点 Y 的左子节点，那么就将原先节点 Y 的左子树 b 摘下来，变成节点 X 的右子树；
  
  同理，围绕节点 X 的右旋：
  拉住节点 X 右边的 r 子树，向下拉，将节点 Y 拉到节点 X 的位置，a 子树仍是节点 Y 的左子树，而节点 X 成为了节点 Y 的右子节点，那么就将原先节点 Y 的右子树 b 摘下来，变成节点 X 的左子树；

  2018-12-05

   1

   7
• 

  数据结构和算法

  这个图文结合对红黑树公析的很详细https://blog.csdn.net/abcdef314159/article/details/77193888

  2018-11-30

  

   7
• 

  失火的夏天

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

  作者回复: 能否举个例子呢

  2018-11-19

   2

   7
• 

  windcaller

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

  作者回复: 没 好难写😂

  2019-06-13

  

   6
• 

  花仙子

  您好，老师有一点不太明白，就是删除操作时，以初步调整为例，case3的情况下，原文（如果节点 d 是黑色，为了不违反红黑树的最后一条定义，我们给节点 d 的右子节点 c 多加一个黑色，这个时候节点 c 就成了“红 - 黑”或者“黑 - 黑”；），最后一条是（每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数数目的黑色节点。），能理解要给节点 d 的右子节点 c 多加一个黑色，但图中的表示方法没看明白，引文原来的d节点是在c和e之间，所以所加的黑色节点是不是也应该在c和e之间，这点不太确定影响后边大半部分的理解，还请老师不吝赐教，多谢，真的挺焦急的

  2018-11-28

  

   6
• 

  Peter Cheng

  魔方还原公式总共200多种，要全部背下来并熟练运用，花的时间因人而异。我觉得这和你完全要掌握红黑树一样，你需要把每种情况都熟记，方能熟练运用。

  2018-11-19

  

   6
• 

  往事随风，顺其自然

  为什么红黑和黑黑这样来标注，这两种看成是黑色还是红色，什么时候当成黑色，什么时候当成红色

  2018-11-19

  

   6