1. 全栈程序员必看首页

关于红黑树的学习笔记

全栈程序员-用户IM • • 未分类

关于红黑树的学习笔记

为什么80%的码农都做不了架构师？>>>   hot3.png

前一段时间组内技术分享，正好趁这个机会好好研究了一下红黑树。在这里写下学习红黑树的一些成果和体会。

一、什么是红黑树

先看一下《算法导论》中对红黑树的定义。

  1. 每个节点或者是红色，或者是黑色
  2. 根节点是黑色
  3. 每一个叶子节点(最后的空节点)是黑色的
  4. 如果一个节点是红色的，那么它的孩子节点都是黑色的
  5. 从任意一个节点到叶子节点，经过的黑色节点是一样的

这5条红黑树的定义看过之后感觉自己还是不太懂什么是红黑树，个人觉得有这种感觉的原因是定义比较抽象，不容易让人理解。那么，我们就从另一个角度入手来理解红黑树。

1. 2-3树

这里先介绍一下2-3树。因为2-3树和红黑树有一定的联系，对于理解红黑树会有很大的帮助，所以我们先来看一下2-3树相关的一些性质。
首先，2-3树满足二分搜索树的性质。不同的是在2-3树中，存在两种节点。一种是有两个叶子节点的，我们称作“2节点”；另一种是有三个叶子节点的，我们称作“3节点”。

2-3%E6%A0%91%E8%8A%82%E7%82%B9%E6%A6%82%E8%A7%88.png

如下是一整颗2-3树的示例。需要强调的是2-3树是完全平衡的树，即从根节点到任意一个叶子节点的高度都是相同的。

2-3%E6%A0%91%E6%95%B4%E4%BD%93%E7%A4%BA%E4%BE%8B.png

2. 2-3树怎样保持完全平衡性

向2-3树中添加一个节点，遵循向二分搜索树中添加节点的基本思路，插入节点比当前节点小，则向当前节点的左子树添加，否则向右子树添加。不过由于2-3树特殊的性质，当要向“2节点”添加节点时，将待插入的节点与该“2节点”进行融合，组成一个新的“3节点”，如下图所示。

2-3%E6%A0%91%E6%8F%92%E5%85%A52%E8%8A%82%E7%82%B9.png

如果要向“3节点”添加节点，同向“2节点”添加节点一样，先组成一个临时的4节点，之后再拆分成3个“2节点”，如图所示。

2-3%E6%A0%91%E6%8F%92%E5%85%A53%E8%8A%82%E7%82%B9.png

如果要插入的“3节点”的父节点是一个“2节点”，通过上述步骤得到的拆分过成为父节点的“2节点”，需要向原“3节点”的父节点进行融合，组成新的“3节点”。过程如下图所示。

2-3%E6%A0%91%E6%8F%92%E5%85%A53%E8%8A%82%E7%82%B9-%E7%88%B6%E8%8A%82%E7%82%B9.png

如果要插入的“3节点”的父节点是一个“3节点”，大体思路相同，向父节点进行融合，只不过此时融合后成为一个临时的“4节点”，之后要再次进行拆分。过程如图所示。

2-3%E6%A0%91%E6%8F%92%E5%85%A53%E8%8A%82%E7%82%B9-%E7%88%B6%E8%8A%82%E7%82%B93.png

如上所述，2-3树保持了完全的平衡性。说了这么长时间的2-3树，那么2-3树和红黑树之间到底有怎样的关系，下面我们具体来看一下。

3. 2-3树与红黑树

对于2-3树中的“2节点”，对应于红黑树中的“黑节点”，即相当于普通二分搜索树中的一个节点。
对于2-3树中的“3节点”，相当于普通二分搜索树中的两个节点融合在一起，我们如何来描述这种融合在一起的两个节点之间的关系呢？其实很简单，如果我们将连接这两个节点的边涂成红色，就可以表示这两个节点是融合的关系，即2-3树中的一个“3节点”。那么问题又来了，对于树这种数据结构，我们在定义的时候通常都是针对节点进行定义，并没有对节点之间的边进行定义，我们如何来表示这条被涂成红色的边呢？大家都知道，对于树中的任意一个节点，都是只有一个父亲节点，所以与其父节点相连接的边可以用该节点进行表示。那么我们就可以将这两个节点中较小的节点（作为左子树的节点）涂成红色，就可以很好地表示这两个节点融合的关系了。

