rbtreedefine.cpp

使用VS.NET开发的数据结构红黑树可视化图形界面演示。可以进行节点的添加及删除。

#include <MainFrm>
#include <cstdio>
#include <iostream>
#using namespace std;

RBTree::RBTree()
{
	Nil=new(RBTreeNode);
	Nil->color=BLACK;
	Nil->leftchild=NULL;
	Nil->rightchild=NULL;
	Nil->parent=NULL;
	Nil->size=0;
	Nil->value=0;
	Nil->level=-1;
	root=Nil;
	root->parent=Nil;
	root->leftchild=Nil;
	root->rightchild=Nil;
}

int RBTree::DeleteFixColor(RBTreeNode * x)
{
	RBTreeNode * w=Nil;
	while(x!=root && x->color==BLACK)
	{
		if(x==x->parent->leftchild)
		{
			w=x->parent->rightchild;
			if(w->color==RED)
			{
				w->color=BLACK;
				x->parent->color=RED;
				LeftRotate(x->parent);
				w=x->parent->rightchild;
			}//if

			if(w->leftchild->color==BLACK && w->rightchild->color==BLACK)
			{
				w->color=RED;
				x=x->parent;
			}//if
			else 
			{
				if(w->rightchild->color==BLACK)
				{
					w->leftchild->color=BLACK;
					w->color=RED;
					RightRotate(w);
					w=x->parent->rightchild;
				}//elseif

				w->color=x->parent->color;
				x->parent->color=BLACK;
				w->rightchild->color=BLACK;
				LeftRotate(x->parent);
				x=root;
			}
		}//if
		else
		{
			w=x->parent->leftchild;
			if(w->color==RED)
			{
				w->color=BLACK;
				x->parent->color=RED;
				RightRotate(x->parent);
				w=x->parent->leftchild;
			}//if

			if(w->rightchild->color==BLACK && w->leftchild->color==BLACK)
			{
				w->color=RED;
				x=x->parent;
			}//if
			else 
			{
				if(w->leftchild->color==BLACK)
				{
					w->rightchild->color=BLACK;
					w->color=RED;
					LeftRotate(w);
					w=x->parent->leftchild;
				}//elseif

				w->color=x->parent->color;
				x->parent->color=BLACK;
				w->leftchild->color=BLACK;
				RightRotate(x->parent);
				x=root;
			}
		}
	}//while
	
	x->color=BLACK;

	return 0;
}

int RBTree::DeleteNode(RBTreeNode * z)
{
	RBTreeNode * y = Nil;
	RBTreeNode * x = Nil;
	
	if(z->leftchild==Nil||z->rightchild==Nil)
		y=z;
	else y=Successor(z);
	
	if(y->leftchild!=Nil)
		x=y->leftchild;
	else
		x=y->rightchild;

	x->parent=y->parent;

	if(y->parent==Nil)
		root=x;
	else if(y==y->parent->leftchild)
			y->parent->leftchild=x;
	else y->parent->rightchild=x;

	if(y!=z)
		z->value=y->value;
	if(y->color==BLACK)
		DeleteFixColor(x);
	
	RBTreeNode * tem = y->parent;
	while(tem!=Nil)
	{
		tem->size=tem->size-1;
		tem=tem->parent;
	}
	delete y;

	return 0;
}

int RBTree::DeleteTree(RBTreeNode * z)
{
	if(z!=Nil)
	{
		DeleteTree(z->leftchild);
		DeleteTree(z->rightchild);
		delete z;
		return 0;
	}
	else return 0;
}

int RBTree::Fixlevel(RBTreeNode * z)
{
	if(z!=Nil)
	{
		z->leftchild->level=z->level+1;
		z->rightchild->level=z->level+1;
		Fixlevel(z->leftchild);
		Fixlevel(z->rightchild);
		return 0;
	}
	else return 0;
}

RBTreeNode * RBTree::Minimum(RBTreeNode * z)
{
	while(z->leftchild!=Nil)
		z=z->leftchild;
	return z;
}

RBTreeNode * RBTree::Maximum(RBTreeNode * z)
{
	while(z->rightchild!=Nil)
		z=z->rightchild;
	return z;
}

RBTreeNode * RBTree::Successor(RBTreeNode * x)
{
	if(x->rightchild!=Nil)
		return Minimum(x->rightchild);
	RBTreeNode * y = x->parent;
	while((y!=Nil) && (x==y->rightchild))
	{
		x=y;
		y=y->parent;
	}
	return y;
}

int RBTree::InsertFixColor(RBTreeNode * z)
{
	RBTreeNode * y=Nil;

	while(z->parent->color==RED)
	{
		if(z->parent==z->parent->parent->leftchild)
		{
			y=z->parent->parent->rightchild;
			
			if(y->color==RED)
			{
				z->parent->color=BLACK;
				y->color=BLACK;
				z->parent->parent->color=RED;
				z=z->parent->parent;
			}
			else
			{
				if(z==z->parent->rightchild)
				{
					z=z->parent;
					LeftRotate(z);
				}
				z->parent->color=BLACK;
				z->parent->parent->color=RED;
				RightRotate(z->parent->parent);
			}
		}//if
		else
		{
			y=z->parent->parent->leftchild;
			
			if(y->color==RED)
			{
				z->parent->color=BLACK;
				y->color=BLACK;
				z->parent->parent->color=RED;
				z=z->parent->parent;
			}
			else
			{
				if(z==z->parent->leftchild)
				{
					z=z->parent;
					RightRotate(z);
				}
				z->parent->color=BLACK;
				z->parent->parent->color=RED;
				LeftRotate(z->parent->parent);
			}
		}
	}//while
	
	root->color=BLACK;
	
	return 0;
}

