数据结构-----红黑树（全）

​

//根据key查找
Node* Search_key(rbtree* T, int target) {
	assert(T);
	assert(T->root);
	Node* cur = T->root;
	while (cur) {
		if (cur->key == target)
			return cur;//找到就返回
		else if (cur->key > target)
			cur = cur->left;
		else
			cur = cur->right;
	}
	printf("The target is not exist\n");
	return NULL;
}

​

#include
#include
#include
#include
 
//宏定义颜色
#define red 0
#define black 1
 
//数据类型Datatype
typedef char Datatype;
//红黑树节点存储结构
typedef struct node {
	Datatype data;
	int color;
	int key;
	struct node* par;//父节点指针
	struct node* left, * right;//左右子节点指针
}Node;
 
//红黑树的定义rbtree
typedef struct tree {
	Node* root;//指向根节点指针
	Node* nil;//叶子节点（哨兵）
}rbtree;
 
 
//创建初始化红黑树
rbtree* Create_inittree();
//插入数据
void Insert_node(rbtree* T, Datatype data, int key);
//已有数据，自增加key创建红黑树
void Create_wholetree(rbtree* T, Datatype* data, int n);
//中序遍历
void inorder_travel(Node* nil, Node* root);
//key查找
Node* Search_key(rbtree* T, int target);
//删除节点操作
void Delete_node(rbtree* T, Node* target);
 
 
				//主函数
int main() {
	rbtree* T = Create_inittree();
	Datatype d[] = { "ABCDEFG" };
	int n = sizeof(d) / sizeof(Datatype) - 1;
	Create_wholetree(T, d, n);
 
	inorder_travel(T->nil, T->root);
 
	Node* p = Search_key(T, 2);
	printf("查找结果 %d:%c\n", p->key, p->data);
 
	Delete_node(T, p);
	printf("删除后遍历结果：\n");
	inorder_travel(T->nil, T->root);
}
 
//创建初始化红黑树
rbtree* Create_inittree() {
	rbtree* T = (rbtree*)malloc(sizeof(rbtree));
	assert(T);
	T->nil = (Node*)malloc(sizeof(Node));
	assert(T->nil);
	//T->nil是不储存数据的节点，作为空节点代替NULL，也就是哨兵节点（表示空）
	T->nil->color = black;
	T->nil->par = NULL;
	T->nil->left = T->nil->right = NULL;
	T->root = T->nil;
	return T;
}
 
//创建一个节点
Node* Create_node(rbtree*T ,Datatype data, int key) {
	Node* new_node = (Node*)malloc(sizeof(Node));
	assert(new_node);
	new_node->data = data;
	new_node->color = red;//初始化颜色红色
	//左右父节点为nil哨兵节点
	new_node->left=new_node->right = T->nil;
	new_node->par = T->nil;
	new_node->key = key;
	return new_node;
}
 
//左旋（以x为旋转点，向左旋转）
void left_rotate(rbtree* T, Node* x) {
	Node* y = x->right;//标记到右子节点
	x->right = y->left;//y的左子节点代替x的右子节点
	if (x->right != T->nil)
		x->right->par = x;//如果不为空（nil）其父节点指向x
	y->par = x->par;//把y的父节点指向x的父节点，此时x与y没有直接联系了
	if (x->par == T->nil) {//判断x的父节点是否为根结点
		T->root = y;//如果是的话，y就变为根结点
	}
	else {
		//y顶替x的位置
		if (x == x->par->left)
			x->par->left = y;//如果x是父节点的左边，那y就代替x成为左子节点
		else
			x->par->right = y;//如果x是父节点的右边，那y就代替x成为右子节点
	}
	//y的左子节点指向x，x的父节点指向y
	y->left = x;
	x->par = y;
}
//右旋（以x为旋转点，向右旋转）
void right_rotate(rbtree* T, Node* x) {
	Node* y = x->left;//标记到左子节点y
	x->left = y->right;//y的右子节点代替x的左子节点
	if (x->left != T->nil)
		x->left->par = x;
	y->par = x->par;//y的父节点指向x的父节点
	if (x->par == T->nil)
		T->root = y;//如果x是根结点的话，那么y代替x成为根结点
	else {
		if (x == x->par->left)
			x->par->left = y;
		else
			x->par->right = y;
	}
	//y的右子节点指向x，x的父节点为y
	y->right = x;
	x->par = y;
}
 
