嘘~ 正在从服务器偷取页面 . . .

红黑树

二叉树 2-3树 红黑树
数据结构
发布日期:   2022-11-12
文章字数:   5.7k

学过了二叉查找树还有平衡二叉树以后，再看点更复杂的树形结构——红黑树，跟平衡二叉树一样，红黑树也是为了解决二叉搜索树不能自平衡的问题。红黑树是2-3树的变形，以2-3树的角度去理解红黑树会容易的多。

先回忆一下AVL树：

AVL树就是要保证插入结点后，任一结点对应的两棵子树的最大高度差为1，这样就可以保证整棵树的深度最小。

AVL虽然高度平衡，但是我们发现它每次插入或者删除结点的时候，树的平衡都可能被打破，而且如果要一直保证也就是动态的来使得这个 AVL 树达到平衡是需要很多操作的，太多步的操作反而会影响这个树形结构的的性能。除非是在树结构变化特别少的情况，不然我们让AVL 树平衡的时候，搜索性能的提升可能还不够抵消平衡树所带来的性能消耗。所以就相继出现了2-3树和红黑树。

1、2-3树

1、什么是2-3树

2-3树的意思就是说，一个父节点可以有两个子结点，也可以有三个子结点，并且其也满足类似二叉搜索树的定义（父结点的值大于左子树，但小于右子树），所有叶子节点都在同一层。

2-3树的某个节点会有两种可能，一是正常的2节点，二是3节点：

  • 2节点：父亲节点存储一个值，最多有左右两个子树。假设父节点为p，子节点为l(左节点)、r(有节点)，且满足：
    　　　　　　
    如下图：
  • 3节点：父亲节点存储两个值，最多有左中右三个子树。假设父节点分别为p1,p2，子节点分别为l(左节点)、m(中间节点)、r(右节点)，且满足：
    　　　　　
    如下图：

    一颗完整的2-3树就如下图所示：

2、2-3树的创建

假设有一组数据集合数组为{ 30, 13, 7, 43, 23, 12, 9, 33, 42, 21, 18, 6, 3, 50 }。

创建2-3树的过程：

1、将30作为根节点

2、插入13，13比30小，融合成一个值为（13 30）的3节点

3、插入7，7比13小，融合成一个值为（7 13 30）的4节点，然后分解

4、插入43，43大于13，43大于30，与30一起融合成3节点

5、插入23，23大于13，23小于30，与（30 43）融合成4节点，然后分解

6、插入12，12小于13，12大于7，与7融合成3节点

7、插入9，9小于13，9大于7，9小于12，与（7 12）融合成4节点，然后分解。分解后9升级到上一层，与（13 30）融合成4节点，再次分解

8、插入33，33大于13，33大于30，33小于43，与43融合成3节点

9、插入42，42大于13，42大于30，42大于33，42小于43，与（33 43）融合成4节点，然后分解

10、省略后面过程，最终生成结果为：

至此，我们创建了一颗2-3树，可以看出2-3树的平衡性还是很好的。

2、红黑树

尽管有平衡二叉树和2-3树了，但是现在用的多的还是红黑树，主要是因为红黑树有这4点的优势：
1、AVL的左右子树高度差不能超过1，每次进行插入/删除操作时，几乎都需要通过旋转操作保持平衡。
2、在频繁进行插入/删除的场景中，频繁的旋转操作使得AVL的性能大打折扣。
3、红黑树通过牺牲严格的平衡，换取插入/删除时少量的旋转操作，整体性能优于AVL。（红黑树插入时的不平衡，不超过两次旋转就可以解决；删除时的不平衡，不超过三次旋转就能解决。）
4、红黑树的红黑规则，保证最坏的情况下，也能在O(log2N)时间内完成查找操作。

1、将2-3树转换成红黑树

创建了一棵2-3树以后，我们就可以进行一些结构上的变化
将所有的3节点进行变换，并且满足三个条件：

  • 红链接均为左链接。
  • 没有任何一个节点同时和两条红链接相连。
  • 任意空链接到根节点路径上的黑色连接数目相同。

这三个条件均满足以后我们创建的就是一棵不那么标准的红黑树，如下图：

2、红黑树的性质

红黑树本身是一棵二叉查找树，在其基础上附加了两个要求：

  • 树中的每个结点增加了一个用于存储颜色的标志域；
  • 树中没有一条路径比其他任何路径长出两倍，整棵树要接近于“平衡”的状态。

