2-3树与红黑树

短命女 2023-05-30 09:20 9阅读 0赞

### 前言 ###

红黑树直接看有点懵，涂上颜色，颜色转换，状态调整，说实话，一上来这么弄，我都不想看，有些东西你会知道是这么回事，但是你不清楚为什么这么做？为什么要涂上颜色？我自己也不太喜欢死记硬背，感觉很伤脑子，而且过一段时间就忘记了，这不是我的风格。

### 2-3 树 ###

2-3 树 同2-3-4树 是差不多的概念，这也是一种平衡树，但有不一样的地方：

*  一般平衡树一个节点只能存一个key，这种树的节点可以有两个key，有两个key的节点称为3节点，有一个key的节点称为2节点，这里不是说 2个节点，就叫2节点。下图左边是2节点，右边是3节点。  
    ![2节点][2]![3节点][3]
 *  2节点只有一个左子树、一个右子树，3节点有三个子树，分别是左子树、中间子树、一个右子树。
 *  平衡树都有 节点旋转操作，因为要保证左子树、右子树 高度不能相差1,2-3树也有，但是它的旋转会复杂一些

同样 2-3树的插入、删除也会更复杂，大致的思路是：

*  如果是2节点，就变成3结点
 *  如果是3结点，3结点成4节点，4节点重新分配节点

删除的话就复杂很多，当然被篇文章就不仔细讨论这些了，他的优点包括平衡二叉树的所有优点：

*  查找时间复杂度： l o g ( n ) log(n) log(n)，最坏的情况下降低了树的高度，比二叉平衡树可以容纳更多的key

当然缺点也非常致命：

*  查找和插入操作的实现需要大量的代码，而且它们所产生的额外开销可能会使算法比标准的二叉查找树更慢

所以2-3树在实际中很少使用。由于其需要大量的节点变换（从2-节点到3-节点到4-节点甚至到5-节点…），这些变换在实际代码中是很复杂的。所以现在几乎没有2-3树的具体实现。  
但是由于2-3树的变化十分直观，因此前人在2-3树的理论基础上发明了红黑树。

### 2-3-4树与红黑树 ###

2-3-4树 与 2-3树唯一的差别就在于多了一个4结点，容纳3个key，其他差别不太大，红黑树其实更类似2-3-4树：

*  一个黑结点 如果有 两个红结点，就类似一个4结点
 *  一个黑结点如果有一个红结点，就类似一个3结点  
    2-3树 和 2-3-4树 虽然很方便，但是上一节中也提到代码会非常复杂，于是改善了一下，提出了红黑树，红黑树用红链接表示2-3树中另类的3-结点，统一了树中的结点类型，使代码实现简单化，又不破坏其高效性，用颜色来做一个标识。

有一些博客里讲解了红黑树的几个特征性质，当然我们也提一下，虽然这些特征比较麻烦：

*  1、根结点是黑色
 *  2、没有相邻的红结点，意思就是父结点是红结点，子结点就不能是红结点，红结点的子结点必须是黑结点
 *  3、从结点（包括根）到其任何后代NULL节点（叶子结点下方挂的两个空节点，并且认为他们是黑色的）的每条路径都具有相同数量的黑色节点

这是约束一颗红黑树的条件，也就是符合这些条件就是红黑树，其实还有一点：新插入的结点都是红色节点。红色节点插入树中之后，根据约束条件来更改颜色、调整树结构。

### 红黑树插入结点 ###

插入相对还是比较简单的。同样结点数目构成的红黑树有很多种，这些不同的情况都可以通过染色、平衡来实现，那么问题来了？你依据什么样的准则来染色、调整？因为很多种染色、平衡操作都可以使得不平衡的红黑树变得平衡，那么你设计的调整准则是什么？

看到一篇文章讲解插入操作，讲解的还是比较好的，插入主要关注三种情况，这三种情况会因为一开始插入，或者是因为调整之后出现的情况，并且并不是调整一次就结束，会反复调整，我们先看下伪代码：

RB-INSERT-FIXUP（T,z）
     1  while color[p[z]] = RED  
     2      if p[z] = left[p[p[z]]]  
     3                y ← right[p[p[z]]]  
     4                if color[y] = RED  
     5                   color[p[z]] ← BLACK                    ▹ Case 1  
     6                   color[y] ← BLACK                       ▹ Case 1  
     7                   color[p[p[z]]] ← RED                   ▹ Case 1  
     8                   z ← p[p[z]]                            ▹ Case 1  
     9                 else  if z = right[p[z]]  
    10                           z ← p[z]                       ▹ Case 2  
    11                           LEFT-ROTATE(T, z)              ▹ Case 2  
    12                 else   
    13                     color[p[z]] ← BLACK                 ▹ Case 3  
    14                     color[p[p[z]]] ← RED                ▹ Case 3  
    15                     RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3  
    16      else (same as then clause   with "right" and "left" exchanged)  
    17  color[root[T]]  ←  BLACK

