美文网首页程序员Java学习笔记
红黑树的原理和常见操作

红黑树的原理和常见操作

作者: maskwang520 | 来源:发表于2018-01-13 17:02 被阅读374次
    1. 概述

    在jdk1.8中,HashMap和ConcurrentHashMap中都采用了红黑树这一数据结构。即当链表达到一定的长度后,就把链表转化成红黑树。这其中主要利用了红黑树的良好性质,不管你节点怎样,他始终保持查找时间复杂度为O(logn)。这样的性质相对于链表在长度很长的时候有很大的优势。O(logn)<O(lgn)

    2. 红黑树的定义
    • 每个结点要么是红的,要么是黑的。
    • 根结点是黑的。
    • 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。
    • 如果一个结点是红的,那么它的俩个儿子都是黑的。
    • 对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。
      一棵典型的红黑树如下:


      红黑树
    3. 红黑树的插入

    在这里,默认你熟悉二叉查找树的结构,以及他的插入和删除操作。红黑树本质上是一棵二叉查找树。
    对红黑树的插入,我们先按二叉查找树去插入,然后对对树做调整,使其满足红黑树的五条定义。(这是因为你插入会破坏其中的规则)
    二叉查找树的插入伪代码如下:

    RB-INSERT(T, z)  
     1  y ← nil[T]  
     2  x ← root[T]  
     3  while x ≠ nil[T]  
     4      do y ← x  
     5         if key[z] < key[x]  
     6            then x ← left[x]  
     7            else x ← right[x]  
     8  p[z] ← y  
     9  if y = nil[T]  
    10     then root[T] ← z  
    11     else if key[z] < key[y]  
    12             then left[y] ← z  
    13             else right[y] ← z  
    14  left[z] ← nil[T]  
    15  right[z] ← nil[T]  
    16  color[z] ← RED  
    17  RB-INSERT-FIXUP(T, z)  
    

    可以看出,RB-INSERT(T, z)前面的第1-13行代码基本就是二叉查找树的插入代码,然后第14-16行代码把z的左孩子、右孩子都赋为叶结点nil,再把z结点着为红色,最后为保证红黑性质在插入操作后依然保持,调用一个辅助程序RB-INSERT-FIXUP来对结点进行重新着色,并旋转。
    换言之

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

    但当遇到下述3种情况时:

    • 插入修复情况1:如果当前结点的父结点是红色且祖父结点的另一个子结点(叔叔结点)是红色
    • 插入修复情况2:当前结点的父结点是红色,叔叔结点是黑色,当前结点是其父结点的右子
    • 插入修复情况3:当前结点的父结点是红色,叔叔结点是黑色,当前结点是其父结点的左子
    3.1 插入修复情况1:当前结点的父结点是红色且祖父结点的另一个子结点(叔叔结点)是红色。

    插入的伪代码如下:

     1 while color[p[z]] = RED  
     2     do if p[z] = left[p[p[z]]]  
     3           then y ← right[p[p[z]]]  
     4                if color[y] = RED  
     5                   then 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  
    

    如下面两个调整前的图和调整之后的图做对比。其中4为新添加的点。它的父节点为红色,叔叔节点为红色。那么调整就是把4的叔叔节点变为黑色(8节点),4的祖父节点变为红色,把当前结点指向祖父结点,从新的当前结点重新开始算法(7节点变为N)。


    3.1.1 调整前的树
    3.1.2 调整后的红黑树
    3.2 插入修复情况2:当前结点的父结点是红色,叔叔结点是黑色,当前结点是其父结点的右子
     9                   else if z = right[p[z]]
    10                           then z ← p[z]                       ▹ Case 2
    11                                LEFT-ROTATE(T, z)              ▹ Case 2
    

    调整之前的图如3.1.2,经过调整后得到如下的图。过程是当前结点的父结点做为新的当前结点,以新当前结点为支点左旋.


    3.2.2 调整之后的树
    3.3 插入修复情况3:当前结点的父结点是红色,叔叔结点是黑色,当前结点是其父结点的左子
    12                           color[p[z]] ← BLACK                 ▹ Case 3
    13                           color[p[p[z]]] ← RED                ▹ Case 3
    14                           RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3
    

    调整过程是把父结点变为黑色,祖父结点变为红色,在祖父结点为支点右旋。最后,把根结点涂为黑色,整棵红黑树便重新恢复了平衡。调整之前的图如3.2.2,经过调整后得到下图。


    3.3.2调整后的图
    3. 红黑树的删除

    在这里默认你熟悉二叉查找树的删除操作。

    下面我们用一个分析技巧:我们从被删结点后来顶替它的那个结点开始调整,并认为它有额外的一重黑色。这里额外一重黑色是什么意思呢,我们不是把红黑树的结点加上除红与黑的另一种颜色,这里只是一种假设,我们认为我们当前指向它,因此空有额外一种黑色,可以认为它的黑色是从它的父结点被删除后继承给它的,它现在可以容纳两种颜色,如果它原来是红色,那么现在是红+黑,如果原来是黑色,那么它现在的颜色是黑+黑。有了这重额外的黑色,原红黑树性质5就能保持不变。现在只要恢复其它性质就可以了,做法还是尽量向根移动和穷举所有可能性。"--saturnman。
    如果是以下情况,恢复比较简单:

    • 当前结点是红+黑色
      解法,直接把当前结点染成黑色,结束此时红黑树性质全部恢复。
    • 当前结点是黑+黑且是根结点, 解法:什么都不做,结束。

    下面4中特殊情况

    • 删除修复情况1:当前结点是黑+黑且兄弟结点为红色(此时父结点和兄弟结点的子结点分为黑)
    • 删除修复情况2:当前结点是黑加黑且兄弟是黑色且兄弟结点的两个子结点全为黑色
    • 删除修复情况3:当前结点颜色是黑+黑,兄弟结点是黑色,兄弟的左子是红色,右子是黑色
    • 删除修复情况4:当前结点颜色是黑-黑色,它的兄弟结点是黑色,但是兄弟结点的右子是红色,兄弟结点左子的颜色任意

    4.1 删除修复情况1:当前结点是黑+黑且兄弟结点为红色(此时父结点和兄弟结点的子结点分为黑)。
    解法:把父结点染成红色,把兄弟结点染成黑色,之后重新进入算法(我们只讨论当前结点是其父结点左孩子时的情况)。此变换后原红黑树性质5不变,而把问题转化为兄弟结点为黑色的情况(注:变化前,原本就未违反性质5,只是为了把问题转化为兄弟结点为黑色的情况)。

    变化前
    变化后

    4.2 删除修复情况2:当前结点是黑加黑且兄弟是黑色且兄弟结点的两个子结点全为黑色。

    解法:把当前结点和兄弟结点中抽取一重黑色追加到父结点上,把父结点当成新的当前结点,重新进入算法。(此变换后性质5不变)。伪代码如下。

    //调用RB-DELETE-FIXUP(T, x) 的9-11行代码
    9                if color[left[w]] = BLACK and color[right[w]] = BLACK
    10                   then color[w] ← RED                          ▹  Case 2
    11                        x p[x]                                  ▹  Case 2
    

    4.3 删除修复情况3:当前结点颜色是黑+黑,兄弟结点是黑色,兄弟的左子是红色,右子是黑色。
    解法:把兄弟结点染红,兄弟左子结点染黑,之后再在兄弟结点为支点解右旋,之后重新进入算法。此是把当前的情况转化为情况4,而性质5得以保持。伪代码如下

    //调用RB-DELETE-FIXUP(T, x) 的第12-16行代码
    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
    

    4.4 删除修复情况4:当前结点颜色是黑-黑色,它的兄弟结点是黑色,但是兄弟结点的右子是红色,兄弟结点左子的颜色任意。
    解法:把兄弟结点染成当前结点父结点的颜色,把当前结点父结点染成黑色,兄弟结点右子染成黑色,之后以当前结点的父结点为支点进行左旋,此时算法结束,红黑树所有性质调整正确。代码如下

    //调用RB-DELETE-FIXUP(T, x) 的第17-21行代码
    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
    

    以上就是红黑树的结构和性质,对于面试和源码的理解很有帮助。

    参考文章:
    教你透彻了解红黑树

    相关文章

      网友评论

        本文标题:红黑树的原理和常见操作

        本文链接:https://www.haomeiwen.com/subject/vgmcoxtx.html