路径：指的是从任何一个结点开始，一直到其子孙的叶子结点的长度；
接近于平衡：红黑树并不是平衡二叉树，只是由于对各路径的长度之差有限制，所以近似于平衡的状态。

下面图示的就是一棵典型的红黑树：

观察上图，可以发现红黑树的一些规律：
1、这些节点不是红色的就是黑色的，但是根节点是黑色的。
2、再看叶子节点，叶子节点跟普通的树不太一样，红黑树的叶子节点都是null节点（空节点）并且都为黑色的。
3、假设从根节点出发，然后从最左边的路径走到叶子节点，都没有连续的红色节点。所以可以得出一个结论，同一路径，不存在连续的红色节点。
以上观察出来的这三条规律就是红黑规则的一部分。

因此我们就可以得出红黑树的红黑规则了：

  • 性质1：每个结点要么是黑色，要么是红色。
  • 性质2：根节点是黑色。
  • 性质3：每个叶子结点（NIL）是黑色。
  • 性质4：每个红色结点的两个子结点一定都是黑色。
  • 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
  • 从性质5又可以推出：
        性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点

3、红黑树的术语约定


正在遍历的结点称做当前结点，如图2中的D，它的父亲叫做父结点，它的父亲的另外一个子结点叫做叔叔结点，父亲的父亲叫做祖父结点。

4、红黑树基本操作

$\color{red}{红黑树总是通过旋转和变色达到自平衡}$

1、左旋

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
void left_rotate(RBT_Node* x) //x 表示需要进行左旋的子树的根结点
{
	RBT_Node* y = x->right_Child;  //找到根节点的右子树
    x->right_Child = y->left_Child;  //将右子树的左孩子移动至节点x的右孩子处
        
    //y所指结点的左结点不为空
    if (y->left_Child != nil)
    {
    	y->left_Child->parent = x;
	}
    y->parent = x->parent;  //设置y的双亲结点为x的双亲节点
        
    //判断x节点是不是其父节点的左右子树
    if (x->parent == nil)
    {
		root = y;
	}
	else if (x->parent->left_Child == x)//x在左子树
    {
		x->parent->left_Child = y;
	}
    else  //x在右子树
    {
    	x->parent->right_Child = y;
    }
    x->parent = y;
    y->left_Child = x;
}

2、右旋

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
//右旋操作（与左子树操作基本相同）
void right_rotate(RBT_Node* x)
{
	RBT_Node* y = x->left_Child;
	x->left_Child = y->right_Child;
	if (y->right_Child != nil)
	{
		y->right_Child->parent = x;
	}
	y->parent = x->parent;
	if (x->parent == nil)
	{
		root = y;
	}
	else if (x->parent->left_Child == x)
	{
		x->parent->left_Child = y;
	}
	else
	{
		x->parent->right_Child = y;
	}
	x->parent = y;
	y->right_Child = x;
}

3、变色

结点的颜色由红变黑或由黑变红。

5、红黑树的插入

在创建红黑树或者向已有红黑树中添加新的数据时，其实我们只需要按部就班地执行以下3 步操作：
1、由于红黑树本身是一棵二叉查找树，所以在插入新的结点时，完全按照二叉查找树插入结点的方法，找到新结点插入的位置；
2、将新插入的结点结点初始化，颜色设置为红色后插入到指定位置；（将新结点初 始化为红色插入后，不会破坏红黑树第 5 条的性质）
3、由于插入新的结点，可能会破坏红黑树第 4 条的性质（若其父结点颜色为红色，就破坏了红黑树的性质），此时需要调整二叉查找树，想办法通过旋转以及修改树中结点的颜色，使其重新成为红黑树！

第一步和第二步都比较容易，与二叉查找树差不多，最麻烦的就是第三步对树的调整。在红黑树中插入结点时，根据插入位置的不同可分为以下 3 种情况，前两种都比较简单：

第一种，插入位置为整棵树的树根。处理办法：只需要将插入结点的颜色改为黑色即可。

第二种：如果插入位置的双亲结点的颜色为黑色。处理方法：此种情况不需要做任何工作，新插入的颜色为红色的结点不会破坏红黑树的性质。

