要么改变世界,要么适应世界

手撕红黑树!使用C语言带你实现一个平衡搜索树【正文】

2024-01-14 23:52:09
0
目录

认识红黑树

上篇文章我们主要认识了二叉树搜索树,这篇文章正式介绍红黑树。

红黑树在二叉搜索树的基础上,加了些性质,包含colorkeyleftrightp,颜色取值为红色或者黑色,此外,我们把NIL节点视为特殊的节点,具体而言,视为外部节点,也叫叶子节点,把带有关键字的节点视为内部节点。

红黑树是具有下面性质的二叉搜索树:

  1. 每个节点,要么是红色的,要么是黑色的。
  2. 根节点是黑色的。
  3. 每个叶子节点(NIL)是黑色的。
  4. 如果一个节点是红色的,那么它的两个子节点都是黑色的(如果子节点是NIL,则子节点也是黑色的)
  5. 对于每个节点,从该节点到其所有后代叶节点的简单路径(即只会从该节点往叶子节点向往下)上,均包含相同数目的黑色节点。

我们把bh(x)定义为从节点x开始(不包括该节点)到叶子节点的任意一条简单路径上的黑色节点个数成为黑高(black-height)。

例如:

rh_tree_1.drawio

节点旁边的表示是对应的黑高。

红黑树通俗点,就是节点的左右子树高度差异不会很大,而上文提到的二叉搜索树的插入和删除,这两个会影响左右子树的高度差,因此我们要在插入或者删除后,调整红黑树的某些节点的左右子树,才能使得这两个操作满足红黑树的性质。

我们可以将红黑树中所有的NIL节点(包括根节点的双亲)都指向同一个,即:

rh_tree_2.drawio

为了方便,我们可以对NIL节点进行缺省,即:

rh_tree_3.drawio

左旋右旋

在开始前,我们先来认识左旋右旋,这两个操作会辅助我们对红黑树调整:

rh_tree_rotation.drawio

上述的左旋右旋是以最上层的结点角度来说的

左旋x节点:假设x节点的右孩子节点y不是NIL节点,则y成为该子树的新的根节点,x成为y的左孩子,y的左孩子成为x的右孩子。

左旋时,我们假定x.right!=NIL且根节点的父节点为T.NIL,则左旋的伪代码如下:

rb_tree_left_rotation(T, x){
    y = x.right;
    x.right = y.left;
    if y.left != T.NIL
        y.left.p = x;
    y.p = x.p;
    // 如果x是红黑树的根节点
    if x.p == T.NIL
        T.root = y;
    	T.root.p = T.NIL;
    // 如果x是双亲节点的左孩子
    else if x == x.p.left
        x.p.left = y;
    // 如果x是双亲节点的右孩子
    else
        x.p.right = y;
    y.left = x;
    x.p = y;
}

右旋时,我们假定y.left!=NIL,且根节点的父节点为T.NIL,则右旋的伪代码如下:

rb_tree_right_rotation(T, y){
    x = y.left;
    y.left = x.right;
    if x.right != T.NIL
        x.right.p = y;
    x.p = y.p;
    // 如果y是红黑树的根节点
    if y.p == T.NIL
        T.root = x;
    	T.root.p = T.NIL;
    // 如果y是双亲节点的左孩子
    else if y == y.p.left
        y.p.left = x;
    // 如果y是双亲节点的右孩子
    else
        y.p.right = x;
    x.right = y;
    y.p = x;
}

插入

插入步骤主要包括以下步骤:

  1. 找到合适位置,插入节点
  2. 将新节点染成红色
  3. (可选的)调整红黑树,直至符合红黑树定义

与往二叉搜索树中插入节点类似:

rb_tree_insert(T, z){
    y = T.NIL;
    x = T.root;
    while x != T.NIL
        y = x;
      	// 插到左子树
      	if z.key < x.key
            x = x.left;
      	// 插到右子树
      	else
          	x = x.right;
    z.p = y;
    // 空树
    if y == T.NIL
        T.root = z;
    else if z.key < y.key
        y.left = z;
    else 
        y.right = z;
    z.left = T.NIL;
    z.right = T.NIL;
    z.color = RED;
    rb_tree_insert_fixup(T, z);
}

如果节点z插入的位置中,其双亲节点是黑色的,则无需进行调整,这是因为插入这个红色节点后并不会违反上文所提的5个性质,相反,如果其双亲节点是红色的,那么就有连续两个红色的节点,违反了性质4,这时候我们要对红黑树进行调整,我们可以证明,仅当新插入的节点的双亲是红色时,需要对红黑树调整,我们可以将需要进行调整的情况分为3种:

  1. z的叔节点y是红色的。
  2. z的叔节点y是黑色的且z是其双亲的右孩子。
  3. z的叔节点y是黑色的且z是其双亲的左孩子。

在情况1中,由于y是红色的,我们可以同时将z的双亲和y染成黑色,将y的双亲染成红色,则以y的双亲为根的子树满足红黑树定义(当然如果y的双亲是整棵红黑树的根,则y的双亲要再次染成黑色的)。

