数据结构与算法分析（十一）--- 平衡二叉树 + 红黑树

文章目录

一、什么是平衡二叉查找树

前篇博客介绍的二叉查找树是最常用的一种二叉树，它支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度是 O(logn)。不过，二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于 log2n 的情况，从而导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间复杂度会退化到 O(n)。前篇博客也说了，要解决这个复杂度退化的问题，我们需要设计一种平衡二叉查找树，什么是平衡二叉查找树呢？

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看，前面介绍的完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。
平衡二叉树
平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。

1.1 AVL如何维护二叉树的平衡

最先被发明的平衡二叉查找树是AVL 树，AVL树的名字来源于它的发明作者G.M. Adelson-Velsky 和 E.M. Landis，它严格符合上面介绍的平衡二叉查找树的定义，即任何节点的左右子树高度之差（平衡因子）的绝对值不超过 1 ，是一种高度平衡的二叉查找树。

只要能随时保证每个结点平衡因子的绝对值不超过1，AVL树的高度就始终能保持O(logn)级别，由于需要对每个结点都得到平衡因子，因此需要在树的结点结构中加入一个变量height，用来记录以当前结点为根结点的子树的高度：

// datastruct\binary_tree.c

struct BinaryTree_Node{
    DataType                data;
    struct BinaryTree_Node *LeftChild;
    struct BinaryTree_Node *RightChild;
    int                     height;
};
typedef struct BinaryTree_Node   *pTreeNode;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

树结点结构中有了高度信息，就可以实现获取当前结点 T 所在子树的当前高度函数getHeight()和平衡因子函数getBalanceFactor()如下：

// datastruct\binary_tree.c

int getHeight(pTreeNode T)
{
    if(T == NULL)
        return 0;

    return T->height;
}