第三种情况就麻烦了，插入位置的双亲结点的颜色为红色。同样的，我们也有相对应的处理方法：因为插入结点颜色为红色，并且双亲结点也是红色的，所以破坏了红黑树第 4 条性质，那么这个时候就需要结合其祖父结点和祖父结点的另一个孩子结点（即叔叔结点）的状态，在这里我们又要分成 3 种情况来讨论：

1、当前结点的父节点是红色，且“叔叔结点”也是红色，所以破坏了红黑树的第 4 条性质。此时的解决方案就是：我们将父结点颜色改为黑色；将叔叔结点颜色改为黑色；再将祖父结点颜色改为红色；下一步将祖父结点认做当前结点，继续判断，处理结果如下图所示：

分析：此种情况下，由于父结点和当前结点颜色都是红色，所以为了不产生冲突，将父结点的颜色改为黑色。但是虽避免了破坏第 4 条，但是却导致该条路径上的黑高度增加了 1 ，破坏了第 5 条性质。但是在将祖父结点颜色改为红色、叔叔结点颜色改为黑色后，该部分子树没有破坏第 5 条性质。但是由于将祖父结点的颜色改变，还需判断是否破坏了上层树的结构，所以需要将祖父结点看做当前结点，继续判断。

2、当前结点的父结点颜色为红色，叔叔结点颜色为黑色，且当前结点是父结点的右孩子。解决方案：将父结点作为当前结点做左旋操作。

在进行以父结点为当前结点的左旋操作后，此种情况就转变成了第 3 种情况，处理过程跟第 3 种情况同步进行。

3、当前结点的父结点颜色为红色，叔叔结点颜色为黑色，且当前结点是父结点的左孩子。解决方案：将父结点颜色改为黑色，祖父结点颜色改为红色，从祖父结点处进行右旋处理。如下图所示：

分析：在此种情况下，由于当前结点 F 和父结点 S 颜色都为红色，违背了红黑树的性质 4，此时可以将 S 颜色改为黑色，又违反了性质 5，因为所有通过 S 的路径其黑高度都增加了 1 ，所以需要将其祖父结点颜色设为红色后紧接一个右旋，这样这部分子树有成为了红黑树。（上图中的右图虽看似不是红黑树，但是只是整棵树的一部分，以 S 为根结点的子树一定是一棵红黑树)

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
RBT_Node* Insert_BST(RBT_Node*& p, RBT_Node*& r, const int& v)
{
	if (r == nil)
	{
		//数为空
		r = new RBT_Node(v, RED, nil, nil, p);
		if (p == nil)
		{
			root = r;
		}
		if (v > p->val)  //插入的节点键值小于父节点的键值
		{
			p->right_Child = r;  //则该节点成为父节点右孩子
		}
		else
		{
			p->left_Child = r;  //则该节点成为父节点右孩子
		}
	}
	
	//若不为空，则一直搜索直至找到空
	else
	{
		if (v < r->val)
		{
			return Insert_BST(r,r->left_Child, v);  //利用递归进行调用
		}
		else
		{
			return Insert_BST(r,r->right_Child, v);
		}
	}
	return r;
}

//插入后的调整函数
void insert(const int& v)
{
	RBT_Node* z = Insert_BST(nil, root, v);
	//首先判断其父节点颜色为红色时才需要调整；为黑色时直接插入即可，不需要调整
	while (z->parent->color == RED)  //父节点的颜色为红色
	{
		//由于还涉及到其叔叔节点，所以此处需分开讨论，确定父节点是祖父节点的左孩子还是右孩子
		if (z->parent->parent->left_Child == z->parent)  //父节点是左节点
		{
			//叔节点为红色
			if (z->parent->parent->right_Child->color == RED)  
			{
				/*如果叔叔结节点颜色为红色，此为第 1 种情况，
				处理方法为：父节点颜色改为黑色；叔叔节点颜色改为黑色；祖父节点颜色改为红色，将祖父节点赋值为当前结点，继续判					断；*/
				z->parent->color = BLACK;  //父节点
				z->parent->parent->right_Child->color = BLACK;  //叔节点
				z->parent->parent->color = RED;  //祖父节点
				z = z->parent->parent;  
			}
			/*反之，如果叔叔节点颜色为黑色，
			此处需分为两种情况：1、当前节点是父节点的右孩子；2、当前节点是父节点的左孩子*/
			else
			{
				/*当前节点的父节点颜色为红色，叔叔节点颜色为黑色，且当前节点是父节点的右孩子。
				解决方案：将父节点作为当前节点做左旋操作。*/
				if (z->parent->right_Child == z)
				{
					z = z->parent;
					left_rotate(z);
				}
				/*当前节点的父节点颜色为红色，叔叔节点颜色为黑色，且当前节点是父节点的左孩子。
				解决方案：将父节点颜色改为黑色，祖父节点颜色改为红色，从祖父节点处进行右旋处理。*/
				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				right_rotate(z->parent->parent);
			}
		}
            
		/*如果父节点时祖父节点的右孩子只需将以上代码部分中的left改为right即可，道理是一样的。*/
		else
		{
			if (z->parent->parent->left_Child->color == RED)
			{
				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				z->parent->parent->left_Child->color = BLACK;
				z = z->parent->parent;
			}
			else
			{
				if (z->parent->left_Child == z)
				{
					z = z->parent;
					right_rotate(z);
				}
				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				left_rotate(z->parent->parent);
			}
		}
	}
	root->color = BLACK;  //将根节点的颜色设置为黑色
}