2-3%E6%A0%91%E4%B8%8E%E7%BA%A2%E9%BB%91%E6%A0%91-3%E8%8A%82%E7%82%B9%E5%AF%B9%E5%BA%94.png

综合以上描述，2-3树与红黑树之间的关系，我们可以用下图很好地进行表示。我们这里说的红色节点都是向左倾斜的。

2-3%E6%A0%91%E4%B8%8E%E7%BA%A2%E9%BB%91%E6%A0%91-%E8%8A%82%E7%82%B9%E7%BB%BC%E5%90%88.png

看过2-3树中的两种节点和红黑树中节点的对应关系后，我们就来看一下一棵2-3树与红黑树之间的对比，如图所示。

2-3%E6%A0%91%E4%B8%8E%E7%BA%A2%E9%BB%91%E6%A0%91-%E6%95%B4%E4%BD%93%E5%AF%B9%E6%AF%94.png

4. 红黑树的性质

讨论了2-3树与红黑树之间的关系，我们再回过头来看一下红黑树的5条定义和性质，会发现很好理解了。

  1. 每个节点或者是红色，或者是黑色
    这条定义很好理解，在此不做解释。
  2. 根节点是黑色
    根据之前说过的，红色的节点对应于2-3树中“3节点”中较小的那个节点，拆成两个“2节点”的话则是一个左子树的节点，即红色的节点总是可以和其父节点进行融合，所以红色节点一定有父节点，显然根节点不能是红色，所以根节点是黑色。
  3. 每一个叶子节点(最后的空节点)是黑色的
    这条性质和第2条是对应的。对于叶子节点（最后的空节点），一颗空树的根节点也为黑色，所以与其说第三条是一条性质，不如说也是一个定义。
  4. 如果一个节点是红色的，那么它的孩子节点都是黑色的
    根据上面2-3树与红黑树两种节点的对比图，我们很容易看到，红色节点的两个子树，对应2-3树中的话，要么是一个“2节点”，要么是一个“3节点”，而不管是“2节点”还是“3节点”，相连的第一个节点都是黑色的，所以说红色节点的孩子节点都是黑色的。
  5. 从任意一个节点到叶子节点，经过的黑色节点是一样的
    根据2-3树与红黑树的关系对比图，可以发现，红黑树中一个黑色节点对应2-3树中一整个节点（“2节点”或“3节点”），而2-3树是完全平衡的树，从根节点到任意路径的叶子节点，经过的节点个数都是相同的，对应红黑树中，即从任意节点到叶子节点，经过的黑色节点是一样的。

二、 红黑树添加元素

回忆刚刚提到的向2-3树中添加元素的过程，或者添加进一个“2节点”，形成一个“3节点”，或者添加进一个“3节点”，形成一个临时的“4节点”。理解了2-3树如何添加节点，对应红黑树就很好理解了。很容易知道，我们总是会将待插入的节点向父节点进行融合，所以我们将待插入的节点看成红色,即永远添加红色节点。
向一棵空树添加节点42。插入后，该节点是根节点，根据红黑树的性质，根节点必须是黑色，所以讲该节点染成黑色。

%E7%BA%A2%E9%BB%91%E6%A0%91%E6%B7%BB%E5%8A%A0-%E6%A0%B9%E8%8A%82%E7%82%B9.png

若向如图的红黑树中添加节点37。因为37比42小，所以添加在42的左子树，对应2-3树中，形成一个“3节点”。

%E7%BA%A2%E9%BB%91%E6%A0%91%E6%B7%BB%E5%8A%A0-%E5%B7%A6%E5%AD%90%E6%A0%91.png

若向如图的红黑树中添加节点42。因为42比37大，所以添加在37的右子树。这样的话红色节点就出现在了一个节点的右子树中，所以此时需要进行左旋转，让树满足红黑树的性质。

%E7%BA%A2%E9%BB%91%E6%A0%91%E6%B7%BB%E5%8A%A0-%E5%B7%A6%E6%97%8B%E8%BD%AC.png

1. 左旋转

对于一般的情况，如何进行左旋转呢？我们要对下图的红黑树进行左旋转。

%E5%B7%A6%E6%97%8B%E8%BD%AC-%E5%88%9D%E5%A7%8B.png

首先将node节点与x节点断开，其次将x的左子树作为node的右子树。

%E5%B7%A6%E6%97%8B%E8%BD%AC-%E8%BF%87%E7%A8%8B1.png

