c/c++Linux后台开发课程笔记 - 1.1.1红黑树

2021/11/23 7:14:27

本文主要是介绍c/c++Linux后台开发课程笔记 - 1.1.1红黑树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

红黑树的应用场景

  • 进程调度cfs
  • epoll
  • nginx timer
  • std::map

红黑树的性质

  1. 节点是红色或者黑色
  2. 根节点是黑色
  3. 叶节点(NIL)是黑色
  4. 红色节点的子节点只能是黑色
  5. 从根节点到任意叶节点的路径的黑色节点数(黑高)相等

红黑树定义

typedef int KEY_TYPE;

typedef struct _rbtree_node {
	unsigned char color;
	struct _rbtree_node *left;
	struct _rbtree_node *right;
	struct _rbtree_node *parent;
	KEY_TYPE key;
	void *value;
} rbtree_node;

typedef struct _rbtree {
	rbtree_node *root;
	rbtree_node *nil; //所有nil都指向这个节点
};

左旋与右旋

在这里插入图片描述
要改三个链接,六个指针(最上面的,x-y,b上面的)

void _left_rotate(rbtree *T, rbtree_node *x) {
	rbtree_node *y = x->right;
	x->right = y->left;
	if(y->left) {
		y->left->parent = x;
	}
	y->parent = x->parent;
	if(x->parent == T->nil) {
		T->root = x;
	} else if (x->parent->left == x) {
		x->parent->left = y;
	} else {
		x->parent->right = y;
	}
	y->left = x;
	x->parent = y;
}

红黑树插入

  1. 查找到要插入的位置,以及它的父节点
  2. 新插入的节点标为红色
  3. 解决可能的冲突 (4)

三种情况

父节点是红色,祖父节点一定是黑

  1. 叔节点是红色
    -> 父节点和叔节点都设为黑,祖父设为红,当前节点变为祖父(把红往上推)
  2. 叔节点是黑色,当前节点是父节点的右孩子
    -> 父节点左旋并调整颜色,转换成情况3
  3. 叔节点是黑色,当前节点是父节点的左孩子
    -> 祖父节点右旋并调整颜色

最后将根节点设成黑色

RB-INSERT-FIXUP(T, z)
01 while color[p[z]] = RED                                                  // 若“当前节点(z)的父节点是红色”,则进行以下处理。
02     do if p[z] = left[p[p[z]]]                                           // 若“z的父节点”是“z的祖父节点的左孩子”,则进行以下处理。
03           then y ← right[p[p[z]]]                                        // 将y设置为“z的叔叔节点(z的祖父节点的右孩子)”
04                if color[y] = RED                                         // Case 1条件:叔叔是红色
05                   then color[p[z]] ← BLACK                    ▹ Case 1   //  (01) 将“父节点”设为黑色。
06                        color[y] ← BLACK                       ▹ Case 1   //  (02) 将“叔叔节点”设为黑色。
07                        color[p[p[z]]] ← RED                   ▹ Case 1   //  (03) 将“祖父节点”设为“红色”。
08                        z ← p[p[z]]                            ▹ Case 1   //  (04) 将“祖父节点”设为“当前节点”(红色节点)
09                   else if z = right[p[z]]                                // Case 2条件:叔叔是黑色,且当前节点是右孩子
10                           then z ← p[z]                       ▹ Case 2   //  (01) 将“父节点”作为“新的当前节点”。
11                                LEFT-ROTATE(T, z)              ▹ Case 2   //  (02) 以“新的当前节点”为支点进行左旋。
12                           color[p[z]] ← BLACK                 ▹ Case 3   // Case 3条件:叔叔是黑色,且当前节点是左孩子。(01) 将“父节点”设为“黑色”。
13                           color[p[p[z]]] ← RED                ▹ Case 3   //  (02) 将“祖父节点”设为“红色”。
14                           RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3   //  (03) 以“祖父节点”为支点进行右旋。
15        else (same as then clause with "right" and "left" exchanged)      // 若“z的父节点”是“z的祖父节点的右孩子”,将上面的操作中“right”和“left”交换位置,然后依次执行。
16 color[root[T]] ← BLACK 