6、红黑树的删除

删除节点要比插入节点简单一点，在红黑树中删除结点，只需要完成 2 步操作：
1、将红黑树按照二叉查找树删除结点的方法删除指定结点；
2、重新调整删除结点后的树，使之重新成为红黑树；（还是通过旋转和重新着色的方式进行调整）

在树删除结点的时候，又要分为 3 种情况：

第一种：若该删除结点本身是叶子结点，则可以直接删除；

第二种：若只有一个孩子结点（左孩子或者右孩子），则直接让其孩子结点顶替该删除结点；

第三种：若有两个孩子结点，则找到该结点的右子树中值最小的叶子结点来顶替该结点，然后删除这个值最小的叶子结点。

以上这三种情况最终都需要删除某个结点，所以我们此时需要判断删除该结点是否会破坏红黑树的性质。判断的依据是：

  • 如果删除结点的颜色为红色，则不会破坏；
  • 如果删除结点的颜色为黑色，则肯定会破坏红黑树的第 5 条性质，此时就需要对树进行调整，调整方案又分成4种情况讨论：

1、删除结点的兄弟结点颜色是红色，调整措施为：将兄弟结点颜色改为黑色，父亲结点改为红色，以父亲结点来进行左旋操作，同时更新删除结点的兄弟结点（左旋后兄弟结点发生了变化），如下图所示：

2、删除结点的兄弟结点及其孩子全部都是黑色的，调整措施为：将删除结点的兄弟结点设为红色，同时设置删除结点的父结点标记为新的结点，继续判断；

3、删除结点的兄弟结点是黑色，其左孩子是红色，右孩子是黑色。调整措施为：将兄弟结点设为红色，兄弟结点的左孩子结点设为黑色，以兄弟结点为准进行右旋操作，最终更新删除结点的兄弟结点；

4、删除结点的兄弟结点是黑色，其右孩子是红色（左孩子不管是什么颜色），调整措施为：将删除结点的父结点的颜色赋值给其兄弟结点，然后再设置父结点颜色为黑色，兄弟结点的右孩子结点为黑色，根据其父结点做左旋操作，最后设置替换删除结点的结点为根结点；

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
void RBT_Transplant(RBT_Node*& u, RBT_Node*& v)
{
    if (u->parent == nil)
    {
        root = v;
    }
    else if (u == u->parent->left_Child)
    {
        u->parent->left_Child = v;
    }
    else
    {
        u->parent->right_Child = v;
    }
    v->parent = u->parent;
}