由于y的双亲被染成了红色,有可能会对y的祖先造成影响(即此时y的双亲的双亲是红色的,此时存在连续的红色的节点),使得一些祖先不能满足红黑树定义,此时,我们要把y的双亲当成z,递归重新判断。

在情况2中,由于z是其双亲的右孩子,我们可以对z的双亲进行一次左旋,此时可以转为情况3.

在情况3中,由于z和z的双亲是红色的,则y的双亲必然是黑色的(因为插入z之前,树是满足红黑树定义的,而z的双亲是红色的,则z的双亲的双亲必然是黑色的),因此我们可以对z的双亲染成黑色,而y的双亲是红色,再对y的双亲做一个右旋,则以z的双亲为根的子树满足红黑树定义。

我们可以以算法导论中的例子为例:

rh_tree_insert.drawio

因此调整的伪代码为:

rb_tree_insert_fixup(T, z){
    while z.p.color == RED
        // 如果z的双亲是左孩子
        if z.p == z.p.p.left
            y = z.p.p.right;
            if y.color == RED
                z.p.color = BLACK;					// case 1
                y.color = BLACK;					// case 1
                z.p.p.color = RED;					// case 1
                z = z.p.p;							// case 1
            else if z == z.p.right
                z = z.p;							// case 2
                rb_tree_left_rotation(T, z)			// case 2
            else
                z.p.color = BLACK;					// case 3
                z.p.p.color = RED;					// case 3
                rb_tree_right_rotation(T, z.p.p);	// case 3
    	// 如果z的双亲是右孩子
    	else
            // 与上面分支对称,将left和right互换即可
            ...
    // 不管怎样,红黑树的性质2一定要满足
	T.root.color = BLACK;     
}

删除

删除过程有亿点点复杂,不过我们可以先分成几个大类(假设被删除的结点是z):

delete_z

A.:z是红色的,且没有子结点:由于其没有孩子,因此删除这个红色结点对其子树(实际子树为空)以及其他的子树都不影响,我们简单地将其删除即可。

B.:z是黑色的,且没有子结点:由于z是黑色的,那么删除z后,对于之前简单路径中包含z的路径长度都减少了1,我们破坏了红黑树性质,这个分类是最复杂的,因此我们后面再展开这类。

C.:z只有一个非T.NIL子结点y:这种情况下,z必然是黑色的且y是红色的,为什么呢?假如z和y都是黑色的,那么根到y的子树的叶子节点的简单路径中黑色结点个数会比根到z的另一个空子树的叶子节点的简单路径中黑色结点个数多1,同理也不可能出现“z是红色的且y是黑色的”,这种情况下我们可以用y替换z(然后删除z),同时将y染成黑色即可。

D.:z有两个子结点:根据之前二叉搜索树的删除,我们可以知道,将来替换z的结点是z的后继x(实际上前驱也可以,不过我们延续二叉搜索树的做法),替换过程我们把z的关键字设置为x的关键字,然后我们删除x按照步骤A、B、C进行(因为x是z的后继,根据前面知识我们知道,当z存在右孩子时,其后继x是z的右子树中最左边的结点,因此其不可能有两个孩子结点)

我们重点展开B类情况:

开始之前,我们先思考一下,如果z是根节点,我们直接删除z即可,然后将红黑树根节点设置为T.NIL即可,如果z不是根节点,参照上文C类的分析,当z没有子结点且z是黑色的情况下,z必然存在一个兄弟节点,我们记该结点为y。

B.a:z的兄弟y是黑色的,且y有一个红色的子结点x,我们对y进行一次旋转,然后再重新染色,再删除z即可,这里又可以分为两种情况:

  • B.a.a:x和z不同向,即一个为左节点,一个为右节点,当z是右节点时,我们对y的双亲进行右旋,如果z是左节点,我们则对y的双亲进行左旋,如下图所示:

    rh_tree_delete.b.a.a.drawio

    注意,变化后新的2号结点颜色要与原先的3号节点颜色相同,否则不满足性质5;此外我们可以证明x没有非NIL子结点

  • B.a.b:x和z同向,即同为其双亲的右孩子或者左孩子,此时我们可以旋转y,并交换x和y的颜色,即可转至上面B.a.a的情况:

    rh_tree_delete.b.a.b.drawio

B.b:z的兄弟y是黑色的,且y没有子结点,这里可以分z的双亲是红色和黑色情况

  • B.b.a:如果z的双亲是红色:这里比较简单,我们直接删除z,然后将y的双亲染为黑色同时将y染为红色

    rh_tree_delete.b.b.a.drawio

  • B.b.b:如果z的双亲是黑色的,这种情况就比较复杂了,我们需要先删除z的同时将y染成红色,然后将z指向y的双亲,由于新的z只有一个红色的子结点y,红色结点的存在与否不影响包含该节点的简单路径中黑色结点个数,因此我们可以当成是B情况的特例,然后使用B.a~B.c的情况进一步调整(虽然B.c的情况在下面才说明),只不过有些时候我们把黑色的非NIL结点当成了NIL结点,但是不影响最终的调整,注意这种情况下我们不再对新的z进行删除操作。当然这个过程中,z有可能一直往上,直至遇到根节点,届时我们不再需要往上进行,这几种情况如下图所示:

    rh_tree_delete.b.b.b.drawio