代码可能有点难懂，参数说明：z是插入节点的指针，T是树。总结一下代码流程：

while  ( z节点父节点 是红色 )：
             if  z节点的父节点  ==  z节点 祖父节点的左节点：
                    y = z节点 祖父节点右节点
                    if y 颜色 == red
                           第一种情况调整                                     ▹ 注意
                           z = z节点的祖父节点
                     else if z是右孩子    #  这也说明 y 颜色是黑色
                               z = z节点的父节点
                               第二种情况调整                                 ▹ 注意
                     else  # z是左孩子 ,y 颜色是黑色
                            第三种情况调整                                    ▹ 注意
             else # 隐藏含义： z节点的父节点  ==  z节点 祖父节点的右节点
                  # 剩下的操作跟上面一样，只不过 左右互换一下
    
    最后将 根节点 颜色 改为 黑色

注意几点：

*  调整一共有三种情况
 *  这是一个while 循环，三种情况 反复调整，一直都 z节点 的父节点不是红色
 *  最后一步：将根节点置位黑色

那么调整的三种情况是怎么样的呢？图解如下：  
![format_png][]  
讲解：

*  红色节点是插入节点：这句话是说 红色圈起来的节点，节点的圆圈是红色笔画的，
 *  调整后， z z z被我用红色字体标出来了，这就是下一个循环中用的 z z z节点。
 *  第一种情况：变色
 *  第二种情况：左旋转
 *  第三种情况：父节点变黑，祖父节点变红，变色后 右旋转

看的时候注意几个问题：

*  第一种情况下：为什么根节点是红色？这不就不符合红黑树定义了嘛？  
    因为有最后的一个步骤将根节点置位黑色，所以其实也不算是一种失误
 *  第二种情况、第三种情况 下 原有结构也是有问题的？  
    因为我们看到了的只是一部分结构，单纯的这种树结构是不会出现的，因为根本不符合红黑树的定义，建议看下[教你透彻了解红黑树][Link 1]。里面有完整的树结构，第二种、第三种其中一部分结构，并且也有可能是调整之后出现的情况
 *  第二种情况、第三种情况的联系  
    如果你仔细看，你会发现第二种情况跟第三种情况是连续的，第二种情况之后就开始执行第三种情况，
 *  第三种情况之后好像出现了不平衡的情况  
    第三种情况是先变色，再旋转，但其实第三种情况的初始状态就不会存在，也就是不存在单纯的第三种情况的初始状态，它只是红黑树的一部分。完整的树下它是平衡的。
 *  出现连续的两个红色节点的情况，比如第三种情况，有点像2-3-4树  
    红-红-黑 就像 一个 4结点，只不过在2-3-4树中是一个结点，在红黑树中要变色、调整，使得平衡。
 *  第三种情况之后，似乎就结束调整了  
    没错，我们看图中第三种情况调整之后， z z z的节点位置，发现它不满足while循环的条件，也就会跳出循环，所以可以认为这是最后的一个步骤。
 *  为什么是这三种情况？  
    很奇怪的一点就是为什么是这三种情况？这三种情况似乎是可以连续起来的，2、3、1这样的顺序，不过也只是猜测，各种情况分析之后其实也就只有这几种情况需要调整了，具体的还要继续研究一下。

插入的操作大致是这样，一些不需要调整的情况如下：

*  插入的是根结点，因为原树是空树，此情况只会违反性质2，所以直接把此结点涂为黑色。
 *  如果插入的结点的父结点是黑色，由于此不会违反性质2和性质4，红黑树没有被破坏，所以此时也是什么也不做。

三种情况的另一种换言之，可以加强大家认识：

*  情况1：如果当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色
 *  情况2：当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的右子
 *  情况3：当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的左子

左右反过来的情况是一样的，处理过程也是类似的，这里不赘述。

TreeSet treeSet = new TreeSet();
            treeSet.add(4);
            treeSet.add(1);
            treeSet.add(2);
            treeSet.add(3);
            treeSet.add(5);
            treeSet.add(6);
            treeSet.add(7);