//删除节点
void Delete_RBT(RBT_Node* z)
{
    RBT_Node* y = z;
    bool delcol = y->color;
    RBT_Node* x = z;
    /*如果只有一个孩子结点（只有左孩子或只有右孩子），
    直接用孩子结点顶替该结点位置即可（没有孩子结点的也走此判断语句）。*/
    if (z->left_Child == nil)
    {
        x = z->right_Child;
        RBT_Transplant(z, z->right_Child);
    }
    else if (z->right_Child == nil)
    {
        x = z->left_Child;
        RBT_Transplant(z, z->left_Child);
    }
    //如果两个孩子，就找到右子树中最小的结点，将之代替，然后直接删除该结点即可
    else
    {
        y = Find_min(z->right_Child);
        delcol = y->color;
        x = y->right_Child;
        if (y->parent == z)
        {
            x->parent = y;
        }
        else
        {
            RBT_Transplant(y, y->right_Child);
            y->right_Child = z->right_Child;
            y->right_Child->parent = y;
        }
        RBT_Transplant(z, y);
        y->left_Child = z->left_Child;
        y->left_Child->parent = y;
        y->color = z->color;
    }
    /*在删除该结点之前，需判断此结点的颜色：如果是红色，直接删除，不会破坏红黑树；
    若是黑色，删除后会破坏红黑树的第 5 条性质，需要对树做调整。*/
    if (delcol == BLACK)
    {
        Delete_Fixup_RBT(x);
    }
}

void Delete_RBT(const int& v)
{
    RBT_Node* z = Get_Node(root, v);
    if (z == nil)
    {
        return;
    }
    Delete_RBT(z);
}

//删除后调整树节点
void Delete_Fixup_RBT(RBT_Node* x)
{
    while (x != root && x->color == BLACK)
    {
        if (x == x->parent->left_Child)
        {
            RBT_Node* w = x->parent->right_Child;
            /*第 1 种情况：删除节点的兄弟节点颜色是红色。
            解决方案为：将兄弟节点颜色改为黑色，父亲节点改为红色，以父亲节点来进行左旋操作，同时更新删除结点的兄弟结点（左旋后			 兄弟结点发生了变化）*/
            if (w->color == RED)
            {
                w->color = BLACK;
                x->parent->color = RED;
                left_rotate(x->parent);
                w = x->parent->right_Child;
            }
            /*第2种情况：删除节点的兄弟节点及其孩子全部都是黑色的。
            解决方案为：将删除节点的兄弟结点设为红色，同时设置删除节点的父节点标记为新的结点，继续判断*/
            if (w->left_Child->color == BLACK && w->right_Child->color== BLACK)
            {
                w->color = RED;
                x = x->parent;
            }
            else
            {
                /*第3种情况：删除节点的兄弟结点是黑色，其左孩子是红色，右孩子是黑色。
                解决方案为：将兄弟节点设为红色，兄弟节点的左孩子结点设为黑色，以兄弟节点为准进行右旋操作，最终更新删除结点的兄				    弟节点*/
                if (w->right_Child->color == BLACK)
                {
                    w->left_Child->color = BLACK;
                    w->color = RED;
                    right_rotate(w);
                    w = x->parent->right_Child;
                }
                /*第4种情况：删除节点的兄弟结点是黑色，其右孩子是红色（左孩子不管是什么颜色）
                解决方案为：将删除节点的父节点的颜色赋值给其兄弟节点，然后再设置父节点颜色为黑色，兄弟节点的右孩子节点为黑色，				    根据其父节点做左旋操作，最后设置替换删除节点的结点为根结点；将删除节点的父节点的颜色赋值给其兄弟节点，然后再设				    置父节点颜色为黑色，兄弟节点的右孩子节点为黑色，根据其父节点做左旋操作，最后设置替换删除节点的结点为根节点*/
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right_Child->color = BLACK;
                left_rotate(x->parent);
                x = root;
            }
        }
        else
        {
            RBT_Node* w = x->parent->left_Child;
            if (w->color == RED)
            {
                w->color = BLACK;
                x->parent->color = RED;
                right_rotate(x->parent);
                w = x->parent->left_Child;
            }
            if (w->right_Child->color == BLACK && w->left_Child->color== RED)
            {
                w->color = RED;
                x = x->parent;
            }
            else
            {
                if (w->left_Child->color == BLACK)
                {
                    w->right_Child->color = BLACK;
                    w->color = RED;
                    left_rotate(w);
                    w = x->parent->left_Child;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left_Child->color = BLACK;
                right_rotate(x->parent);
                x = root;
            }
        }
    }
    x->color = BLACK;
}

6、红黑树的应用

1、散列表的冲突处理
map的实现，底层一般会采用红黑树，在节点多的时候效率高。
在节点少的时候，可用链表方式。

2、动态插入、删除和查询较多的场景

文章作者: Jeremy Yang
文章链接: https://www.jeremyyang.github.io/2022/11/12/hong-hei-shu/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Jeremy Yang !
二叉树 2-3树 红黑树
赏
  目录