//插入后平衡调整
void Insert_adjust(rbtree* T, Node* t) {
	//如果父节点的颜色是红色那就进行调整操作了
	if (t->par->color == red) {
		Node* p = t->par;
		Node* pp = p->par;
		//01 p节点是pp左子节点
		if (p == pp->left) {
			Node* uncle = pp->right;
			//01-1 叔叔节点颜色是红色
			if (uncle->color == red) {
				p->color = black;
				uncle->color = black;
				pp->color = red;
				t = pp;
			}
			//01-2 叔叔节点颜色是黑色
			else {
				//01-2-1 插入节点t是p的左子节点
				if (t == p->left) {
					p->color = black;
					pp->color = red;
					right_rotate(T, pp);
					t = p;
				}
				//01-2-2 插入节点t是p的右子节点
				else if(t==p->right){
					left_rotate(T, p);
					t->color = black;
					pp->color = red;
					right_rotate(T, pp);
				}
			}
		}
		//02 p节点是pp的右子节点
		else {		
			Node* uncle = pp->left;
			//02-1 叔叔节点颜色是红色
			if (uncle->color == red) {
				pp->color = red;
				p->color = black;
				uncle->color = black;
				t = pp;
			}
			//02-2 叔叔节点颜色是黑色
			else {
				//02-2-1 插入节点t是p的右子节点
				if (t == p->right) {
					p->color = black;
					pp->color = red;
					left_rotate(T,pp);
					t = p;
				}
				//02-2-2 插入节点t是p的左子节点
				else {
					right_rotate(T, p);
					t->color = black;
					pp->color = red;
					left_rotate(T, pp);
				}
			}
		}
	}
	//根节点标记黑色
	T->root->color = black;
}
 
//插入节点
void Insert_node(rbtree* T, Datatype data,int key) {
	assert(T);
	Node* t = Create_node(T ,data, key);
	Node* root = T->root;//快指针
	Node* cur=T->nil;//慢指针
	//1.如果根节点为空
	if (T->root==T->nil) {
		T->root = t;//根结点指向新创建的节点
	}
	else {
		while (root != T->nil) {
			cur = root;//cur标记为root的上一个节点（父节点）
			if (t->key > root->key)
				root = root->right;
			else if (t->key < root->key)
				root = root->left;
			//如果出现插入重复的key值，就退出，不进行插入操作
			else {
				printf("Don't insert the same key!\n");
				free(t);
				t = NULL;
				return;
			}
		}
	}
	//判断插入的位置
	if (key < cur->key)
		cur->left = t;//小的话就插入左边
	else
		cur->right = t;//大的话就插入右边
	t->par = cur;//新插入的父节点指针指向cur
	Insert_adjust(T, t);//平衡调整
}
 
//已有数据，自增加key创建红黑树
void Create_wholetree(rbtree* T, Datatype* data, int n) {
	for (int i = 0; i < n; i++) {
		Insert_node(T, data[i], i+1);
	}
}
 
//中序遍历
void inorder_travel(Node* nil,Node* root) {
	if (root == nil)
		return;
	inorder_travel(nil, root->left);
	printf("%d: %c\n", root->key, root->data);
	inorder_travel(nil, root->right);
}
 
//根据key查找
Node* Search_key(rbtree* T, int target) {
	assert(T);
	assert(T->root);
	Node* cur = T->root;
	while (cur) {
		if (cur->key == target)
			return cur;//找到就返回
		else if (cur->key > target)
			cur = cur->left;
		else
			cur = cur->right;
	}
	printf("The target is not exist\n");
	return NULL;
}
 