然后再将node作为x新的左子树，之后要把x的颜色染成node的颜色，最后将node的颜色变为红色，这样就完成了左旋转的操作。

%E5%B7%A6%E6%97%8B%E8%BD%AC-%E8%BF%87%E7%A8%8B2.png

2. 颜色翻转（flipColors）

向红黑树中插入节点66，很容易知道插入到42右子树的位置，对应于2-3树的插入如图所示。

%E9%A2%9C%E8%89%B2%E7%BF%BB%E8%BD%AC-1.png

然而上面我们说到，我们总是要将新拆分出来的树的父亲节点向上进行融合，即这个父亲节点在红黑树中总是红色的，根据红黑树的性质，该父亲节点的两个孩子节点一定是黑色的。这样就需要将上一步形成的树进行颜色的翻转，变成如下图的形态。

%E9%A2%9C%E8%89%B2%E7%BF%BB%E8%BD%AC-2.png

3. 右旋转

向如图的红黑树中插入节点12，根据二分搜索树插入的操作，此时会形成一条链状的结构，对于2-3树中则是变形成为图中的样子，才能保证平衡性。所以在红黑树中，也要通过变形，变成与2-3树对应的形态。这种情况的变形操作，称为“右旋转”。

%E5%8F%B3%E6%97%8B%E8%BD%AC-1.png

一般的情况，右旋转操作同上面的左旋转操作很类似，下面我们一起来看一下过程。我们要对下图的红黑树进行右旋转的操作。

%E5%8F%B3%E6%97%8B%E8%BD%AC%E4%B8%80%E8%88%AC-%E5%88%9D%E5%A7%8B.png

首先将node和x节点断开，将x的右子树T1作为node的左子树。

%E5%8F%B3%E6%97%8B%E8%BD%AC%E4%B8%80%E8%88%AC-%E8%BF%87%E7%A8%8B1.png

其次将node作为x的右子树。

%E5%8F%B3%E6%97%8B%E8%BD%AC%E4%B8%80%E8%88%AC-%E8%BF%87%E7%A8%8B2.png

接着要把x的颜色染成原来node的颜色，把node染成红色。

%E5%8F%B3%E6%97%8B%E8%BD%AC%E4%B8%80%E8%88%AC-%E8%BF%87%E7%A8%8B3.png

然后很显然，需要再进行一次颜色翻转操作，才能满足红黑树的性质。

%E5%8F%B3%E6%97%8B%E8%BD%AC%E5%90%8E%E9%A2%9C%E8%89%B2%E7%BF%BB%E8%BD%AC.png

有一种比较复杂的情况，向下图的红黑树中插入节点40,要满足的红黑树的性质我们需要怎么操作呢？

%E7%BA%A2%E9%BB%91%E6%A0%91%E6%8F%92%E5%85%A5%E5%A4%8D%E6%9D%82-1.png

对应2-3树中最终的形态，第一步我们可以通过一次左旋转，变成下图的样子。

%E7%BA%A2%E9%BB%91%E6%A0%91%E6%8F%92%E5%85%A5%E5%A4%8D%E6%9D%82%E5%B7%A6%E6%97%8B%E8%BD%AC.png

会发现，这样就变成了上面说到的需要右旋转的形态，所以再进行一次右旋转和颜色翻转，就可以满足红黑树的性质了。

%E7%BA%A2%E9%BB%91%E6%A0%91%E6%8F%92%E5%85%A5%E5%A4%8D%E6%9D%82%E5%8F%B3%E6%97%8B%E8%BD%AC%E9%A2%9C%E8%89%B2%E7%BF%BB%E8%BD%AC.png

4.红黑树插入总结

上面分情况讨论了向红黑树中添加节点的各种情况，这里总结一下。其实根据上面的讨论，我们可以发现，最后一种复杂的情况可以涵盖其余简单的情况，复杂的操作包含了左旋转、右旋转、颜色翻转，这三种操作，完全可以保持红黑树的性质。下面的一张图，很好的总结了向红黑树中添加节点不同情况下的过程。

%E7%BA%A2%E9%BB%91%E6%A0%91%E6%8F%92%E5%85%A5%E6%80%BB%E7%BB%93.png

三、红黑树删除元素

关于红黑树的删除操作，比插入操作要复杂一些，需要分情况进行讨论。下面我们具体来看一下。
红黑树的删除操作大体分为2步：

  1. 二分搜索树删除节点
  2. 删除修复操作

