rbtree.cpp

数据结构的红黑树算法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum boolean{RED, BLACK};
typedef enum boolean boolean;
typedef char keytype;

struct TreeNode{
	keytype key;
	boolean color;
	TreeNode* lchild;
	TreeNode* rchild;
	TreeNode* parent;
};

typedef struct TreeNode* pTREE;
typedef struct TreeNode* pNODE;

void LeftRotate(pTREE &RBTree, pNODE x);             //左旋转
void RightRotate(pTREE &RBTree, pNODE x);            //右旋转
pTREE RBInsert(pTREE RBTree, keytype k);             //插入操作
pTREE RBInsertFixup(pTREE RBTree, pNODE z);          //插入操作的辅助函数
pTREE RBDelete(pTREE RBTree, keytype k);            //删除操作
pTREE RBDeleteFixup(pTREE RBTree, pNODE x);          //删除操作的辅助函数
pNODE Search(pTREE RBTree, keytype k);              //查找数值k对应的结点，返回指向该结点的指针
void PrintNode(pTREE RBTree);
void MidVisit(pTREE RBTee);                         //中序遍历

 
int main(void)
{
	int i;
	pTREE RBTREE = NULL;           //RBTREE指向红黑树的根结点
	char str[] = "ALGORITHM";
	int count = (int)strlen(str);

	for (i = 0; i < count; i++){            
		RBTREE = RBInsert(RBTREE, str[i]);
		printf("插入 %c 之后:\n", str[i]);
		MidVisit(RBTREE);
		putchar('\n');
	}

	
	for (i = 0; i < count; i++){
		if (i == (count - 1)){
			printf("删除 %c 之后：\n结点已完全删除，结束！\n", str[count-1]);
			exit(0);
		}
		RBDelete(RBTREE, str[i]);		
		printf("删除 %c 之后:\n", str[i]);
		MidVisit(RBTREE);
		putchar('\n');
	}

	system("pause");
	return 0;
}

//对结点x实施左旋
void LeftRotate(pTREE &RBTree, pNODE x)
{
	pNODE y = x->rchild;

	if (y == NULL)		
		return;
	
	x->rchild = y->lchild;          //把y的左子树变为x的右子树
	if (y->lchild != NULL)
		y->lchild->parent = x;
	y->parent = x->parent;          //x的父结点变为y的父结点

	if (x == RBTree)
		RBTree = y;
	else if (x == x->parent->lchild)
		x->parent->lchild = y;
	else
		x->parent->rchild = y;

	y->lchild = x;
	x->parent = y;
}

//对结点x实施右旋
void RightRotate(pTREE &RBTree, pNODE x)
{
	pNODE y = x->lchild;

	if (y == NULL)
		return;

	x->lchild = y->rchild;
	if (y->rchild != NULL)
		y->rchild->parent = x;
	y->parent = x->parent;

	if (x == RBTree)         //x是根结点
		RBTree = y;
	else if (x == x->parent->lchild)               //x是左儿子
		x->parent->lchild = y;
	else                                           //x是右儿子 
		x->parent->rchild = y;
	y->rchild = x;
	x->parent = y;
}

//像原来树中插入一个结点z，z的数据域为k，RBTree指向树的根结点
pTREE RBInsert(pTREE RBTree, keytype k)
{
	pNODE x = RBTree;
	pNODE y = NULL;
	pNODE z = (pNODE)malloc(sizeof(struct TreeNode));    //要插入的新结点
	z->key = k;

	while (x != NULL){             
		y = x;
		if (z->key < x->key){               //按查找树的规则进行插入
			if (x->lchild != NULL)
				x = x->lchild;
			else
				break;
		}
		else{
			if (x->rchild != NULL)
				x = x->rchild;
			else
				break;
		}
	}

	z->parent = y;
	if (y == NULL)
		RBTree = z;
	else{
		if (z->key < y->key)           //安排z是y的左儿子还是右儿子
			y->lchild = z;
		else
			y->rchild = z;
	}

	z->lchild = NULL;
	z->rchild = NULL;
	z->color = RED;
	return RBInsertFixup(RBTree, z);
}

//插入红色结点后可能违背红黑树的定义，下面函数对插入的结点z进行修正
pTREE RBInsertFixup(pTREE RBTree, pNODE z)
{
	pNODE zUncle;                 //z的伯父结点

 	while ((RBTree != z) && (z->parent->color == RED)){
		if (z->parent == z->parent->parent->lchild){ //如果z的父结点是z的祖父结点的左儿子
			zUncle = z->parent->parent->rchild;
			if ((zUncle != NULL) && (zUncle->color == RED)){              //伯父结点的颜色同样为RED
				z->parent->color = BLACK;               
				zUncle->color = BLACK;
				z->parent->parent->color = RED;
				z = z->parent->parent;               //进行循环
			}
			else{
				if (z == z->parent->rchild){            
					z = z->parent;
					LeftRotate(RBTree, z);
				}
				z->parent->color = BLACK;               
				z->parent->parent->color = RED;
				RightRotate(RBTree, z->parent->parent);
			}
		}

		else{
			zUncle = z->parent->parent->lchild;
			if ((zUncle != NULL) && (zUncle->color == RED)){
				z->parent->color = BLACK;
				zUncle->color = BLACK;
				z->parent->parent->color = RED;
				z = z->parent->parent;               //进行循环
			}
			else{
				if (z == z->parent->lchild){
					z = z->parent;
					RightRotate(RBTree, z);
				}
				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				LeftRotate(RBTree, z->parent->parent);
			}
		}
	}
	RBTree->color = BLACK;
	return RBTree;
}

