[数据结构与算法]红黑树C语言代码实现（插入，删除）

#define _CRT_SECURE_NO_WARNINGS
/*vs studio不用这句话会给scanf报错*/
#include <stdio.h>
#include<stdlib.h>
#define RED 1
#define BLACK 0
typedef struct rbtree_node {
	int weight;
	int color;
	struct rbtree_node* left, * right, * parent;
}*tree;
typedef struct rbtree_root {
	tree root;
	tree nil;//叶节点
}*tree_root;
tree_root make_root();
void make_tree(tree_root root);
tree_root insert_tree(tree_root root, tree X);
void left_rotate(tree_root root, tree X);
void right_rotate(tree_root root, tree X);
tree find(tree_root root, tree temp, int X, int* flag);
void exchange_color(tree a, tree b);
void PreorderTraversal(tree_root root, tree BT);
void InorderTraversal(tree_root root, tree BT);
void delete_tree(tree_root, int X);
tree find_min(tree_root root, tree temp);
tree get_brother(tree temp);
void delete_x(tree temp);
tree delete_treeLeft(tree_root root, tree temp);
tree delete_treeRight(tree_root root, tree temp);
tree delete_treeplus(tree_root root, tree temp);
void destroy_tree(tree_root root, tree BT);
void destroy_root(tree_root root);
void display(tree_root root);
void delete_input(tree_root root);