红黑树的删除首先满足二分搜索树的删除，然后对删除节点后的树进行修复操作，让其重新满足红黑树的5条性质。
对于二分搜索树的删除，这里就不再赘述，我们主要讨论红黑树的删除修复操作。以下所说的当前节点意思是通过二分搜索树的方式删除要删除的节点后，代替原来节点的节点。
当删除节点是红色节点时,那么原来红黑树的性质依旧保持，此时不用做修复操作。
当删除节点是黑色节点时,情况很多，我们分情况讨论。

1.简单情况

  1. 当前节点是红色节点
    直接把当前节点染成黑色,结束，红黑树的性质全部恢复。
  2. 当前节点是黑色节点，并且是根节点
    什么都不做，直接结束。

2.复杂情况

  1. N、S、SL、SR、P都为黑色
    其中N是上述的当前节点，S是N的兄弟节点，P是N的父节点，SL和SR是N兄弟节点的左右孩子节点。

    %E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%E6%83%85%E5%86%B51-1.png

    此时将S染成红色，这样经过N路径的黑色节点就和N的兄弟子树中的黑色节点相同了，但是经过P节点的黑色节点少了一个，此时需要将P当做新的N再进行操作，具体怎么操作可以见以下一些情况。

    %E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%E6%83%85%E5%86%B51-2.png

  2. N、S、SL、SR为黑色，P为红色

    %E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%E6%83%85%E5%86%B52-1.png

    此时将P和S的颜色进行交换,P成为了黑色,它为经过节点N的路径添加了一个黑色节点，从而补偿了被删除的黑色节点。S的颜色只是上移到父节点P上,因而经过S节点路径的黑色节点的数目也没有发生改变。

    %E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%E6%83%85%E5%86%B52-2.png

  3. N、S为黑色，SR为红色
    图中蓝色节点表示该节点可以为黑色也可以为红色，即对该节点的颜色没有要求。

    %E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%E6%83%85%E5%86%B53-1.png

    此时将以P为根的子树进行左旋转

    %E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%E6%83%85%E5%86%B53-2.png

    然后交换P和S的颜色

    %E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%E6%83%85%E5%86%B53-3.png

    将SR染成黑色

    %E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%E6%83%85%E5%86%B53-4.png

    调整后经由N的路径的黑色节点数比调整前增加了一个，恰好补偿了被删除的黑色节点。对于不经过N但经过其他节点的任意一个路径来说，它们贡献的黑色节点数目不变。

     

  4. N、S为黑色，SL为红色，SR为黑色

    %E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%E6%83%85%E5%86%B54-1.png

    此时，将以S为根的子树进行右旋转

    %E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%E6%83%85%E5%86%B54-2.png

    接着交换S和SL的颜色

    %E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%E6%83%85%E5%86%B54-3.png

    节点SL的左孩子在旋转前后不变，而SL原来为红色，所以SL的左孩子必定为黑色。所以旋转后对于N节点来说，相当于情况3。之后再通过情况3中的描述进行操作。整体上情况4需要进行一次右旋转和一次左旋转。

     

  5. N为黑色，S为红色

    %E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%E6%83%85%E5%86%B55-1.png

    此时，将以P为根的子树进行左旋转

    %E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%E6%83%85%E5%86%B55-2.png

    将P和S颜色交换

    %E7%BA%A2%E9%BB%91%E6%A0%91%E5%88%A0%E9%99%A4%E6%83%85%E5%86%B55-3.png

    经过这样的变换后，把该情形转化成了N为黑色，其兄弟为黑色的情形，再通过以上描述的几种情况进行变换，最终保持红黑树的性质。

    红黑树删除的各种复杂的情况，以上都进行了讨论，虽然比较繁琐，但是认真研究后还是可以理解的，并没有之前想象地那么困难。

     

四、红黑树的性能

红黑树的增删改查的复杂度显然是O(logn)级别的，通常说红黑树是统计性能更优的树结构。
为什么说统计性能更优呢？因为若是单纯的读操作，AVL树的性能比红黑树强一些，红黑树不是严格的平衡树，它是保持“黑平衡”的树。对于红黑树，最坏的情况，是树中最左侧的节点的左子树都是红色的节点，即对应2-3树中的“3节点”，所以这时红黑树的高度就是2logn（除了logn个黑色节点外，还有logn个红色节点），红黑树要比AVL树要高一些。所以从单纯的查询性能来说，红黑树的性能并没有AVL树强。
对于插入删除操作来说，红黑树相比于AVL树减少了左旋转或右旋转的次数，所以红黑树的插入删除的性能比AVL树强一些。
综合增删改查各方面的性能，红黑树的综合性能比较高。