B.c:z的兄弟y是红色的,由于z是黑色的且没有子结点,y是红色的,因此z的双亲必然是黑色的且y有两个黑色的子结点(但是y有没有红色的孙子结点不确定):

rh_tree_delete.b.c.drawio

我们可以先对z的双亲做一个旋转(上图的情况是左旋,当z是右孩子时对称地对双亲右旋即可),并将y和其新的左孩子对调颜色,外面可以发现,此时如果不删除结点1,那么这棵树是满足红黑树的,但是外面删除了结点1,言外之意,我们把左边的删除过程和右边做了一个等价交换,而这种情况,我们可以转成B.aB.b情况。

new y 和 旧的y同向

还有一点值得注意,B情况包含涵盖了所有情况了吗??其实没有,我们还缺少一种情况,即“z是黑色的没有孩子结点,且z的兄弟结点y也是黑色的且y有两个红孩子”,但是我们这种情况可以规约成B.a.a情况,例如:

rh_tree_delete.b.d.drawio

完成上面的分析后,我们就可以写出这部分的伪代码了,不过在开始之前,我们也要先定义一个子过程,用于使用以v为根的子树来替换以u为根的子树

rb_tree_transplant(T, u, v){
    if u.p == T.NIL
        T.root = v;
    else if u == u.p.left
        u.p.left = v;
    else
        u.p.right = v;
    v.p = u.p;
}

ok,下面是删除功能的伪代码了:

rb_tree_delete_case_B_a_a_fix(T, x){
    y = x.p;
    y_is_left = (y == y.p.left);
    y_p_color = y.p.color
    if y_is_left
        rb_tree_right_rotation(T, y.p)
    	y.right.color = BLACK;
    else
        rb_tree_left_rotation(T, y.p);
    	y.left.color = BLACK;
    x.color = BLACK;
    y.color = y_p_color;
}
rb_tree_delete_case_B_a_b_fix(T, x){
    y = x.p;
    y_is_left = (y == y.p.left);
    y.color = RED;
    x.color = BLACK
    if y_is_left
        rb_tree_left_rotation(T, y);
    else
        rb_tree_right_rotation(T, y);
    // 交换 x 和 y 指针
    swap_ptr(y, x);
    // 化为 B.a.a
    rb_tree_delete_case_B_a_a_fix(T, x);
}
yrb_tree_delete_case_B_b_a_fix(T, y){
    y.color = RED;
    y.p.color = BLACK;
}