int main() {
	tree_root root = make_root();
	make_tree(root);
	display(root);
	delete_input(root);
	display(root);
	destroy_tree(root, root->root);
	destroy_root(root);
	return 0;
}
void make_tree(tree_root root) {
	int treeAmount;
	int weight;
	printf("请输入结点数目:\n");
	scanf("%d", &treeAmount);
	for (int i = 0; i < treeAmount; i++) {
		scanf("%d", &weight);
		tree temp = (tree)malloc(sizeof(struct rbtree_node));//建结点
		temp->color = RED;//新结点默认红色
		temp->weight = weight;
		temp->parent = temp->left = temp->right = root->nil;
		root = insert_tree(root, temp);//插入结点
	}
	return;
}
tree_root insert_tree(tree_root root, tree X) {
	if (root->root == root->nil) {//空树
		root->root = X;
		root->root->color = BLACK;
		root->root->parent = root->nil;
	}
	else {
		int flag = 1;//查看元素是否已经存在
		if (X->parent == root->nil && X != root->root) {//判断X是否新插入的结点
			tree temp = find(root, root->root, X->weight, &flag);
			if (flag) {//元素不存在，插入
				if (X->weight < temp->weight)
					temp->left = X;
				else
					temp->right = X;
				X->parent = temp;
			}
			else {
				printf("插入元素%d已存在\n", X->weight);
				free(X);
				return root;
			}
		}
		if (X->parent->color == RED) {//插入后，出现两个连续红色
			if (X->parent->parent->left->color == X->parent->parent->right->color) {//父亲和伯伯颜色一样，两者都是红色
				X->parent->parent->left->color = X->parent->parent->right->color = BLACK;
				if (X->parent->parent != root->root) {//爷爷不是根结点
					X->parent->parent->color = RED;
					insert_tree(root, X->parent->parent);//爷爷作为新结点，检查是否和曾爷爷同为红色
				}
			}
			else if (X->parent->parent->left->color == RED) {//父亲和伯伯颜色不一样，且父亲在爷爷的左子树
				if (X->parent->right->color == RED) {
					X = X->parent;
					left_rotate(root, X);
				}
				exchange_color(X->parent, X->parent->parent);
				right_rotate(root, X->parent->parent);
			}
			else {//父亲和伯伯颜色不一样，父亲在爷爷的右子树
				if (X->parent->left->color == RED) {
					X = X->parent;
					right_rotate(root, X);
				}
				exchange_color(X->parent, X->parent->parent);
				left_rotate(root, X->parent->parent);
			}
		}
	}
	return root;
}
tree_root make_root() {//建立根结点及叶结点
	tree_root temp = (tree_root)malloc(sizeof(struct rbtree_root));
	temp->nil = (tree)malloc(sizeof(struct rbtree_node));
	temp->nil->color = BLACK;
	temp->nil->weight = 0;
	temp->nil->parent = temp->nil->left = temp->nil->right = NULL;
	temp->root = temp->nil;
	return temp;
}
tree find(tree_root root, tree temp, int X, int* flag) {
	if (temp->weight < X) {
		if (temp->right != root->nil) {
			return find(root, temp->right, X, flag);
		}
		else {
			return temp;//X不在树中，且temp应该作为X的父亲
		}

	}
	else if (temp->weight > X) {
		if (temp->left != root->nil) {
			return find(root, temp->left, X, flag);
		}
		else {
			return temp;
		}
	}
	else if (temp->weight == X) {
		*flag = 0;//在树中找到元素，flag变0
		return temp;
	}
}
void exchange_color(tree a, tree b) {
	int color = a->color;
	a->color = b->color;
	b->color = color;
	return;
}
void left_rotate(tree_root root, tree X) {//左旋
	X->right->parent = X->parent;
	if (X != root->root) {
		if (X->parent->left == X)
			X->parent->left = X->right;
		else
			X->parent->right = X->right;
	}
	X->parent = X->right;
	if (X->right->left != root->nil)
		X->right->left->parent = X;
	X->right = X->right->left;
	X->parent->left = X;
	if (X == root->root) {
		root->root = X->parent;
		root->root->color = BLACK;
	}
	return;
}
void right_rotate(tree_root root, tree X) {//右旋
	X->left->parent = X->parent;//X的左儿子向X父亲建立关系
	if (X->parent->left == X)//X父亲向X左儿子建立关系
		X->parent->left = X->left;
	else
		X->parent->right = X->left;
	X->parent = X->left;//X向左儿子建立关系
	X->left->right->parent = X;//X的左儿子的右儿子向X建立关系
	X->left = X->left->right;//X向X的左儿子的右儿子建立关系
	X->parent->right = X;//X现在的父亲向X建立关系
	if (X == root->root) {//更换根结点
		root->root = X->parent;
		//root->root->color = BLACK;
	}
	return;
}
void PreorderTraversal(tree_root root, tree BT)
{
	if (BT != root->nil) {
		printf("%d,", BT->weight, BT->color);
		if (BT->color == 1)
			printf("红\t");
		else
			printf("黑\t");
		PreorderTraversal(root, BT->left);
		PreorderTraversal(root, BT->right);
	}
}
void InorderTraversal(tree_root root, tree BT)
{
	if (BT != root->nil) {
		InorderTraversal(root, BT->left);
		printf("%d,", BT->weight);
		if (BT->color == 1)
			printf("红\t");
		else
			printf("黑\t");
		InorderTraversal(root, BT->right);
	}
}
void delete_tree(tree_root root, int X) {//这种情况下的X必然有一个空的子结点，情况简单
	int flag = 1;
	tree temp = find(root, root->root, X, &flag);
	tree mark = temp;
	if (flag) {
		printf("要删除的元素不存在\n");
		return;
	}
	if (temp->right == root->nil) {//X不存在右子树
		if (temp->color == BLACK && temp->left->color == RED) {//这种情况换值后直接删
			temp->weight = temp->left->weight;
			delete_x(temp->left);
			return;
		}
		if (temp->color == RED) {//直接删
			delete_x(temp);
			return;
		}
		if (temp == root->root) {//树只有X一个结点，删了树变空
			free(temp);
			root->root = root->nil;
			return;
		}
	}
	if (temp->right != root->nil) {//寻找X右子树的最小值，将最小值放入X结点，问题转变成删除X右子树最小值的结点
		temp = find_min(root, temp->right);
		mark->weight = temp->weight;
		temp->weight = X;
	}
	if (temp->color == RED) {//红色直接删
		delete_x(temp);
		return;
	}

	if (temp->right->color == RED) {//换值后直接删
		temp->weight = temp->right->weight;
		delete_x(temp->right);
		return;
	}
	tree to_delete = delete_treeplus(root, temp);//其他情况，此时X必为黑色
	delete_x(to_delete);
}
tree find_min(tree_root root, tree temp) {
	while (temp->left != root->nil)
		temp = temp->left;
	return temp;
}
tree get_brother(tree temp) {
	if (temp->parent->left != temp)
		return temp->parent->left;
	else
		return temp->parent->right;
}
void delete_x(tree temp) {
	if (temp == temp->parent->right) {
		temp->parent->right = temp->right;
		temp->right->parent = temp->parent;
	}
	else {
		temp->parent->left = temp->right;
		temp->right->parent = temp->parent;
	}
	free(temp);
	return;
}
tree delete_treeLeft(tree_root root, tree temp) {//删除结点在父亲的左子树上
	if (temp->color == RED) {//一次性直接删除成功的话不会触发这个，触发这个的时候，X（temp)的子树的黑权重必然比X的兄结点的子树少1
		temp->color = BLACK;
		return temp;
	}
	if (temp->parent->color == BLACK) {
		tree brother = get_brother(temp);
		if (brother == root->nil)
			return temp;//不是一次性删除可能会出现这种情况，直接返回就行
		if (brother->color == BLACK) {
			if (brother->right->color == RED) {//兄弟右儿子红色
				brother->right->color = BLACK;
				left_rotate(root, brother->parent);
				return temp;
			}
			if (brother->left->color == RED) {//兄弟左儿子红色
				brother->left->color = BLACK;
				right_rotate(root, brother);
				left_rotate(root, temp->parent);
				return temp;
			}
			if (brother->left->color == BLACK && brother->right->color == BLACK) {//最麻烦的情况
				if (temp->left->color == RED || temp->right->color == RED){ //一次性删除不会触发这个。同时减少父亲另一边的黑权重，使左右黑权重平衡
					brother->color = RED;
					if (temp->parent != root->root) {//三个黑色这种情况，如果没回溯到根结点，这样处理会导致根的左右黑权重不平衡。
						//解决方法一是回溯时触发其他颜色的情况，会直接解决平衡问题。二是回溯到根结点，还是三个黑，再这样处理根另一边黑权重-1，重新平衡。
						delete_treeplus(root, temp->parent);
					}
					return temp;
				}
			temp->color = RED;
			brother->color = RED;
			brother->parent->color = BLACK;
			if (brother->parent != root->root)//不是根结点这种处理会使根左右黑权重不平衡
				delete_treeplus(root, temp->parent);
			return temp;
			}
		}
		else {//父亲为黑，兄弟为红，此情况转化成父亲黑色，兄弟黑色再做处理
			exchange_color(brother, brother->parent);
			left_rotate(root, brother->parent);
		}
	}
	if (temp->parent->color == RED) {
		tree brother = get_brother(temp);
		/*if (brother == root->nil) {
			temp->parent->color = BLACK;
			printf("不会发生");
			return temp;
		}*/
		if (brother->right->color == RED) {//兄弟右儿子为红
			exchange_color(brother, brother->right);
			temp->parent->color = BLACK;
			left_rotate(root, brother->parent);
			return temp;
		}
		if (brother->left->color == BLACK && brother->right->color == BLACK) {//兄弟结点左右儿子为空或者黑色
			exchange_color(brother, brother->parent);
			return temp;
		}
		else {//兄弟结点左儿子为红色的情况
			temp->parent->color = BLACK;
			right_rotate(root, brother);
			left_rotate(root, temp->parent);
			return temp;
		}
	}
}
tree delete_treeRight(tree_root root, tree temp) {//删除结点在父亲的右子树上，处理基本为Left的镜像
	if (temp->color == RED) {
		temp->color = BLACK;
		return temp;
	}
	if (temp->parent->color == BLACK) {
		tree brother = get_brother(temp);
		if (brother == root->nil)
			return temp;
		if (brother->color == BLACK) {
			if (brother->left->color == RED) {
				brother->left->color = BLACK;
				right_rotate(root, temp->parent);
				return temp;
			}
			if (brother->right->color == RED) {
				brother->right->color = BLACK;
				left_rotate(root, brother);
				right_rotate(root, temp->parent);
				return temp;
			}
			if (brother->left->color == BLACK && brother->right->color == BLACK) {
				if (temp->left->color == RED || temp->right->color == RED) {
					brother->color = RED;
					if (temp->parent != root->root) {
						delete_treeplus(root, temp->parent);
					}
					return temp;
				}
				temp->color = RED;
				brother->color = RED;
				brother->parent->color = BLACK;
				if (brother->parent != root->root) {
					delete_treeplus(root, temp->parent);
				}
				return temp;
			}
		}
		else {
			exchange_color(brother, brother->parent);
			right_rotate(root, brother->parent);
		}
	}
	if (temp->parent->color == RED ) {
		tree brother = get_brother(temp);
		/*if (brother == root->nil) {
			temp->parent->color = BLACK;
			printf("不会发生");
			return temp;
		}*/
		if (brother->left->color == BLACK && brother->right->color == BLACK) {
			brother->parent->color = BLACK;
			brother->color = RED;
			return temp;
		}
		if (brother->left->color == RED) {
			exchange_color(brother, brother->left);
			temp->parent->color = BLACK;
			right_rotate(root, temp->parent);
			return temp;
		}
		else {
			temp->parent->color = BLACK;
			left_rotate(root, brother);
			right_rotate(root, temp->parent);
			return temp;
		}
	}
}
tree delete_treeplus(tree_root root, tree temp) {
	if (temp->parent->right == temp)
		return delete_treeRight(root, temp);
	else
		return delete_treeLeft(root, temp);
}
void destroy_tree(tree_root root, tree BT)
{
	if (BT != root->nil) {
		destroy_tree(root, BT->left);
		destroy_tree(root, BT->right);
		free(BT);
	}
}
void destroy_root(tree_root root) {
	free(root->nil);
	free(root);
}
void delete_input(tree_root root) {
	printf("\n请输入要删除的树的数量:\n");
	int number;
	scanf("%d", &number);
	for (int i = number; i > 0; i--) {
		scanf("%d", &number);
		delete_tree(root, number);
	}
}
void display(tree_root root) {
	PreorderTraversal(root, root->root);
	printf("\n");
	printf("------------------------------------------------------------------------------------------\n");
	InorderTraversal(root, root->root);
}

参考了这篇文章：https://blog.csdn.net/weewqrer/article/details/51866488?utm_source=app&app_version=4.15.0&code=app_1562916241&uLinkId=usr1mkqgl919blen

如果发现数据出问题，欢迎反馈