以上代码是我用来测试的代码，通过debug来查看了每个节点的颜色，得到了最终树的形状：  
![format_png 1][]  
我比较奇怪，为啥 这个不是其他结构，因为4也可以作为根节点，得到一个更加平衡的二叉树，于是我猜想是不是跟节点插入顺序有关，于是我重新弄了一个代码：

TreeSet treeSet = new TreeSet();
            treeSet.add(4);
            treeSet.add(1);
            treeSet.add(5);
            treeSet.add(2);
            treeSet.add(6);
            treeSet.add(3);
            treeSet.add(7);

我debug看了一下，还是结构发生了变化，  
![format_png 2][]  
插入的顺序跟最终的结果关系很大，有可能本来就很平衡，不需要调整。

#### 红黑树 删除结点 ####

删除结点 一共有6种情况，真是复杂，慢慢来分析，这里会先讲解删除树节点的大致操作，然后来了解一下二叉树删除节点之后的调整过程，定一个基调，用来分析红黑树的删除：

*  1、叶子节点删除，直接删除
 *  2、只有一个子节点的节点，删除该节点，子节点替代上去
 *  3、有两个子节点的节点删除，选择左子节点的最大节点来替代，默认这么做，也可以选择右边最小子节点。  
    不过红黑树是先删除再调整树结构，调整树结构时会以删除节点的位置出发来做调整操作。  
    所以如果是红黑树的话，应该怎么做呢？
 *  当前结点是红节点
 *  删除后，替代节点如果是黑色节点，且是根节点，则直接删除

这两种情况比较好弄，但是不太好理解，第一种比较好理解，第二种不太好理解，因为极有可能会造成左子树黑色结点少了一个，这样，根节点到叶子节点的路径上黑色节点数目不太一致，这一点先保留意见，之后来测试一下场景。  
还有另外四种情况，代码先上：

1 while x ≠ root[T] and color[x] = BLACK  
     2     do if x = left[p[x]]  
     3           then w ← right[p[x]]  
     4                if color[w] = RED  
     5                   then color[w] ← BLACK                        ▹  Case 1  
     6                        color[p[x]] ← RED                       ▹  Case 1  
     7                        LEFT-ROTATE(T, p[x])                    ▹  Case 1  
     8                        w ← right[p[x]]                         ▹  Case 1  
     9                if color[left[w]] = BLACK and color[right[w]] = BLACK  
    10                   then color[w] ← RED                          ▹  Case 2  
    11                        x ← p[x]                                ▹  Case 2  
    12               else if color[right[w]] = BLACK  
    13                           then color[left[w]] ← BLACK          ▹  Case 3  
    14                                color[w] ← RED                  ▹  Case 3  
    15                                RIGHT-ROTATE(T, w)              ▹  Case 3  
    16                                w ← right[p[x]]                 ▹  Case 3  
    17                         color[w] ← color[p[x]]                 ▹  Case 4  
    18                         color[p[x]] ← BLACK                    ▹  Case 4  
    19                         color[right[w]] ← BLACK                ▹  Case 4  
    20                         LEFT-ROTATE(T, p[x])                   ▹  Case 4  
    21                         x ← root[T]                            ▹  Case 4  
    22        else (same as then clause with "right" and "left" exchanged)  
    23 color[x] ← BLACK

4种情况主要有：

*  Case 1：当前结点是黑色，且兄弟结点为红色(此时父结点和兄弟结点的子结点分为黑)  
    下图中A节点就是当前节点，把父结点染成红色，把兄弟结点染成黑色，之后重新进入算法。此变换前、后 原红黑树性质5不变，而把问题转化为兄弟结点为黑色的情况。![format_png 3][]
 *  Case 2：当前结点是黑色，且兄弟是黑色且兄弟结点的两个子结点全为黑色  
    这里要注意，调整后会将B节点作为当前节点，然后进行插入调整。所以下面的图可以看出其实是不平衡的，删除调整之后还需要插入调整。  
    ![format_png 4][]
 *  Case 3：当前结点颜色是黑，兄弟结点是黑色，兄弟的左子是红色，右子是黑色  
    把兄弟结点染红，兄弟左子结点染黑，之后再在兄弟结点为支点解右旋，之后重新进入算法，这主要是把当前情况转化为情况4，然后通过插入调整来使得满足性质：根节点到所有叶子节点路径中黑色节点数目一致。这里有个疑问？插入调整的当前节点是哪个？  
    ![format_png 5][]
 *  Case 4：当前结点颜色是黑，它的兄弟结点是黑色，但是兄弟结点的右子是红色，兄弟结点左子的颜色任意  
    把兄弟结点染成当前结点父结点的颜色，把当前结点父结点染成黑色，兄弟结点右子染成黑色，之后以当前结点的父结点为支点进行左旋，然后进行插入调整，  
    ![format_png 6][]