rb_tree_delete_case_B_b_b_fix(T, y){
    y.color = RED;
    new_z = y.p;
    if new_z == T.root
        return;
    new_z_is_left = (new_z == new_z.p.left);
    new_y = (new_z_is_left ? new_z.p.right : new_z.p.left)
    if new_y.color == BLACK and (
        (new_z_is_left and new_y.right != T.NIL and new_y.right.color == RED) or 
        (!new_z_is_left and new_y.left != T.NIL and new_y.left.color == RED)
    )
        // 转 B.a.a后结束
        rb_tree_delete_case_B_a_a_fix(T, new_z_is_left ? new_y.right : new_y.left);
    else if new_y.color == BLACK and ( 
        (new_z_is_left and new_y.left != T.NIL and new_y.left.color == RED) or
        (!new_z_is_left and new_y.right != T.NIL and new_y.right.color == RED)
    )
        // 转 B.a.b后结束
        rb_tree_delete_case_B_a_a_fix(T, new_z_is_left ? new_y.left : new_y.right);
    // 注意,这里使用“y是不是有俩个黑色的子结点”而不是使用“y是不是有两个NIL子结点”
    else if new_y.color == BLACK and new_y.left.color == BALCK and new_y.right.color == BALCKL and new_z.p.color == RED
        // 转 B.b.a后结束
        rb_tree_delete_case_B_b_a_fix(T, new_y);
    else if new_y.color == BLACK and new_y.left.color == BALCK and new_y.right.color == BALCKL and new_z.p.color == BLACK
        // 继续递归 B.b.b
        rb_tree_delete_case_B_b_b_fix(T, new_y);
    else if new_y.color == RED
        // 转 B.c后结束
        rb_tree_delete_case_B_c_fix(T, new_y);
}
rb_tree_delete_case_B_c_fix(T, y){
    y.color = BLACK;
    y_is_left = (y == y.p.left);
    if y_is_left
        rb_tree_right_rotation(T, y.p);
    	y.right.left.color = RED;
    	new_y = y.right.left;
    else
        rb_tree_left_rotation(T, y.p);
		y.left.right.color = RED;
    	new_y = y.left.right;
    // 如果 new_y 有红色子结点,跳转 B.a.a 或者 B.a.b
    if (y_is_left and new_y.left.color == RED) or 
       (!y_is_left and new_y.right.color == RED)
        rb_tree_delete_case_B_a_a_fix(T, y_is_left ? new_y.left : new_y.right);
    else if (y_is_left and new_y.right.color == RED) or 
       (!y_is_left and new_y.left.color == RED)
        rb_tree_delete_case_B_a_b_fix(T, y_is_left ? new_y.right : new_y.left);
	 // 如果 new_y 有没有子结点,由于 new y 的双亲是红色的,跳转B.b.a
    else if new_y.left.color == BLACK and new_y.right.color == BLACK
        rb_tree_delete_case_B_b_a_fix(T, new_y);
}
rb_tree_delete_case_A(T, z){
    // 直接删除
    if z == z.p.left
        z.p.left = T.NIL;
    else
        z.p.right = T.NIL;
}
rb_tree_delete_case_B(T, z){
    
    // 先删除z
    if z == z.p.left
        z.p.left = T.NIL;
    	y = z.p.right;
    	z_is_left = true;
    else
        z.p.right = T.NIL;
    	y = z.p.left;
        z_is_left = false;
    // 如果z是根节点,则删除后是空树,不需要考虑z的兄弟节点了,因为根本不存在
    if z == T.root
        T.root = T.NIL;
        return;
    // 再根据不同的情况进行调整
    // b.a.a
    if y.color == BLACK and (
        (z_is_left and y.right != T.NIL and y.right.color == RED) or 
        (!z_is_left and y.left != T.NIL and y.left.color == RED)
    )
        rb_tree_delete_case_B_a_a_fix(T, z_is_left ? y.right : y.left);
    // b.a.b
    else if y.color == BLACK and ( 
        (z_is_left and y.left != T.NIL and y.left.color == RED) or
        (!z_is_left and y.right != T.NIL and y.right.color == RED)
    )
        rb_tree_delete_case_B_a_b_fix(T, z_is_left ? y.left : y.right);
    // b.b.a
    else if y.color == BLACK and y.left == T.NIL and y.right == T.NIL and z.p.color == RED
        rb_tree_delete_case_B_b_a_fix(T, y);
    // b.b.b
    else if y.color == BLACK and y.left == T.NIL and y.right == T.NIL and z.p.color == BLACK
        rb_tree_delete_case_B_b_b_fix(T, y);
    // b.c
    else if y.color == RED
        rb_tree_delete_case_B_c_fix(T, y);
}
rb_tree_delete_case_C(T, z){
    if z.left == T.NIL
        y = z.right;
    else
        y = z.left;
    rb_tree_transplant(T, z, y);
    y.color = BLACK;
}
rb_tree_delete_case_D(T, z){
    x = rb_tree_search_suc(z);
    z.key = x.key;
    rb_tree_delete(T, x);
}
rb_tree_delete(T, z){
    // A情况
    else if z.color == RED and z.left == T.NIL and z.right == z.left
        rb_tree_delete_case_A(T, z);
    // B情况
    else if z.color == BLACK and z.left == T.NIL and z.right == T.NIL
        rb_tree_delete_case_B(T, z);
    // C情况
    else if (z.left == T.NIL and z.right != T.NIL) or (z.right == T.NIL and z.left != T.NIL)
        rb_tree_delete_case_C(T, z);
    // D情况
    else if z.left != T.NIL and z.right != T.NIL
        rb_tree_delete_case_D(T, z);
}

C语言实现

先定义红黑树以及树的结点:

typedef struct Node {
    int key;
    int color;
    struct Node* p, * left, * right;
}TreeNode;

typedef struct Tree {
    TreeNode* root;
    TreeNode* NIL;
}RedBlackTree;

然后是初始化红黑树的代码:

// 初始化一个NIL结点,红黑树整个生命周期只会生成一个NIL结点
void initRedBlackTree(RedBlackTree* tree) {
    TreeNode* nil = (TreeNode*)malloc(sizeof(TreeNode));
    nil->color = BLACK;
    tree->NIL = nil;
    tree->root = nil;
    tree->root->p = tree->NIL;
    tree->root->left = tree->NIL;
    tree->root->right = tree->NIL;
}

我们还要写一个用于验证红黑树的函数:

int valid;
int dfsValid(RedBlackTree* T, TreeNode* root, TreeNode* p) {
    if (root->color != RED && root->color != BLACK) {
        // 性质1
        valid = -1;
    }
    if (root == T->NIL && root->color != BLACK) {
        // 性质3
        valid = -1;
    }
    if (root->color == RED && (root->left->color == RED || root->right->color == RED)) {
        // 性质4
        valid = -1;
    }
    if (root != T->NIL && root->p != p) {
        valid = -1;
    }
    // 性质5
    if (root != T->NIL) {
        int leftBlackNodeCnt = dfsValid(T, root->left, root);
        int rightBlackNodeCnt = dfsValid(T, root->right, root);
        if (leftBlackNodeCnt != rightBlackNodeCnt) {
            valid = -1;
        }
        return leftBlackNodeCnt + (root->color == BLACK ? 1 : 0);
    }

    // 搜索树性质
    if (root->left != T->NIL && root->left->key > root->key) {
        valid = -1;
    }
    if (root->right != T->NIL && root->right->key < root->key) {
        valid = -1;
    }
    return (root->color == BLACK ? 1 : 0);
}