红黑树删除节点

  1. 找到节点,如果子节点数=0则直接删除,如果子节点数=1则用子节点替换,如果=2就找到后序节点,把后序节点内容复制到当前节点,再删除后序节点
  2. 如果删除的节点是黑色,则当前节点多拥有一层黑色
  3. 如果当前节点是黑+红,则直接把当前节点设成黑,结束
  4. 否则要重新平衡

删除再平衡

  1. 兄弟节点是红 ->父节点左旋,转换成2/3/4
  2. 兄弟节点是黑,兄弟的两个子节点都是黑 -> 把兄弟节点设红,当前节点保留黑,当前节点设为父节点 )(把黑往上推)
  3. 兄弟是黑,兄弟的左孩子是红 -> 通过右旋兄弟转换成4
  4. 兄弟是黑,兄弟的右孩子是红 -> 父节点左旋,借一个红节点过来左边并设成黑的,这样就没有双黑了,结束
RB-DELETE-FIXUP(T, x)
01 while x ≠ root[T] and color[x] = BLACK  
02     do if x = left[p[x]]      
03           then w ← right[p[x]]                                             // 若 “x”是“它父节点的左孩子”,则设置 “w”为“x的叔叔”(即x为它父节点的右孩子)                                          
04                if color[w] = RED                                           // Case 1: x是“黑+黑”节点,x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。
05                   then color[w] ← BLACK                        ▹  Case 1   //   (01) 将x的兄弟节点设为“黑色”。
06                        color[p[x]] ← RED                       ▹  Case 1   //   (02) 将x的父节点设为“红色”。
07                        LEFT-ROTATE(T, p[x])                    ▹  Case 1   //   (03) 对x的父节点进行左旋。
08                        w ← right[p[x]]                         ▹  Case 1   //   (04) 左旋后,重新设置x的兄弟节点。
09                if color[left[w]] = BLACK and color[right[w]] = BLACK       // Case 2: x是“黑+黑”节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色。
10                   then color[w] ← RED                          ▹  Case 2   //   (01) 将x的兄弟节点设为“红色”。
11                        x ←  p[x]                               ▹  Case 2   //   (02) 设置“x的父节点”为“新的x节点”。
12                   else if color[right[w]] = BLACK                          // Case 3: x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的左孩子是红色,右孩子是黑色的。
13                           then color[left[w]] ← BLACK          ▹  Case 3   //   (01) 将x兄弟节点的左孩子设为“黑色”。
14                                color[w] ← RED                  ▹  Case 3   //   (02) 将x兄弟节点设为“红色”。
15                                RIGHT-ROTATE(T, w)              ▹  Case 3   //   (03) 对x的兄弟节点进行右旋。
16                                w ← right[p[x]]                 ▹  Case 3   //   (04) 右旋后,重新设置x的兄弟节点。
17                         color[w] ← color[p[x]]                 ▹  Case 4   // Case 4: x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的右孩子是红色的。(01) 将x父节点颜色 赋值给 x的兄弟节点。
18                         color[p[x]] ← BLACK                    ▹  Case 4   //   (02) 将x父节点设为“黑色”。
19                         color[right[w]] ← BLACK                ▹  Case 4   //   (03) 将x兄弟节点的右子节设为“黑色”。
20                         LEFT-ROTATE(T, p[x])                   ▹  Case 4   //   (04) 对x的父节点进行左旋。
21                         x ← root[T]                            ▹  Case 4   //   (05) 设置“x”为“根节点”。
22        else (same as then clause with "right" and "left" exchanged)        // 若 “x”是“它父节点的右孩子”,将上面的操作中“right”和“left”交换位置,然后依次执行。
23 color[x] ← BLACK   

参考资料

[1] 零声教育 Linux C/C++后端服务器架构开发 1.1.1
[2] 红黑树(一)之 原理和算法详细介绍 https://www.cnblogs.com/skywang12345/p/3245399.html



这篇关于c/c++Linux后台开发课程笔记 - 1.1.1红黑树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程