//在红黑树中删除数据域为k的结点
pTREE RBDelete(pTREE RBTree, keytype k)
{
	pNODE x, y;	
	pNODE z = Search(RBTree, k);

	if (z == NULL)
		return RBTree;
	if ((z->lchild == NULL) || (z->rchild == NULL))
		y = z;
	else{
		y = z->rchild;
		while (y->lchild != NULL)
			y = y->lchild;
	}		
	if (y->lchild != NULL)      //如果被删除的结点左儿子非空，则使用x记录
		x = y->lchild;
	else
		x = y->rchild;
	if (x != NULL)
		x->parent = y->parent;
	if (y->parent == NULL)
		RBTree = x;
	else if (y == y->parent->lchild)
		y->parent->lchild = x;
	else
		y->parent->rchild = x;

	if (y != z)         //key有两个孩子时，实际删除的是z的直接后继y结点，所以要将后继结点的信息复制到key结点中
		z->key = y->key;
	if ((y->color == BLACK) && (x != NULL))
		RBDeleteFixup(RBTree, x);
	free(y);
	return RBTree;
}


pTREE RBDeleteFixup(pTREE RBTree, pNODE x)    //RBTree point to root
{
	pNODE xBrother;

	while ((x != RBTree) && (x->color == BLACK)){//如果color(x)为red，只需要讲color(x)=black就行了
		if (x == x->parent->lchild){
			xBrother = x->parent->rchild;
			if (xBrother == NULL)
				continue;
			if (xBrother->color == RED){
				xBrother->color = BLACK;
				x->parent->color = RED;
				LeftRotate(RBTree, x->parent);//修改了树结构,这一步后xBrother为x的祖父节点并且xBrother右孩子的black nodes不变
				xBrother = x->parent->rchild;//修正x得兄弟结点，现在color(father)=black right(father)=black,并且father->left得
			}
			if ((xBrother->lchild != NULL) && (xBrother->lchild->color == BLACK) && (xBrother->rchild != NULL) && (xBrother->rchild->color == BLACK)){
				xBrother->color = RED;
				x = x->parent;
			}
			else{
				if ((xBrother != NULL) && (xBrother->rchild->color == BLACK)){
					xBrother->lchild->color = BLACK;
					xBrother->color = RED;
					RightRotate(RBTree, xBrother);
					xBrother = x->parent->rchild;
				}
				xBrother->color = x->parent->color;
				x->parent->color = BLACK;
				xBrother->rchild->color = BLACK;
				LeftRotate(RBTree, x->parent);
				x = RBTree;
			}
		}
		else{
			xBrother = x->parent->lchild;
			if (xBrother == NULL)
				continue;
			if (xBrother->color == RED){
				xBrother->color = BLACK;
				x->parent->color = RED;
				LeftRotate(RBTree, x->parent);//修改了树结构,这一步后xBrother为x的祖父节点并且xBrother右孩子的black nodes不变
				xBrother = x->parent->lchild;//修正x得兄弟结点，现在color(father)=black right(father)=black,并且father->left得
			}
			if ((xBrother->rchild != NULL) && (xBrother->rchild->color == BLACK) && (xBrother->lchild != NULL) && (xBrother->lchild->color == BLACK)){
				xBrother->color = RED;
				x = x->parent;
			}
			else{
				if ((xBrother->lchild != NULL) && (xBrother->lchild->color == BLACK)){
					xBrother->rchild->color = BLACK;
					xBrother->color = RED;
					LeftRotate(RBTree, xBrother);
					xBrother = x->parent->lchild;
				}
				xBrother->color = x->parent->color;
				x->parent->color = BLACK;
				xBrother->lchild->color = BLACK;
				RightRotate(RBTree, x->parent);
				x = RBTree;
			}
		}
	}
	x->color = BLACK;
	return RBTree;
}

//寻找值k对应的结点
pNODE Search(pTREE RBTree, keytype k)
{
	pNODE x = RBTree;

	do{
		if (k == x->key)
			break;
		if (k < x->key){
			if (x->lchild != NULL)
				x = x->lchild;
			else
				break;
		}
		else{
			if (x->rchild != NULL)
				x = x->rchild;
			else
				break;
		}
	} while (NULL != x);	

	return x;
}

void PrintNode(pNODE node)
{
	char* color[] = {"RED", "BLACK"};

	printf("Key = %c,\tcolor = %s", node->key, color[node->color]);
	if (node->parent != NULL)
		printf(",\tparent = %c", node->parent->key);
	if (node->lchild != NULL)
		printf(",\tleft = %c", node->lchild->key);
	if (node->rchild != NULL)
		printf(",\tright = %c", node->rchild->key);
	printf("\n");
}


void MidVisit(pTREE RBTree)
{
	if (RBTree != NULL){
		if (RBTree->lchild != NULL)
			MidVisit(RBTree->lchild);
		PrintNode(RBTree);
		if (RBTree->rchild != NULL)
			MidVisit(RBTree->rchild);
	}
}