红黑树代码详解

1.什么叫红黑树

红黑树（Red-Black Tree）是一种自平衡二叉查找树（Self-Balancing Binary Search Tree），它的设计目的是在插入和删除操作时保持树的平衡，从而保证树的高度在对数级别，进而保证查找、插入和删除操作的时间复杂度为 。

2.红黑树的性质

红黑树通过引入节点颜色（红色和黑色）来实现自平衡。每个节点都有一个颜色属性，可以是红色或黑色。红黑树满足以下五个性质：

1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色。
3. 每个叶子节点（NIL节点，空节点）是黑色。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的（即不能有两个连续的红色节点）。
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（黑高相等）。

3.红色和黑色的意义

3.1. 颜色的引入：
- 红色：表示该节点与其父节点之间存在一种特殊的父子关系，可以理解为“延伸”的关系。红色节点的存在允许树在某些情况下暂时失去平衡，但通过旋转和重新着色操作可以恢复平衡。
- 黑色：表示该节点与其父节点之间是一种正常的父子关系，黑色节点的引入是为了确保树的平衡性。

3.2. 性质的作用：
1.平衡性:
红黑树通过上述性质确保树的高度在对数级别，从而保证操作的时间复杂度为 。
2.效率：
相比于 AVL 树(自平衡二叉树)，红黑树的旋转次数较少，因此在插入和删除操作时更加高效。
3.实现复杂度：
虽然红黑树的实现比简单的二叉查找树复杂，但相比其他自平衡树（如 AVL 树），红黑树的实现相对简单且高效。
## 红黑树的左旋操作

4.红黑树的左旋操作

假设待左旋的结构中，X为父节点，Y为孩子节点。左旋操作后，Y节点代替X节点的位置，X节点成为Y节点的左孩子，x节点的左孩子成为y节点的右孩子b。

4.1 代码

void rbtree_left_rotate(rbtree *T, rbtree_node *x) {
	rbtree_node *y = x->right;  // x  --> y  ,  y --> x,   right --> left,  left --> right
	
	x->right = y->left; //1 1
	if (y->left != T->nil) { //1 2 y的左子树不是空节点
		y->left->parent = x;
	}
	y->parent = x->parent; //1 3
	if (x->parent == T->nil) { //1 4 x如果是根节点，y变成根节点
		T->root = y;
	} else if (x == x->parent->left) {// x不是根节点，x是他父亲节点的左子树
		x->parent->left = y;
	} else {// x不是根节点，x是他父亲节点的右子树
		x->parent->right = y;
	}

	y->left = x; //1 5
	x->parent = y; //1 6
}

5.红黑树的右旋操作

假设待右旋的结构中，y为父节点，x为孩子节点。右旋操作后，x节点代替y节点的位置，y节点成为x节点的右孩子，b节点的右孩子成为y节点的左孩子。

5.1 代码

void rbtree_right_rotate(rbtree *T, rbtree_node *y) {
	rbtree_node *x = y->left;
	y->left = x->right;
	if (x->right != T->nil) {//x的右子树不是空节点
		x->right->parent = y;
	}
	x->parent = y->parent;
	if (y->parent == T->nil) {//y如果是根节点，x变成根节点
		T->root = x;
	} else if (y == y->parent->right) {// y不是根节点，y是他父亲节点的右子树
		y->parent->right = x;
	} else {// y不是根节点，y是他父亲节点的左子树
		y->parent->left = x;
	}
	x->right = y;
	y->parent = x;
}

6.插入和删除操作

在插入和删除操作时，红黑树会通过旋转和重新着色来维护上述性质。这些操作包括：

• 左旋 和 右旋：改变树的结构，但保持二叉查找树的性质。
• 重新着色：改变节点的颜色，以满足红黑树的性质。

6.1示例

假设有一个红黑树，初始状态如下：

    10(B)
   /    \
 5(R)   15(B)

• 根节点 10 是黑色的。
• 节点 5 是红色的。
• 节点 15 是黑色的。
  在这个树中，所有性质都得到了满足：
  • 每个节点要么是红色，要么是黑色。
  • 根节点 10 是黑色的。
  • 每个叶子节点（NIL节点）是黑色的。
  • 没有两个连续的红色节点。
  • 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点。

6.2插入操作示例

假设我们要插入节点 3：

1. 插入节点：

• 插入节点 3 作为 5 的左子节点，颜色为红色。（为什么一开始要红色的？一开始插入红色不改变红黑树性质，如果是黑色，那就会影响红黑树的性质）
• 树变为：

	    10(B)
	   /    \
	5(R)   15(B)
	/  
3(R)

2. 检查性质：
   检查性质4，发现 5 和 3 都是红色的，违反了性质4。
3. 修复性质：
   通过旋转和重新着色来修复性质。例如，可以进行左旋和重新着色：

    10(B)
   /    \
3(R)   15(B)
   \
 5(B)

6.3 插入代码

void rbtree_insert(rbtree *T, rbtree_node *z) {
	rbtree_node *y = T->nil;
	rbtree_node *x = T->root;
	//循环查找节点要插入的位置，一直找到底
	while (x != T->nil) {
		y = x;//保存节点值，
		if (z->key < x->key) {//插入的节点值小于节点里面的K值，往左查找
			x = x->left;
		} else if (z->key > x->key) {//插入的节点值大于节点里面的K值，往右查找
			x = x->right;
		} else { //Exist ，插入的节点k值等于节点里面的K值，返回
			return ;
		}
	}
	//插入节点Y 的左子树或者右子树
	z->parent = 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;//一开始插入红色不改变红黑树性质，如果是黑色，那就会影响红黑树的性质
	//调整
	rbtree_insert_fixup(T, z);
}
void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {
	//z节点的父节点是红色，才需要调整
	while (z->parent->color == RED) { //z ---> RED
		if (z->parent == z->parent->parent->left) {//z节点的父节点 == 祖父节点的左子树
			rbtree_node *y = z->parent->parent->right;//祖父节点的右子树（叔父节点）
			if (y->color == RED) {//叔父节点是红色
				z->parent->color = BLACK;//父亲节点设置为黑
				y->color = BLACK;//叔父节点设置为黑
				z->parent->parent->color = RED;//祖父节点设置为红

				z = z->parent->parent; //z --> RED （往上回溯）
			} else {//叔父节点是黑色

				if (z == z->parent->right) {//z是父节点的右子树
					z = z->parent;
					rbtree_left_rotate(T, z);//左旋
				}

				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				rbtree_right_rotate(T, z->parent->parent);//右旋转
			}
		}else {//z节点的父节点 == 祖父节点的右子树
			rbtree_node *y = z->parent->parent->left;
			if (y->color == RED) {
				z->parent->color = BLACK;
				y->color = BLACK;
				z->parent->parent->color = RED;

				z = z->parent->parent; //z --> RED
			} else {
				if (z == z->parent->left) {
					z = z->parent;
					rbtree_right_rotate(T, z);
				}

				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				rbtree_left_rotate(T, z->parent->parent);
			}
		}
		
	}

	T->root->color = BLACK;
}

7.总结

红黑树通过引入节点颜色和相关的性质，确保树的高度在对数级别，从而保证高效的查找、插入和删除操作。