其实通过上述的情况来看，这里的删除调整不是一下子就结束了，也要进行插入调整，两个调整之后还要进行多次调整，最终可以得到一颗符合条件的平衡树。  
来看一个代码实现：

TreeSet treeSet = new TreeSet();
            treeSet.add(4);
            treeSet.add(1);
            treeSet.add(5);
            treeSet.add(2);
            treeSet.add(6);
            treeSet.add(3);
            treeSet.add(7);
    
    
            treeSet.remove(2);

通过debug发现删除前后的差别是，删除前：  
![format_png 2][]  
删除后：  
![format_png 7][]

### 红黑树 业务总结 ###

目前树结构的有：

*  二叉查找树（BST）  
    英文Binary Sort Tree，查找、插入、删除的时间复杂度为 O ( l o g N ) O(logN) O(logN)，时间复杂度就变味了 O ( N ) O(N) O(N)
 *  AVL 树  
    平衡二叉树全称平衡二叉搜索树，也叫AVL树。是一种自平衡的树。它要求左子树、右子树的高度相差不超过1，如果超过1了就会执行调整算法来调整数结构。

红黑树也是一种AVL树，红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。

实际应用中，根据业务特点来选择：

*  若搜索的次数远远大于插入和删除，那么选择AVL
 *  如果搜索，插入删除次数几乎差不多，应该选择RB

### 参考博客 ###

[漫画算法：什么是红黑树？（通俗易懂）][Link 2]  
[2-3树到红黑树][2-3]  
[红黑树从头至尾插入和删除结点的全程演示图][Link 3]  
[RedBlack.pdf][]

[2]: https://img-blog.csdnimg.cn/20191109143631374.png
[3]: https://img-blog.csdnimg.cn/20191109143605280.png
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL0tsYXVzemhhby9waWN0dXJlL21hc3Rlci9waWN0dXJlL3JlZEJsYWNrLyVFNyVCQSVBMiVFOSVCQiU5MSVFNiVBMCU5MSVFNiU4RiU5MiVFNSU4NSVBNSVFNiU5MyU4RCVFNCVCRCU5Qy10aHIuanBn?x-oss-process=image/format,png
[Link 1]: https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL0tsYXVzemhhby9waWN0dXJlL21hc3Rlci9waWN0dXJlL3JlZEJsYWNrLyVFNyVCQSVBMiVFOSVCQiU5MSVFNiVBMCU5MS10cmVlU2V0LkpQRw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL0tsYXVzemhhby9waWN0dXJlL21hc3Rlci9waWN0dXJlL3JlZEJsYWNrLyVFNiU4RiU5MiVFNSU4NSVBNS1vbmUuSlBH?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL0tsYXVzemhhby9waWN0dXJlL21hc3Rlci9waWN0dXJlL3JlZEJsYWNrLyVFNiU4MyU4NSVFNSU4NiVCNW9uZS5wbmc?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL0tsYXVzemhhby9waWN0dXJlL21hc3Rlci9waWN0dXJlL3JlZEJsYWNrLyVFNiU4MyU4NSVFNSU4NiVCNXR3by5wbmc?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL0tsYXVzemhhby9waWN0dXJlL21hc3Rlci9waWN0dXJlL3JlZEJsYWNrLyVFNiU4MyU4NSVFNSU4NiVCNXRoci5wbmc?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL0tsYXVzemhhby9waWN0dXJlL21hc3Rlci9waWN0dXJlL3JlZEJsYWNrLyVFNiU4MyU4NSVFNSU4NiVCNWZvci5wbmc?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL0tsYXVzemhhby9waWN0dXJlL21hc3Rlci9waWN0dXJlL3JlZEJsYWNrLyVFNSU4OCVBMCVFOSU5OSVBNC0lRTklQkIlOTElRTglOEElODIlRTclODIlQjklRTYlOTMlOEQlRTQlQkQlOUMuSlBH?x-oss-process=image/format,png
[Link 2]: http://www.ishenping.com/ArtInfo/313445.html
[2-3]: https://www.imthebest.top/interview/2-3%E6%A0%91%E5%88%B0%E7%BA%A2%E9%BB%91%E6%A0%91.html
[Link 3]: https://blog.csdn.net/v_july_v/article/details/6284050
[RedBlack.pdf]: https://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf