数据结构与算法——第9章-查找表-红黑树的旋转(9.8.2)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 概述

1
2
3
1.旋转操作
2.左旋操作
3.右旋操作

二 旋转操作

1
2
3
4
5
当使用红黑树进行插入或者删除结点的操作时，可能会破坏红黑树的 5 条性质，
从而变成了一棵普通树，此时就可以通过对树中的某些子树进行旋转，从而使整棵树重新变为一棵红黑树。

旋转操作分为左旋和右旋，同二叉排序树转平衡二叉树的旋转原理完全相同。
例如图 2 表示的是对一棵二叉查找树中局部子树进行左旋和右旋操作：

三 左旋操作

3.1 如何操作

1
2
3
左旋：如图 2 所示，左旋时 y 结点变为该部分子树的根结点，
同时 x 结点（连同其左子树 a）移动至 y 结点的左孩子。
若 y 结点有左孩子 b，由于 x 结点需占用其位置，所以调整至 x 结点的右孩子处。

3.2 左旋操作的具体实现函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//T 表示为树根，x 表示需要进行左旋的子树的根结点
void rbTree_left_rotate( RBT_Root* T, RB_TREE* x) {
	RB_TREE* y = x->right;//找到根结点的右子树
	x->right = y->left;//将右子树的左孩子移动至结点 x 的右孩子处
	if(x->right != T->nil) { //如果 x 的右子树不是 nil，需重新连接 右子树的双亲结点为 x
		x->right->p = x;
	}
	y->p = x->p;//设置 y 的双亲结点为 x 的双亲结点
	//重新设置 y 的双亲结点同 y 的连接，分为 2 种情况：1、原 x 结点本身就是整棵树的数根结点，此时只需要将 T 指针指向 y；2、根据 y 中
	关键字同其父结点关键字的值的大小，判断 y 是父结点的左孩子还是右孩子
	if(y->p == T->nil) {
		T->root = y;
	} else if(y->key < y->p->key) {
		y->p->left = y;
	} else {
		y->p->right = y;
	}
	y->left = x;//将 x 连接给 y 结点的左孩子处
	x->p = y;//设置 x 的双亲结点为 y。
}

四 右旋操作

4.1 如何操作

1
2
右旋：如图 2 所示，同左旋是同样的道理，x 结点变为根结点，同时 y 结点连同其右子树 c 作为 x 结点的右子树，
原 x 结点的右子树 b 变为 y 结点的左子树。

4.2 右旋的具体代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void rbTree_right_rotate( RBT_Root* T, RB_TREE* x) {
	RB_TREE * y = x->left;
	x->left = y->right;
	if(T->nil != x->left) {
		x->left->p = x;
	}
	y->p = x->p;
	if(y->p == T->nil) {
		T->root = y;
	} else if(y->key < y->p->key) {
		y->p->left= y;
	} else {
		y->p->right = y;
	}
	y->right = x;
	x->p = y;
}

五 参考

  • C语言中文网—红黑树（更高级的二叉查找树）算法详解