int getBalanceFactor(pTreeNode T)
{   
    if(T == NULL)
        return 0;

    return getHeight(T->LeftChild) - getHeight(T->RightChild);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

显然，结点 T 所在子树的高度等于其左子树的高度与右子树的高度的较大值加 1 ，因此可以实现更新当前结点 T 的高度信息的函数如下：

// datastruct\binary_tree.c

void updateHeight(pTreeNode T)
{
    if(T == NULL)
        return;
    
    T->height = max(getHeight(T->LeftChild), getHeight(T->RightChild)) + 1;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

接下来看AVL树如何维护二叉树的平衡？假设现在已经有一棵平衡二叉树，那么在往其中插入一个结点时，一定会有结点的平衡因子发生变化，此时可能会有结点的平衡因子的绝对值大于 1 （这些平衡因子的绝对值为2），这样以该结点为根结点的子树（最小不平衡子树）就是失衡的，需要进行调整。显然，只有在从根结点到该插入结点的路径上的结点才可能发生平衡因子变化，因此只需对这条路径上失衡的结点进行调整，可以证明，只要把最靠近插入结点的失衡结点（最低不平衡结点）调整到平衡，路径上的所有结点就都会平衡。

根据新插入的结点与最低不平衡结点的位置关系，可以分为左左情况（LL）、右右情况（RR型）、左右情况（LR型）和右左情况（RL型）4种类型分别处理。左左情况指的是最低不平衡结点Root的平衡因子为2（即左子树高度比右子树大2），且Root左孩子的平衡因子为 1 ；右左情况指的是Root的平衡因子为 -2 ，且Root右孩子的平衡因子为 1 ；其它情况依次类推即可。这四种类型的调整方法如下：
AVL树平衡调整过程
从上图可以看出，当新插入一个结点打破原来AVL树的平衡后，AVL树可通过左、右旋转重新实现平衡，其中LL型与RR型两种情况只需要进行一次旋转即可，LR型与RL型两种情况则需要进行两次旋转才能恢复平衡。

1.2 左旋与右旋操作

从上面的分析可知，二叉树的平衡化有两大基础操作： 左旋和右旋。左旋，即是逆时针旋转；右旋，即是顺时针旋转。这种旋转在整个平衡化过程中可能进行一次或多次，这两种操作都是从失去平衡的最小子树根结点(最低不平衡结点)开始的。

  • 左旋操作

左旋操作过程图
上图是一个二叉查找树，其中 ☆ 是结点A的左子树，◆ 和 ◇ 分别是结点B的左子树和右子树。当进行左旋操作时，结点 A 与结点B 进行了“父子转换”，原先结点 B 是结点 A 的右子结点，转换后结点 A 是结点 B 的左子结点，原先结点 B 的左子树 ◆ 怎么办呢？考虑到结点 A、B、◆ 的元素值满足 A < ◆ < B，所以让 ◆ 成为 A 的右子树即可。

假设指针 root 指向结点 A ，指针 tmp 指向结点 B ，于是调整过程可以分为三个步骤：

  1. 让 B 的左子树 ◆ 成为 A 的右子树；
  2. 让 A 成为 B 的左子树；
  3. 将根结点设置为结点 B 。

按照上述逻辑，左旋操作的实现代码如下：

// datastruct\binary_tree.c

pTreeNode LeftRotation(pTreeNode T)
{
    pTreeNode temp = T->RightChild;
    T->RightChild = temp->LeftChild;
    temp->LeftChild = T;

    updateHeight(T);
    updateHeight(temp);

    return temp;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 右旋操作

右旋操作过程
右旋操作跟左旋是对称的过程，实现步骤也跟左旋基本相同，也是先移动 ◆ ，再改变 A 和 B 的父子关系，调整步骤如下：

  1. 让 A 的右子树 ◆ 成为 B 的左子树；
  2. 让 B 成为 A 的右子树；
  3. 将根结点设定为结点 A。

按照上述逻辑，右旋操作的实现代码如下：

// datastruct\binary_tree.c

pTreeNode RightRotation(pTreeNode T)
{
    pTreeNode temp = T->LeftChild;
    T->LeftChild = temp->RightChild;
    temp->RightChild = T;

    updateHeight(T);
    updateHeight(temp);

    return temp;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

1.3 实现平衡的四种情况

有了左旋与右旋操作的实现代码，接着前面继续分析因插入新结点而失去平衡的AVL树如何恢复平衡，也即根据新插入的结点与最低不平衡结点的位置关系，逐个分析前面提到的四种类型调整操作的实现。

  • LL型：最低不平衡结点 A 的平衡因子为 2 ，且其左子树 B 的平衡因子为 1

LL型调整示意图

  • RR型：最低不平衡结点 A 的平衡因子为 -2 ，且其右子树 B 的平衡因子为 -1

RR型调整示意图

  • LR型：最低不平衡结点 A 的平衡因子为 2 ，且其右子树 B 的平衡因子为 -1

LR型调整示意图

  • RL型：最低不平衡结点 A 的平衡因子为 -2 ，且其右子树 B 的平衡因子为 1

RL型调整示意图
将上述AVL树插入的四种类型汇总如下（BF表示平衡因子）：
AVL树插入情况汇总
根据上表编写AVL树恢复平衡的实现代码如下：

// datastruct\binary_tree.c

pTreeNode TreeRebalance(pTreeNode T)
{
    if(T == NULL)
        return NULL;
    
    updateHeight(T);
    int fb_root = getBalanceFactor(T);
    int fb_left = getBalanceFactor(T->LeftChild);
    int fb_right = getBalanceFactor(T->RightChild);
	// LL型
    if(fb_root > 1 && fb_left > 0)
        return RightRotation(T);
    // LR型
    else if(fb_root > 1 && fb_left < 0){
        T->LeftChild = LeftRotation(T->LeftChild);
        return RightRotation(T);
     // RR型
    }else if(fb_root < -1 && fb_right < 0)
        return LeftRotation(T);
    // RL型
    else if(fb_root < -1 && fb_right > 0){
        T->RightChild = RightRotation(T->RightChild);
        return LeftRotation(T);
    }else
        return T;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

有了恢复平衡的实现代码，对前一篇介绍的二叉查找树的插入代码稍加修改就可以支持自平衡操作，修改后的AVL树插入实现代码如下：

// datastruct\binary_tree.c

pTreeNode AVL_Insert(pTreeNode T, DataType x)
{
    if(T == NULL)
    {
        // create and return a one-node tree
        T = malloc(sizeof(struct BinaryTree_Node));
        if(T == NULL){
            printf("Out of space!");
        }else{
            T->data = x;
            T->LeftChild = T->RightChild = NULL;
            T->height = 1;
        }
        return T;
    }

    if(x < T->data)
        T->LeftChild = AVL_Insert(T->LeftChild, x);
    else if(x > T->data)
        T->RightChild = AVL_Insert(T->RightChild, x);    
    // else x is in the tree already, we will do nothing
    
    T = TreeRebalance(T);
    return T;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

由于对已平衡的AVL树，插入一个新结点，平衡因子绝对值不会大于 2，只需要进行一次平衡调整即可恢复平衡，所以只需要在二叉查找树插入操作代码最后增加一行平衡调整操作即可。

下面给出一个示例程序，验证下前面实现的AVL树操作实现代码是否有bug，示例代码如下：

// datastruct\binary_tree.c

#define DataType int
#define max(a, b)   ((a) > (b)) ? (a) : (b)

struct BinaryTree_Node{
    DataType                data;
    struct BinaryTree_Node *LeftChild;
    struct BinaryTree_Node *RightChild;
    int                     height;
};
typedef struct BinaryTree_Node   *pTreeNode;

int getHeight(pTreeNode T);
int getBalanceFactor(pTreeNode T);
void updateHeight(pTreeNode T);
pTreeNode LeftRotation(pTreeNode T);
pTreeNode RightRotation(pTreeNode T);
pTreeNode TreeRebalance(pTreeNode T);
pTreeNode AVL_Insert(pTreeNode T, DataType x);
void preOrder(pTreeNode T);
void inOrder(pTreeNode T);
void postOrder(pTreeNode T);

int main(void)
{
    pTreeNode T_AVL = NULL;

    T_AVL = AVL_Insert(T_AVL, 1);
    T_AVL = AVL_Insert(T_AVL, 2);
    T_AVL = AVL_Insert(T_AVL, 3);
    T_AVL = AVL_Insert(T_AVL, 4);
    T_AVL = AVL_Insert(T_AVL, 5);
    T_AVL = AVL_Insert(T_AVL, 6);
    T_AVL = AVL_Insert(T_AVL, 7);
    T_AVL = AVL_Insert(T_AVL, 8);
    T_AVL = AVL_Insert(T_AVL, 9);

    printf("preOrder: ");
    preOrder(T_AVL);
    printf("\n");
    printf("inOrder: "); 
    inOrder(T_AVL);
    printf("\n");
    printf("postOrder: ");
    postOrder(T_AVL);
    printf("\n");
    
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

上面示例程序的运行结果如下：
AVL树插入程序执行结果
从二叉树的三种遍历可以构建唯一的二叉树结构，可以发现构建的二叉树结构满足AVL树的平衡条件。如果换成前篇介绍的二叉查找树的插入操作，则该二叉查找树将会退化为链表。AVL树的删除操作比较复杂，本篇的重点是介绍二叉树的平衡调整与红黑树实现原理，这里就不再展开介绍AVL删除操作的实现了。

二、什么是红黑树

如果你有一定的开发经验，你会发现，在工程中，很多用到平衡二叉查找树的地方都会用红黑树。为什么工程中都喜欢用红黑树，而不是其他平衡二叉查找树比如AVL树呢？

发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

所以，如果我们现在设计一个新的平衡二叉查找树，只要树的高度不比 log2n 大很多（比如树的高度仍然是对数级的），尽管它不符合我们前面介绍的严格平衡二叉查找树（比如AVL树）的定义，但我们仍然可以说，这是一个合格的平衡二叉查找树。

AVL 树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL 树为了维持这种高度的平衡，就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价就有点高了。

红黑树只是做到了近似平衡，并不是严格的平衡，在维护平衡的成本上，要比 AVL 树要低。所以，红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。那么，什么是红黑树？如何定义一棵红黑树呢？

2.1 如何定义一棵红黑树？

平衡二叉查找树其实有很多，比如 AVL树、Splay Tree（伸展树）、Treap（树堆）等，但是我们提到平衡二叉查找树，听到的基本都是红黑树。它的出镜率甚至要高于“平衡二叉查找树”这几个字，有时候，我们甚至默认平衡二叉查找树就是红黑树，那我们现在就来看看这个“明星树”。

红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树，它的定义是不严格符合平衡二叉查找树的定义的。那红黑树究竟是怎么定义的呢？

顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

  • 节点是红色或者是黑色的；
  • 根节点是黑色的；
  • 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
  • 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
  • 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

这里的第三点要求“叶子节点都是黑色的空节点”，稍微有些奇怪，它主要是为了简化红黑树的代码实现而设置的，下面给出一个红黑树的图示（省略了空的叶子节点）：
红黑树图示

2.2 为什么说红黑树是“近似平衡”的？

前面介绍了，平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以，“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。

前一篇博客介绍了，二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是 log2n，所以如果要证明红黑树是近似平衡的，我们只需要分析，红黑树的高度是否比较稳定地趋近 log2n 就好了。

红黑树的高度不是很好分析，下面一步一步来推导：

  • 首先，如果我们将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高度是多少呢？

红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点的父节点）作为父节点。所以，之前的二叉树就变成了四叉树。
红黑树去掉红色节点
前面红黑树的定义里有这么一条：从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。我们从四叉树中取出某些节点，放到叶节点位置，四叉树就变成了完全二叉树。所以，仅包含黑色节点的四叉树的高度，比包含相同节点个数的完全二叉树的高度还要小。完全二叉树的高度近似 log2n，这里的四叉“黑树”的高度要低于完全二叉树，所以去掉红色节点的“黑树”的高度也不会超过 log2n。

  • 我们现在知道只包含黑色节点的“黑树”的高度，那我们现在把红色节点加回去，高度会变成多少呢？

从上面红黑树的例子和定义看，在红黑树中，红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其它红色节点隔开。红黑树中包含最多黑色节点的路径不会超过 log2n，所以加入红色节点之后，最长路径不会超过 2log2n，也就是说，红黑树的高度近似 2log2n。

所以，红黑树的高度只比高度平衡的 AVL 树的高度（log2n）仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。

三、实现红黑树的基本思想

不知道你有没有玩过魔方？其实魔方的复原解法是有固定算法的：遇到哪几面是什么样子，对应就怎么转几下。你只要跟着这个复原步骤，就肯定能将魔方复原。

实际上，红黑树的平衡过程跟魔方复原非常神似，大致过程就是：遇到什么样的节点排布，我们就对应怎么去调整。只要按照这些固定的调整规则来操作，就能将一个非平衡的红黑树调整成平衡的。

还记得我们前面讲过的红黑树的定义吗？在插入、删除节点的过程中，最后两点要求可能会被破坏，而我们今天要讲的“平衡调整”，实际上就是要把被破坏的第四、第五点恢复过来。怎么恢复红黑树的平衡呢？需要用到前面介绍的AVL树平衡化两大基础操作：左旋与右旋。

3.1 红黑树插入操作的平衡调整

红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。所以，关于插入操作的平衡调整，有这样两种特殊情况，但是也都非常好处理。

  • 如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义；
  • 如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。

除此之外，其他情况都会违背红黑树的定义，于是我们就需要进行调整，调整的过程包含两种基础的操作：左右旋转和改变颜色。

红黑树的平衡调整过程是一个迭代的过程。我们把正在处理的节点叫作关注节点。关注节点会随着不停地迭代处理，而不断发生变化，最开始的关注节点就是新插入的节点。

新节点插入之后，如果红黑树的平衡被打破，那一般会有下面三种情况。我们只需要根据每种情况的特点，不停地调整，就可以让红黑树继续符合定义，也就是继续保持平衡。我们下面依次来看每种情况的调整过程（父节点的兄弟节点叫作叔叔节点，父节点的父节点叫作祖父节点）：

  • CASE 1：如果关注节点是 a，它的叔叔节点 d 是红色，我们就依次执行下面的操作：
  1. 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色；
  2. 将关注节点 a 的祖父节点 c 的颜色设置成红色；
  3. 关注节点变成 a 的祖父节点 c；
  4. 跳到 CASE 2 或者 CASE 3。

红黑树插入case1调整过程

  • CASE 2：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点，我们就依次执行下面的操作：
  1. 关注节点变成节点 a 的父节点 b；
  2. 围绕新的关注节点 b 左旋；
  3. 跳到 CASE 3。

红黑树插入case2调整过程

  • CASE 3：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点，我们就依次执行下面的操作：
  1. 围绕关注节点 a 的祖父节点 c 右旋；
  2. 将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换;
  3. 调整结束。

红黑树插入case3调整过程

3.2 红黑树删除操作的平衡调整

红黑树插入操作的平衡调整还不是很难，但是它的删除操作的平衡调整相对就要难多了。不过原理都是类似的，我们依旧只需要根据关注节点与周围节点的排布特点，按照一定的规则去调整就行了。

删除操作的平衡调整分为两步，第一步是针对删除节点初步调整。初步调整只是保证整棵红黑树在一个节点删除之后，仍然满足最后一条定义的要求，也就是说，每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；第二步是针对关注节点进行二次调整，让它满足红黑树的第四条定义，即不存在相邻的两个红色节点。

3.2.1 针对删除节点初步调整

这里需要注意一下，红黑树的定义中“只包含红色节点和黑色节点”，经过初步调整之后，为了保证满足红黑树定义的最后一条要求，有些节点会被标记成两种颜色，“红 - 黑”或者“黑 - 黑”。如果一个节点被标记为了“黑 - 黑”，那在计算黑色节点个数的时候，要算成两个黑色节点。

在下面的讲解中，如果一个节点既可以是红色，也可以是黑色，在画图的时候，我会用一半红色一半黑色来表示。如果一个节点是“红 - 黑”或者“黑 - 黑”，我会用左上角的一个小黑点来表示额外的黑色。

  • CASE 1：如果要删除的节点是 a，它只有一个子节点 b，那我们就依次进行下面的操作：
  1. 删除节点 a，并且把节点 b 替换到节点 a 的位置，这一部分操作跟普通的二叉查找树的删除操作一样；
  2. 节点 a 只能是黑色，节点 b 也只能是红色，其他情况均不符合红黑树的定义。这种情况下，我们把节点 b 改为黑色；
  3. 调整结束，不需要进行二次调整。

红黑树初步删除case1调整过程

  • CASE 2：如果要删除的节点 a 有两个非空子节点，并且它的后继节点就是节点 a 的右子节点 c，我们就依次进行下面的操作：
  1. 如果节点 a 的后继节点就是右子节点 c，那右子节点 c 肯定没有左子树。我们把节点 a 删除，并且将节点 c 替换到节点 a 的位置。这一部分操作跟普通的二叉查找树的删除操作无异；
  2. 然后把节点 c 的颜色设置为跟节点 a 相同的颜色；
  3. 如果节点 c 是黑色，为了不违反红黑树的最后一条定义，我们给节点 c 的右子节点 d 多加一个黑色，这个时候节点 d 就成了“红 - 黑”或者“黑 - 黑”；
  4. 这个时候，关注节点变成了节点 d，第二步的调整操作就会针对关注节点来做。

红黑树初步删除case2调整过程

  • CASE 3：如果要删除的是节点 a，它有两个非空子节点，并且节点 a 的后继节点不是右子节点，我们就依次进行下面的操作：
  1. 找到后继节点 d，并将它删除，删除后继节点 d 的过程参照 CASE 1；
  2. 将节点 a 替换成后继节点 d；
  3. 把节点 d 的颜色设置为跟节点 a 相同的颜色；
  4. 如果节点 d 是黑色，为了不违反红黑树的最后一条定义，我们给节点 d 的右子节点 c 多加一个黑色，这个时候节点 c 就成了“红 - 黑”或者“黑 - 黑”；
  5. 这个时候，关注节点变成了节点 c，第二步的调整操作就会针对关注节点来做。

红黑树初步删除case3调整过程

3.2.2 针对关注节点进行二次调整

经过初步调整之后，关注节点变成了“红 - 黑”或者“黑 - 黑”节点。针对这个关注节点，我们再分四种情况来进行二次调整。二次调整是为了让红黑树中不存在相邻的红色节点。

  • CASE 1：如果关注节点是 a，它的兄弟节点 c 是红色的，我们就依次进行下面的操作：
  1. 围绕关注节点 a 的父节点 b 左旋；
  2. 关注节点 a 的父节点 b 和祖父节点 c 交换颜色；
  3. 关注节点不变；
  4. 继续从四种情况中选择适合的规则来调整。

红黑树二次删除case1调整过程

  • CASE 2：如果关注节点是 a，它的兄弟节点 c 是黑色的，并且节点 c 的左右子节点 d、e 都是黑色的，我们就依次进行下面的操作：
  1. 将关注节点 a 的兄弟节点 c 的颜色变成红色；
  2. 从关注节点 a 中去掉一个黑色，这个时候节点 a 就是单纯的红色或者黑色；
  3. 给关注节点 a 的父节点 b 添加一个黑色，这个时候节点 b 就变成了“红 - 黑”或者“黑 - 黑”；
  4. 关注节点从 a 变成其父节点 b；
  5. 继续从四种情况中选择符合的规则来调整。

红黑树二次删除case2调整过程

  • CASE 3：如果关注节点是 a，它的兄弟节点 c 是黑色，c 的左子节点 d 是红色，c 的右子节点 e 是黑色，我们就依次进行下面的操作：
  1. 围绕关注节点 a 的兄弟节点 c 右旋；
  2. 节点 c 和节点 d 交换颜色；
  3. 关注节点不变；
  4. 跳转到 CASE 4，继续调整。

红黑树二次删除case3调整过程

  • CASE 4：如果关注节点 a 的兄弟节点 c 是黑色的，并且 c 的右子节点是红色的，我们就依次进行下面的操作：
  1. 围绕关注节点 a 的父节点 b 左旋；
  2. 将关注节点 a 的兄弟节点 c 的颜色，跟关注节点 a 的父节点 b 设置成相同的颜色；
  3. 将关注节点 a 的父节点 b 的颜色设置为黑色；
  4. 将关注节点 a 的叔叔节点 e 设置为黑色；
  5. 调整结束。

红黑树二次删除case4调整过程
红黑树的平衡调整过程到这里就完成了，回头看平衡调整步骤，确实跟魔方复原过程很相似，并没有多么清晰的逻辑关系，因此也没必要深究这个调整过程的正确性或者试图记住这个平衡调整策略的步骤。你只需知道，只要按照固定的操作步骤，保持插入、删除的过程，不破坏平衡树的定义就行了。

本章数据结构实现源码下载地址：https://github.com/StreamAI/ADT-and-Algorithm-in-C/tree/master/datastruct

更多文章：

注：本文转载自blog.csdn.net的流云IoT的文章"https://blog.csdn.net/m0_37621078/article/details/103899554"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！