int redBlackTreeValid(RedBlackTree* T) {
    // 根节点是黑色的(性质2),空节点是黑色的(性质3)
    if (T->root->color != BLACK || T->NIL->color != BLACK) {
        return -1;
    }
    if (T->root->p != T->NIL) {
        return -1;
    }
    valid = 1;
    dfsValid(T, T->root, T->NIL);
    if (valid == -1) {
        printf("*********Not valid red black tree!*********\n");
        return -1;
    }
    return 1;
}

我们可以编写一个测试代码,测试10次,每次产生指定长度10000的随机数据插入,插入完毕后随机删除结点:

int final_test(int len, int debug) {

    if (len > 10000) {

    }
    RedBlackTree* T = (RedBlackTree*)malloc(sizeof(RedBlackTree));
    initRedBlackTree(T);
    redBlackTreeValid(T);

    int nums[10000];
    // 测试插入
    printf("----- start insert  -----\n");
    for (int i = 0; i < len;i++) {
        nums[i] = generateRandomNumber(0, len);
        if (debug) {
            printf("insert %d\n", nums[i]);
        }
        TreeNode* z = (TreeNode*)malloc(sizeof(TreeNode));
        z->color = RED;
        z->p = T->NIL;
        z->left = T->NIL;
        z->right = T->NIL;
        z->key = nums[i];
        rb_tree_insert(T, z);
        redBlackTreeValid(T);
    }
    // 测试删除
    printf("----- start delete  -----\n");
    int remain = len;
    int deleteIdx, deleteKey;
    for (int i = 1; i <= len;i++) {
        deleteIdx = generateRandomNumber(0, remain);
        // 避免下次再被选到
        deleteKey = nums[deleteIdx];
        // printf("delete %d\n", deleteKey);
        nums[deleteIdx] = nums[remain - 1];
        nums[remain - 1] = deleteKey;
        TreeNode* z = rb_tree_search(T, T->root, deleteKey);

        if (z == T->NIL) {
            printf("No found!");
        }
        else {
            if (debug) {
                printf("delete %d\n", deleteKey);
            }
            rb_tree_delete(T, z);
            if (redBlackTreeValid(T) == -1) {
                printf("delete error just now on %d\n", deleteKey);
            }
        }

        remain--;

    }

}
int main() {
    // 重新设置随机数种子
    srand(time(NULL));
    for (int i = 1; i <= 10; i++) {
        final_test(10000, 0);
    }
    return 0;
}