//删除黑色叶子节点调整
void Del_b_adjust(rbtree* T, Node* x) {
	//被删除节点x父节点的左边
	if (x == x->par->left) {
		Node* p = x->par;//父节点
		Node* b = p->right;//兄弟节点
		p->left = T->nil;
		//删除节点x
		free(x);
		x = NULL;
		//1.兄弟节点为黑色
		if (b->color == black) {
			//1-1没有侄子节点
			if (b->left == T->nil && b->right == T->nil) {
				p->color = black;
				b->color = red;
			}
			//1-2左侄节点红色
			else if (b->left->color == red && b->right == T->nil) {
				right_rotate(T, b);
				b->par->color = p->color;
				p->color = black;
				left_rotate(T, p);
			}
			//1-3右侄子节点红色
			else if (b->left == T->nil && b->right->color == red) {
				b->color = p->color;
				p->color = black;
				left_rotate(T, p);
			}
			//1-4 两个侄子节都是红色
			else {
				left_rotate(T, p);
				b->color = p->color;
				b->right->color = black;
				p->color = black;
			}
		}
		//2.兄弟节点为红色
		else {
			left_rotate(T, p);
			b->color = black;
			p->right->color = red;
		}
	}
 
	//被删除节点在父节点的右边
	else {
		Node* p = x->par;
		Node* b = p->left;
		p->right = T->nil;
		free(x);
		x = NULL;
		//1.兄弟节点黑色
		if (b->color == black) {
			//1-1没有侄子节点
			if (b->left == T->nil && b->right == T->nil) {
				p->color = black;
				b->color = red;
			}
			//1-2兄弟有右子节点
			else if (b->right->color == red && b->left == T->nil) {
				left_rotate(T, b);
				b->par->color = p->color;
				p->color = black;
				right_rotate(T, p);
			}
			//1-3 兄弟有左子节点
			else if (b->left->color == red && b->right == T->nil) {
				b->color = p->color;
				p->color = black;
				b->left->color = black;
				right_rotate(T, p);
			}
			//1-4 兄弟有左右子节点
			else {
				right_rotate(T, p);
				b->color = p->color;
				p->color = black;
				b->left->color = black;
			}
		}
		//2.兄弟节点为红色
		else {
			right_rotate(T, p);
			b->color = black;
			p->left->color = red;
		}
	}
}
//查找删除替身节点（找后驱）
Node* node_successor(rbtree* T, Node* root) {
	while (root->left != T->nil)
		root = root->left;
	return root;
}
//删除节点操作
void Delete_node(rbtree* T, Node* target) {
	//1.删除的节点是叶子节点
	if (target->left == T->nil && target->right == T->nil) {
		//1-01如果这个节点是红色节点
		if (target->color == red) {
			if (target == target->par->left)
				target->par->left = T->nil;
			else
				target->par->right = T->nil;
			free(target);
			target = NULL;
		}
		//1-02 如果是黑色叶子节点进入到调整
		else
			Del_b_adjust(T, target);
	}
	//2.删除的只有一个左孩子的节点
	else if (target->left != T->nil && target->right == T->nil) {
		Node* lc = target->left;
		target->data = lc->data;
		target->key = lc->key;
		target->left = T->nil;
		free(lc);
		lc = NULL;
	}
	//3.删除的只有一个右孩子的节点
	else if (target->left == T->nil && target->right != T->nil) {
		Node* rc = target->right;
		target->data = rc->data;
		target->key = rc->key;
		target->right = T->nil;
		free(rc);
		rc = NULL;
	}
	//4.删除的节点有左右孩子
	else {
		Node* sub = node_successor(T, target->right);//找到替代者
		target->data = sub->data;
		target->key = sub->key;
		Delete_node(T, sub);//递归进入到前三种删除方式
	}
 
	T->root->color = black;//根结点为黑色
}