int RBTree::InsertNode(RBTreeNode * z)
{
	RBTreeNode * y = Nil;
	RBTreeNode * x = root;
	while(x!=Nil)
	{
		y=x;
		if(z->value<x->value)
			x=x->leftchild;
		else x=x->rightchild;
	}//while
	
	z->parent=y;
	
	if(y==Nil)
		root=z;
	else
	{
		if(z->value<y->value)
			y->leftchild=z;
		else y->rightchild=z;
	}//else
	
	z->leftchild=Nil;
	z->rightchild=Nil;
	z->color=RED;
	
	RBTreeNode * tmp = z->parent;
	while(tmp!=Nil)
	{
		tmp->size=tmp->size+1;
		tmp=tmp->parent;
	}
	
	InsertFixColor(z);
	return 0;
}

int RBTree::LeftRotate(RBTreeNode * x)
{
	RBTreeNode * y=Nil;
	y=x->rightchild;
	x->rightchild=y->leftchild;
	y->leftchild->parent=x;
	y->parent=x->parent;
	
	if(x->parent==Nil)
	{
		root=y;
	}//if
	else 
	{
		if(x==x->parent->leftchild)
			x->parent->leftchild=y;
		else
			x->parent->rightchild=y;
	}
	y->leftchild=x;
	x->parent=y;

	x->size=x->leftchild->size+x->rightchild->size+1;
	y->size=y->leftchild->size+y->rightchild->size+1;

	return 0;
}

int RBTree::RightRotate(RBTreeNode * x)
{
	RBTreeNode * y=Nil;
	y=x->leftchild;
	x->leftchild=y->rightchild;
	y->rightchild->parent=x;
	y->parent=x->parent;
	
	if(x->parent==Nil)
	{
		root=y;
	}//if
	else 
	{
		if(x==x->parent->rightchild)
			x->parent->rightchild=y;
		else
			x->parent->leftchild=y;
	}
	y->rightchild=x;
	x->parent=y;

	x->size=x->leftchild->size+x->rightchild->size+1;
	y->size=y->leftchild->size+y->rightchild->size+1;

	return 0;
}

int RBTree::BuildTree()
{
	long num;
	cout<<"Please input the number of treenodes:"<<endl;
	cin>>num;
	for (int i=1;i<=num;i++)
	{
		long key;
		cout<<"Please input the "<<i<<"th node's value"<<endl;
		cin>>key;
		RBTreeNode * tmp = new(RBTreeNode);
		tmp->value=key;
		tmp->leftchild=Nil;
		tmp->rightchild=Nil;
		tmp->parent=Nil;
		InsertNode(tmp);
	}
	Fixlevel();
	return 0;

}

int RBTree::PrintTree(RBTreeNode * x)
{
	if(x!=Nil)
	{
		for(int i=0;i<(x->level-1)*4;i++)
		{
			cout<<" ";
		}
		cout<<"└─";
		cout<<"color:"<<x->color<<" value"<<x->value<<" level"<<x->level<<" size"<<x->size<<endl;

		
	
		PrintTree(x->leftchild);
		PrintTree(x->rightchild);
		return 0;
		
	}
	else return 0;
}

int RBTree::PrintTree()
{
	PrintTree(root);
	return 0;
}

RBTreeNode * RBTree::FindNode(long key)
{
	RBTreeNode * tmp=root;
	if(root!=Nil)
	{
		while(tmp!=Nil && tmp->value!=key)
		{
			if(tmp->value<key)
				tmp=tmp->rightchild;
			if(tmp->value>key)
				tmp=tmp->leftchild;
		}
		return tmp;
	}
	else return Nil;
}

int RBTree::DeleteNode(long key)
{
	RBTreeNode * tmp = FindNode(key);
	if(tmp!=Nil)
	{	
		DeleteNode(tmp);
		return 0;
	}
	else return 0;
}

int RBTree::DeleteNode()
{
	cout<<"Please input the value to be deleted!"<<endl;
	long key;
	cin>>key;
	DeleteNode(key);
	Fixlevel();
	return 0;
}

RBTreeNode * RBTree::OS_Select(RBTreeNode * x,long i)
{
	long r=x->leftchild->size+1;
	if(i==r)
		return x;
	else
	{
		if (i<r)
			return OS_Select(x->leftchild,i);
		else
			return OS_Select(x->rightchild,i-r);
	}
}

long RBTree::OS_Rank(RBTreeNode * x)
{
	long r=x->leftchild->size+1;
	RBTreeNode * y=x;
	while(y!=root)
	{
		if(y==y->parent->rightchild)
			r=r+y->parent->leftchild->size+1;
		y=y->parent;
	}//while
	return r;
}