测试结果如下(如果有出现删除或者插入后不符合红黑树性质,则会打印*********Not valid red black tree!*********

debug

完整实现:

#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>
#include <time.h>
#define RED 0
#define BLACK 1
typedef struct Node {
    int key;
    int color;
    struct Node* p, * left, * right;
}TreeNode;

typedef struct Tree {
    TreeNode* root;
    TreeNode* NIL;
}RedBlackTree;
// 初始化一个NIL结点,红黑树整个生命周期只会生成一个NIL结点
void initRedBlackTree(RedBlackTree* tree) {
    TreeNode* nil = (TreeNode*)malloc(sizeof(TreeNode));
    nil->color = BLACK;
    tree->NIL = nil;
    tree->root = nil;
    tree->root->p = tree->NIL;
    tree->root->left = tree->NIL;
    tree->root->right = tree->NIL;
}
void rb_tree_left_rotation(RedBlackTree* T, TreeNode* x) {
    TreeNode* y = x->right;
    x->right = y->left;
    if (y->left != T->NIL) {
        y->left->p = x;
    }
    y->p = x->p;
    // 如果x是红黑树的根节点
    if (x->p == T->NIL) {
        T->root = y;
        T->root->p = T->NIL;
    }
    // 如果x是双亲节点的左孩子
    else if (x == x->p->left) {
        x->p->left = y;
    }
    // 如果x是双亲节点的右孩子
    else {
        x->p->right = y;
    }
    y->left = x;
    x->p = y;
}
void rb_tree_right_rotation(RedBlackTree* T, TreeNode* y) {
    TreeNode* x = y->left;
    y->left = x->right;
    if (x->right != T->NIL) {
        x->right->p = y;
    }
    x->p = y->p;
    // 如果y是红黑树的根节点
    if (y->p == T->NIL) {
        T->root = x;
        T->root->p = T->NIL;
    }
    // 如果y是双亲节点的左孩子
    else if (y == y->p->left) {
        y->p->left = x;
    }
    // 如果y是双亲节点的右孩子
    else {
        y->p->right = x;
    }
    x->right = y;
    y->p = x;
}

TreeNode* rb_tree_search(RedBlackTree* T, TreeNode* root, int key) {

    if (root == T->NIL || root->key == key) {
        return root;
    }
    // 在左子树中
    if (key < root->key) {
        return rb_tree_search(T, root->left, key);
    }
    // 在右子树中
    else {
        return rb_tree_search(T, root->right, key);
    }
}
// ======= 插入开始部分  ==========
void rb_tree_insert_fixup(RedBlackTree* T, TreeNode* z) {
    TreeNode* y;
    while (z->p->color == RED) {
        // 如果z的双亲是左孩子
        if (z->p == z->p->p->left) {
            y = z->p->p->right;
            if (y->color == RED) {
                z->p->color = BLACK;				// case 1
                y->color = BLACK;				    // case 1
                z->p->p->color = RED;				// case 1
                z = z->p->p;                        // case 1
            }
            else if (z == z->p->right) {
                z = z->p;                           // case 2
                rb_tree_left_rotation(T, z);		// case 2
            }
            else {
                z->p->color = BLACK;				// case 3
                z->p->p->color = RED;				// case 3
                rb_tree_right_rotation(T, z->p->p);	// case 3
            }
        }
        else {
            y = z->p->p->left;
            if (y->color == RED) {
                z->p->color = BLACK;				// case 1
                y->color = BLACK;				    // case 1
                z->p->p->color = RED;				// case 1
                z = z->p->p;                        // case 1
            }
            else if (z == z->p->left) {
                z = z->p;                           // case 2
                rb_tree_right_rotation(T, z);		// case 2
            }
            else {
                z->p->color = BLACK;				// case 3
                z->p->p->color = RED;				// case 3
                rb_tree_left_rotation(T, z->p->p);	// case 3
            }
        }
    }
    // 不管怎样,红黑树的性质2一定要满足
    T->root->color = BLACK;
}


void rb_tree_insert(RedBlackTree* T, TreeNode* z) {
    TreeNode* y = T->NIL;
    TreeNode* x = T->root;
    while (x != T->NIL) {
        y = x;
        // 插到左子树
        if (z->key < x->key) {
            x = x->left;
        }
        // 插到右子树
        else {
            x = x->right;
        }
    }
    z->p = y;
    // 空树
    if (y == T->NIL) {
        T->root = z;
    }
    else if (z->key < y->key) {
        y->left = z;
    }
    else {
        y->right = z;
    }
    z->left = T->NIL;
    z->right = T->NIL;
    z->color = RED;
    rb_tree_insert_fixup(T, z);
}

// ======= 插入结束部分  ==========


// ======= 删除开始部分  ==========
rb_tree_delete_case_B_a_a_fix(RedBlackTree* T, TreeNode* x) {
    TreeNode* y = x->p;
    int y_is_left = (y == y->p->left);
    int y_p_color = y->p->color;
    if (y_is_left) {
        rb_tree_right_rotation(T, y->p);
        y->right->color = BLACK;
    }
    else {
        rb_tree_left_rotation(T, y->p);
        y->left->color = BLACK;
    }
    x->color = BLACK;
    y->color = y_p_color;
}
rb_tree_delete_case_B_a_b_fix(RedBlackTree* T, TreeNode* x) {
    TreeNode* y = x->p;
    int y_is_left = (y == y->p->left);
    y->color = RED;
    x->color = BLACK;
    if (y_is_left) {
        rb_tree_left_rotation(T, y);
    }
    else {
        rb_tree_right_rotation(T, y);
    }
    // 交换 x 和 y 指针
    TreeNode* t = x;
    x = y;
    y = t;
    // 化为 B->a->a
    rb_tree_delete_case_B_a_a_fix(T, x);
}
rb_tree_delete_case_B_b_a_fix(RedBlackTree* T, TreeNode* y) {
    y->color = RED;
    y->p->color = BLACK;
}
rb_tree_delete_case_B_c_fix(RedBlackTree* T, TreeNode* y) {
    y->color = BLACK;                     
    int y_is_left = (y == y->p->left);
    TreeNode* new_y;
    if (y_is_left) {
        rb_tree_right_rotation(T, y->p);
        y->right->color = RED;
        new_y = y->right->left;
    }
    else {
        rb_tree_left_rotation(T, y->p);
        y->left->color = RED;
        new_y = y->left->right;
    }
    // new_y 和旧的 y 是同向的
    // 如果 new_y 有红色子结点,跳转B.a.a 或者 B.a.b
    if ((y_is_left && new_y->left->color == RED) || (!y_is_left && new_y->right->color == RED)) {
        rb_tree_delete_case_B_a_a_fix(T, y_is_left ? new_y->left : new_y->right);
    }
    else if ((y_is_left && new_y->right->color == RED) || (!y_is_left && new_y->left->color == RED)) {
        rb_tree_delete_case_B_a_b_fix(T, y_is_left ? new_y->right : new_y->left);
    }
    // 如果 new_y 有没有子结点,由于 new y 的双亲是红色的,跳转B.b.a
    else if (new_y->left->color == BLACK && new_y->right->color == BLACK) {
        rb_tree_delete_case_B_b_a_fix(T, new_y);
    }

}
rb_tree_delete_case_B_b_b_fix(RedBlackTree* T, TreeNode* y) {
    y->color = RED;
    TreeNode* new_z = y->p;
    if (new_z == T->root) {
        return;
    }
    int new_z_is_left = (new_z == new_z->p->left);
    TreeNode* new_y = (new_z_is_left ? new_z->p->right : new_z->p->left);
    if (new_y->color == BLACK && (
        (new_z_is_left && new_y->right != T->NIL && new_y->right->color == RED) ||
        (!new_z_is_left && new_y->left != T->NIL && new_y->left->color == RED)
        )) {
        // 转 B.a.a后结束
        rb_tree_delete_case_B_a_a_fix(T, new_z_is_left ? new_y->right : new_y->left);
    }
    else if (new_y->color == BLACK && (
        (new_z_is_left && new_y->left != T->NIL && new_y->left->color == RED) ||
        (!new_z_is_left && new_y->right != T->NIL && new_y->right->color == RED)
        )) {
        // 转 B.a.b后结束
        rb_tree_delete_case_B_a_b_fix(T, new_z_is_left ? new_y->left : new_y->right);
    }
    // 注意,这里使用“y是不是有俩个黑色的子结点”而不是使用“y是不是有两个NIL子结点”
    else if (new_y->color == BLACK && new_y->left->color == BLACK && new_y->right->color == BLACK && new_z->p->color == RED) {
        // 转 B.b.a后结束
        rb_tree_delete_case_B_b_a_fix(T, new_y);
    }
    else if (new_y->color == BLACK && new_y->left->color == BLACK && new_y->right->color == BLACK && new_z->p->color == BLACK) {
        // 继续递归 B.b.b
        rb_tree_delete_case_B_b_b_fix(T, new_y);
    }
    else if (new_y->color == RED) {
        // 转 B.c后结束
        rb_tree_delete_case_B_c_fix(T, new_y);
    }
}

rb_tree_delete_case_A(RedBlackTree* T, TreeNode* z) {
    // 直接删除
    if (z == z->p->left) {
        z->p->left = T->NIL;
    }
    else {
        z->p->right = T->NIL;
    }
    free(z);
}
rb_tree_delete_case_B(RedBlackTree* T, TreeNode* z) {
    int z_is_left;
    TreeNode* y;
    // 先删除z
    if (z == z->p->left) {
        z->p->left = T->NIL;
        y = z->p->right;
        z_is_left = 1;
    }
    else {
        z->p->right = T->NIL;
        y = z->p->left;
        z_is_left = 0;
    }
    // 如果z是根节点,则删除后是空树,不需要考虑z的兄弟节点了,因为根本不存在
    if (z == T->root) {
        T->root = T->NIL;
        return;
    }
    TreeNode* z_p = z->p;
    free(z);

    // 其他再根据不同的情况进行调整
    // b.a.a
    if (y->color == BLACK && (
        (z_is_left && y->right != T->NIL && y->right->color == RED) ||
        (!z_is_left && y->left != T->NIL && y->left->color == RED)
        )) {
        rb_tree_delete_case_B_a_a_fix(T, z_is_left ? y->right : y->left);
    }
    // b.a.b
    else if (y->color == BLACK && (
        (z_is_left && y->left != T->NIL && y->left->color == RED) ||
        (!z_is_left && y->right != T->NIL && y->right->color == RED)
        )) {
        rb_tree_delete_case_B_a_b_fix(T, z_is_left ? y->left : y->right);
    }
    // b.b.a
    else if (y->color == BLACK && y->left == T->NIL && y->right == T->NIL && z_p->color == RED) {
        rb_tree_delete_case_B_b_a_fix(T, y);
    }
    // b.b.b
    else if (y->color == BLACK && y->left == T->NIL && y->right == T->NIL && z_p->color == BLACK) {
        rb_tree_delete_case_B_b_b_fix(T, y);
    }
    // b.c
    else if (y->color == RED) {
        rb_tree_delete_case_B_c_fix(T, y);
    }
}
rb_tree_transplant(RedBlackTree* T, TreeNode* u, TreeNode* v) {
    if (u->p == T->NIL) {
        T->root = v;
    }
    else if (u == u->p->left) {
        u->p->left = v;
    }
    else {
        u->p->right = v;
    }
    v->p = u->p;
}
rb_tree_delete_case_C(RedBlackTree* T, TreeNode* z) {
    TreeNode* y;
    if (z->left == T->NIL) {
        y = z->right;
    }
    else {
        y = z->left;
    }
    rb_tree_transplant(T, z, y);
    y->color = BLACK;
    free(z);
}
TreeNode* b_tree_search_min(RedBlackTree* T, TreeNode* root) {
    if (root == T->NIL) {
        return T->NIL;
    }
    TreeNode* ans = root;
    while (ans->left != T->NIL) {
        ans = ans->left;
    }
    return ans;
}
TreeNode* rb_tree_search_suc(RedBlackTree* T, TreeNode* x) {
    if (x->right != T->NIL) {
        return b_tree_search_min(T, x->right);
    }
    TreeNode* y = x->p;
    while (y != T->NIL && x == y->right) {
        x = y;
        y = y->p;
    }
    return y;
}
rb_tree_delete_case_D(RedBlackTree* T, TreeNode* z) {
    TreeNode* x = rb_tree_search_suc(T, z);
    z->key = x->key;
    rb_tree_delete(T, x);
}
rb_tree_delete(RedBlackTree* T, TreeNode* z) {
    // A情况
    if (z->color == RED && z->left == T->NIL && z->right == z->left) {
        rb_tree_delete_case_A(T, z);
    }
    // B情况
    else if (z->color == BLACK && z->left == T->NIL && z->right == T->NIL) {
        rb_tree_delete_case_B(T, z);
    }
    // C情况
    else if ((z->left == T->NIL && z->right != T->NIL) || (z->right == T->NIL && z->left != T->NIL)) {
        rb_tree_delete_case_C(T, z);
    }
    // D情况
    else if (z->left != T->NIL && z->right != T->NIL) {
        rb_tree_delete_case_D(T, z);
    }
}
// ======= 删除结束部分  ==========

int valid;
int dfsValid(RedBlackTree* T, TreeNode* root, TreeNode* p) {
    if (root->color != RED && root->color != BLACK) {
        // 性质1
        valid = -1;
    }
    if (root == T->NIL && root->color != BLACK) {
        // 性质3
        valid = -1;
    }
    if (root->color == RED && (root->left->color == RED || root->right->color == RED)) {
        // 性质4
        valid = -1;
    }
    if (root != T->NIL && root->p != p) {
        valid = -1;
    }
    // 性质5
    if (root != T->NIL) {
        int leftBlackNodeCnt = dfsValid(T, root->left, root);
        int rightBlackNodeCnt = dfsValid(T, root->right, root);
        if (leftBlackNodeCnt != rightBlackNodeCnt) {
            valid = -1;
        }
        return leftBlackNodeCnt + (root->color == BLACK ? 1 : 0);
    }

    // 搜索树性质
    if (root->left != T->NIL && root->left->key > root->key) {
        valid = -1;
    }
    if (root->right != T->NIL && root->right->key < root->key) {
        valid = -1;
    }
    return (root->color == BLACK ? 1 : 0);
}




int redBlackTreeValid(RedBlackTree* T) {
    // 根节点是黑色的(性质2),空节点是黑色的(性质3)
    if (T->root->color != BLACK || T->NIL->color != BLACK) {
        return -1;
    }
    if (T->root->p != T->NIL) {
        return -1;
    }
    valid = 1;
    dfsValid(T, T->root, T->NIL);
    if (valid == -1) {
        printf("*********Not valid red black tree!*********\n");
        return -1;
    }
    return 1;
}
// 生成[a, b)范围内的随机整数
int generateRandomNumber(int a, int b) {
    return a + rand() % (b - a);
}
void printdfs(RedBlackTree* T, TreeNode* root) {
    if (root == T->NIL) {
        return;
    }
    printf("%d:%c left = %d, right = %d\n", root->key, root->color == RED ? 'R' : 'B', root->left->key, root->right->key);
    printdfs(T, root->left);
    printdfs(T, root->right);
}
int final_test(int len, int debug) {

    if (len > 10000) {

    }
    RedBlackTree* T = (RedBlackTree*)malloc(sizeof(RedBlackTree));
    initRedBlackTree(T);
    redBlackTreeValid(T);

    int nums[10000];
    // 测试插入
    printf("----- start insert  -----\n");
    for (int i = 0; i < len;i++) {
        nums[i] = generateRandomNumber(0, len);
        if (debug) {
            printf("insert %d\n", nums[i]);
        }
        TreeNode* z = (TreeNode*)malloc(sizeof(TreeNode));
        z->color = RED;
        z->p = T->NIL;
        z->left = T->NIL;
        z->right = T->NIL;
        z->key = nums[i];
        rb_tree_insert(T, z);
        redBlackTreeValid(T);
    }
    // 测试删除
    printf("----- start delete  -----\n");
    int remain = len;
    int deleteIdx, deleteKey;
    for (int i = 1; i <= len;i++) {
        deleteIdx = generateRandomNumber(0, remain);
        // 避免下次再被选到
        deleteKey = nums[deleteIdx];
        // printf("delete %d\n", deleteKey);
        nums[deleteIdx] = nums[remain - 1];
        nums[remain - 1] = deleteKey;
        TreeNode* z = rb_tree_search(T, T->root, deleteKey);

        if (z == T->NIL) {
            printf("No found!");
        }
        else {
            if (debug) {
                printf("delete %d\n", deleteKey);
            }
            rb_tree_delete(T, z);
            if (redBlackTreeValid(T) == -1) {
                printf("delete error just now on %d\n", deleteKey);
            }
        }

        remain--;

    }

}
int main() {
    
    // 重新设置随机数种子
    srand(time(NULL));
    for (int i = 1; i <= 10; i++) {
        final_test(9999, 0);
    }



    return 0;
}

后记

红黑树可以称得上几乎平衡的二叉搜索树,能够在最坏的情况下把插入、检索和删除的时间复杂度都控制在$O(\lg(n))$,如果把一系列数据结构都当成是学生的话,把插入、随机检索和删除作为考核科目,那么红黑树可以比喻成每科都能拿90分的学霸,而二叉平衡树(AVL)在“检索”拿到95分,哈希表更是在“检索”科目拿到97分,不过后面两位学生在插入和删除方面拿到的分数就比90分低多了。

红黑树应用十分广,因为它能够做到插入、删除和检索都接近$O(\log n)$,没有平衡二叉树调整那么频繁,却能够接近平衡二叉树的查询时间,当然由于其树型结构,当面临大量顺序读写时,比不上数组,因为数组能够借助硬件缓存,使得CPU直接从高速缓存中拿到数据,而红黑树难以做到高命中率。在随机读写方面,除了哈希表,红黑树和平衡二叉树天下无敌!

参考文献

算法导论第三版

历史评论
开始评论