五、红黑树的应用

  1. Java中的TreeMap，Java8中HashMap的TreeNode节点采用了红黑树实现
  2. C++中，STL的map和set也应用了红黑树
  3. Linux中完全公平调度算法CFS(Completely Fair Schedule)
  4. 用红黑树管理进程控制块epoll在内核中的实现，用红黑树管理事件块
  5. Nginx中，用红黑树管理timer等

这次的分享，主要对红黑树的性质以及向红黑树中插入、删除元素进行分析，对于红黑树的应用并没有很深入的进行研究，如上所述的几种红黑树的应用，也只是了解，还需要在以后的工作学习中进行完善。以上是本人对红黑树学习的一些成果和心得，记下来让自己所学的知识体系化，也方便日后的复习回顾。

转载于:https://my.oschina.net/yomut/blog/2236964

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/101380.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0
blank

相关推荐

  • 单模光纤的传输距离比多模光纤的传输距离_单模多模单模光纤传感器

    单模光纤的传输距离比多模光纤的传输距离_单模多模单模光纤传感器

    单模光纤的传输距离比多模光纤的传输距离_单模多模单模光纤传感器1.1000Base-SX及1000Base-LX是什么意思?短波长光传输1000Base-SX、长波长光传输1000Base-LX多模光纤可以分为长波激光(称为1000BaseLX)和短波激光(称为1000BaseSX)。2.千兆位以太网标准问题：请问多模和单模光纤的极限传输距离是多少？标准光纤类型光纤直径(μm)最大传输距离1000base-sx多模62.5260m1000base-sx…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年8月30日
  • 如何判断一个网址是否安全_域名和dns的区别

    如何判断一个网址是否安全_域名和dns的区别

    如何判断一个网址是否安全_域名和dns的区别前言近几年，互联网发生着翻天覆地的变化，尤其是我们一直习以为常的HTTP协议，在逐渐的被HTTPS协议所取代，在浏览器、搜索引擎、CA机构、大型互联网企业的共同促进下，互联网迎来了“HTTPS加密时代”，HTTPS将在未来的几年内全面取代HTTP成为传输协议的主流。读完本文，希望你能明白： HTTP通信存在什么问题 HTTPS如何改进HTTP存在那些问题 HTTP…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年10月16日
  • MQ消息队列详解、四大MQ的优缺点分析

    MQ消息队列详解、四大MQ的优缺点分析

    MQ消息队列详解、四大MQ的优缺点分析MQ消息队列详解近期有了想跳槽的打算，所以自己想巩固一下自己的技术，想了解一些面试比较容易加分的项，近期准备深入研究一下redis和mq这两样，这总体上都是为了解决服务器并发的原因，刚翻到了一篇有关于mq的，觉得写得特别好，特此记录一下，也算是为了加深自己的印象。首先从MQ容易面对的面试题切入一下为什么要使用MQ消息队列有什么优点和缺点kafka、ActiveMQ、RabbitMQ、R…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年6月2日
  • Linux 文件权限rwx

    Linux 文件权限rwx

    Linux 文件权限rwxLinux/Unix的文件调用权限分为三级:文件所有者（Owner）、用户组（Group）、其它用户（OtherUsers）。只有文件所有者和超级用户可以修改文件或目录的权限。可以使用绝对模式（八进制数字模式），符号模式指定文件的权限。使用权限:所有使用者who的符号模式表who 用户类型 说明 u user 文件所有者 g group 文件所有者所在组 o others 所有其他用户 a all .

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年5月27日
  • 域名转接公告

    域名转接公告

    域名转接公告

    全栈程序员-用户IM 全栈程序员-用户IM
    2021年7月25日
  • 解决windows10下无法安装.net framework 3.5，错误代码0x8024401C

    解决windows10下无法安装.net framework 3.5，错误代码0x8024401C

    解决windows10下无法安装.net framework 3.5，错误代码0x8024401Cwindowsupdateerror0x8024401c不想改bug2018-09-2015:28:164478已收藏3展开Error0x8024401c以系統管理員身分執行命令提示字元，然後執行下列三行指令：netstopwuauservregdeleteHKEY_LOCAL_MACHINE\SOFTWARE\Policies\Microsoft\Windows\WindowsUpdatenetstartwuauserv操作如下：C:\Windows\s

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年4月29日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号