redblacktree.cpp

Soul的源代码,类似于劲舞团之类的游戏

// RedBlackTree.cpp: implementation of the RedBlackTree class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "RB_Tree.h"
#include "RedBlackTree.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

RedBlackTreeNode::RedBlackTreeNode()
{
}

RedBlackTreeNode::RedBlackTreeNode(RedBlackEntry * newEntry)
  : key(newEntry->GetKey()) 
{
}

RedBlackTreeNode::~RedBlackTreeNode()
{
}

RedBlackTreeNode* RedBlackTreeNode::GetLeftChild()
{
	return left;
}
RedBlackTreeNode* RedBlackTreeNode::GetRightChild()
{
	return right;
}

int RedBlackTreeNode::SetKey(char *ckey)
{
	key= storedEntry.SetKey(ckey);
	//strcpy(storedEntry.key,key);
	return 1;
}

char* RedBlackTreeNode::GetKey()
{
	return key;
}

int RedBlackTreeNode::GetColor()
{
	return red;
}

RedBlackEntry * RedBlackTreeNode::GetEntry()
{
	return &storedEntry;
}

RedBlackEntry::~RedBlackEntry()
{}
char* RedBlackEntry::SetKey(char *ckey)
{
	strcpy(key,ckey);
	return key;
}

RedBlackTree::RedBlackTree()
{
  nil = new RedBlackTreeNode;
  nil->left = nil->right = nil->parent = nil;
  nil->red = 0;
  nil->key = NULL;
//  nil->storedEntry = NULL;
  
  root = new RedBlackTreeNode;
  root->parent = root->left = root->right = nil;
  root->key = NULL;
  root->red=0;
//  root->storedEntry = NULL;  
}

RedBlackTree::~RedBlackTree()
{
	if(nil != NULL)
        delete nil;
	if(root != NULL)
		delete root;
}


//-------------------------------------------------------------------------------------------------------
//	Name		 :: LeftRotate(RedBlackTreeNode* x)
//	Create Date	 :: 2004/04/15
//	Description	 :: 飘府狼 闭屈阑 嘎冕促.
//	param		 ::	
//	Bug	Report	 ::
//-------------------------------------------------------------------------------------------------------
void RedBlackTree::LeftRotate(RedBlackTreeNode* x)
{
	RedBlackTreeNode* y;

	y=x->right;
	x->right=y->left;

	if (y->left != nil)
		y->left->parent=x; /* used to use sentinel here */
  
	y->parent=x->parent;   

	if( x == x->parent->left)
		x->parent->left=y;
	else
	    x->parent->right=y;
  
	y->left=x;
	x->parent=y;
}


//-------------------------------------------------------------------------------------------------------
//	Name		 :: RightRotate(RedBlackTreeNode* y)
//	Create Date	 :: 2004/04/15
//	Description	 :: 飘府狼 闭屈阑 嘎冕促.
//	param		 ::	
//	Bug	Report	 ::
//-------------------------------------------------------------------------------------------------------
void RedBlackTree::RightRotate(RedBlackTreeNode* y)
{
	RedBlackTreeNode* x;

	x=y->left;
	y->left=x->right;

	if (nil != x->right)
		x->right->parent=y; 

	x->parent=y->parent;
	if( y == y->parent->left)
	    y->parent->left=x;
	else
		y->parent->right=x;
	
	x->right=y;
	y->parent=x;
}


//-------------------------------------------------------------------------------------------------------
//	Name		 :: TreeInsertHelp(RedBlackTreeNode* z)
//	Create Date	 :: 2004/04/15
//	Description	 :: 飘府俊 z畴靛甫 牢辑飘 秦林绰何盒.
//	param		 ::	insert且 畴靛甫 罐绰促.
//	Bug	Report	 ::
//-------------------------------------------------------------------------------------------------------
int RedBlackTree::TreeInsertHelp(RedBlackTreeNode* z)
{
	//  this funtion篮 坷肺瘤 RedBlackTree::Insert 俊辑父 静咯柳促.
	RedBlackTreeNode* x;
	RedBlackTreeNode* y;
    int compVal = 1;

	z->left=z->right=nil;
	y=root;
	x=root->left;

	while( x != nil)
	{
		y=x;
		compVal = Compare(x->key, z->key);
		if ( 1 == compVal /*x->key > z->key*/)
			x=x->left;
		else if(-1 == compVal)/* x->key <= z->key */
			x=x->right;
		else 
			return compVal;
	}

	z->parent=y;
	if ( (y == root) || (1 == compVal)/*(y->key > z->key)*/ )
		y->left=z;
	else
		y->right=z;

	return compVal;
}


//-------------------------------------------------------------------------------------------------------
//	Name		 :: Insert(RedBlackTreeNode* z)
//	Create Date	 :: 2004/04/15
//	Description	 :: 飘府俊 货肺款 畴靛甫 牢辑飘 秦林绊 闭屈阑 嘎眠绰 何盒.
//					insert窍扁傈俊 z 畴靛绰 捞固 技泼登绢 乐绢具 茄促.
//	param		 ::	insert且 畴靛甫 罐绰促.
//
//	Bug	Report	 ::
//-------------------------------------------------------------------------------------------------------
RedBlackTreeNode * RedBlackTree::Insert(RedBlackTreeNode * newNode)
{
	RedBlackTreeNode * y;
	RedBlackTreeNode * x;

	x = newNode;

	// 鞍篮蔼捞 乐栏搁 NULL蔼 府畔
	if(TreeInsertHelp(x) == 0)
		return NULL; /*鞍篮 畴靛啊 粮犁 茄促.*/
	
	x->red=1;
	// 闭屈飘府甫 父甸绢 林绰 何盒.
	while(x->parent->red)
	{ 
		if (x->parent == x->parent->parent->left)
		{
			y=x->parent->parent->right;
			if (y->red)
			{
				x->parent->red=0;
				y->red=0;
				x->parent->parent->red=1;
				x=x->parent->parent;
			}
			else
			{
				if (x == x->parent->right)
				{
					x=x->parent;
					LeftRotate(x);
				}
				x->parent->red=0;
				x->parent->parent->red=1;
				RightRotate(x->parent->parent);
			} 
		}
		else
		{ 
			y=x->parent->parent->left;
			if (y->red)
			{
				x->parent->red=0;
				y->red=0;
				x->parent->parent->red=1;
				x=x->parent->parent;
			}
			else
			{
				if (x == x->parent->left)
				{
				  x=x->parent;
				  RightRotate(x);
				}
				x->parent->red=0;
				x->parent->parent->red=1;
				LeftRotate(x->parent->parent);
			} 
		}
	}
	root->left->red=0;
	return(newNode);
}

/***********************************************************************/
/*  FUNCTION:  GetSuccessorOf  */
/**/
/*    INPUTS:  x is the node we want the succesor of */
/**/
/*    OUTPUT:  This function returns the successor of x or NULL if no */
/*             successor exists. */
/**/
/*    Modifies Input: none */
/**/
/*    Note:  uses the algorithm in _Introduction_To_Algorithms_ */
/***********************************************************************/
  
RedBlackTreeNode * RedBlackTree::GetSuccessorOf(RedBlackTreeNode * x) const
{ 
	RedBlackTreeNode* y;

	if (nil != (y = x->right))
	{ /* assignment to y is intentional */
		while(y->left != nil) /* returns the minium of the right subtree of x */
			y=y->left;
        return(y);
	}
	else
	{
		y=x->parent;
		while(x == y->right)
		{ /* sentinel used instead of checking for nil */
			x=y;
			y=y->parent;
		}
		if (y == root)
			return(nil);
		return(y);
	}
}

/***********************************************************************/
/*  FUNCTION:  DeleteFixUp */
/**/
/*    INPUTS:  x is the child of the spliced */
/*             out node in DeleteNode. */
/**/
/*    OUTPUT:  none */
/**/
/*    EFFECT:  Performs rotations and changes colors to restore red-black */
/*             properties after a node is deleted */
/**/
/*    Modifies Input: this, x */
/**/
/*    The algorithm from this function is from _Introduction_To_Algorithms_ */
/***********************************************************************/

void RedBlackTree::DeleteFixUp(RedBlackTreeNode* x)
{
	RedBlackTreeNode * w;
	RedBlackTreeNode * rootLeft = root->left;

	while( (!x->red) && (rootLeft != x))
	{
		if (x == x->parent->left)
		{
			w=x->parent->right;
			if (w->red)
			{
				w->red=0;
				x->parent->red=1;
				LeftRotate(x->parent);
				w=x->parent->right;
			}
			if ( (!w->right->red) && (!w->left->red) )
			{ 
				w->red=1;
				x=x->parent;
			}
			else
			{
				if (!w->right->red)
				{
					w->left->red=0;
					w->red=1;
					RightRotate(w);
					w=x->parent->right;
				}

				w->red=x->parent->red;
				x->parent->red=0;
				w->right->red=0;
				LeftRotate(x->parent);
				x=rootLeft; /* this is to exit while loop */
			}
		}
		else
		{ /* the code below is has left and right switched from above */
			w=x->parent->left;
			if (w->red)
			{
				w->red=0;
				x->parent->red=1;
				RightRotate(x->parent);
				w=x->parent->left;
			}
			if ( (!w->right->red) && (!w->left->red) )
			{ 
				w->red=1;
				x=x->parent;
		    }
			else
			{
				if (!w->left->red)
				{
					w->right->red=0;
					w->red=1;
					LeftRotate(w);
					w=x->parent->left;
				}
				w->red=x->parent->red;
				x->parent->red=0;
				w->left->red=0;
				RightRotate(x->parent);
				x=rootLeft; /* this is to exit while loop */
			}
		}
	}
	x->red=0;
}


//-------------------------------------------------------------------------------------------------------
//	Name		 :: RedBlackEntry * RedBlackTree::DeleteNode(RedBlackTreeNode * z)
//	Create Date	 :: 2004/04/15
//	Description	 :: 畴靛甫 昏力矫 龋免 茄促.. 昏力饶浚 罐靛矫 弊畴靛狼 皋葛府甫 馆吵窍磊..
//	param		 ::	
//	Bug	Report	 ::
//-------------------------------------------------------------------------------------------------------
RedBlackEntry * RedBlackTree::DeleteNode(RedBlackTreeNode * z)
{
	RedBlackTreeNode* y;
	RedBlackTreeNode* x;
	RedBlackEntry * returnValue = &z->storedEntry;

	y= ((z->left == nil) || (z->right == nil)) ? z : GetSuccessorOf(z);
	x= (y->left == nil) ? y->right : y->left;
	if (root == (x->parent = y->parent)) /* assignment of y->p to x->p is intentional */
		root->left=x;
	else
	{
		if (y == y->parent->left)
			y->parent->left=x;
		else
			y->parent->right=x;
    }
	if (y != z)
	{ /* y should not be nil in this case */

		/* y is the node to splice out and x is its child */
  
		y->left=z->left;
		y->right=z->right;
		y->parent=z->parent;
		z->left->parent=z->right->parent=y;
		if (z == z->parent->left)
			z->parent->left=y; 
		else
			z->parent->right=y;
		if (!(y->red))
		{
			y->red = z->red;
			DeleteFixUp(x);
	    }
		else
			y->red = z->red; 
//		delete z;

	}
	else
	{
		if (!(y->red))
			DeleteFixUp(x);
//		delete y;
	}
	return returnValue;
}


//int RedBlackTree::Compare(int a, int b)
//{
//	if( a > b )
//		return 1;
//	else if ( a < b )
//		return -1;
//	else
//		return 0;
//}
//-------------------------------------------------------------------------------------------------------
//	Name		 :: int RedBlackTree::Compare(char* a, char* b)
//	Create Date	 :: 2004/04/15
//	Description	 :: 滴巩磊凯狼 厚背窍绊 臭绊 撤澜阑 蝶柳促.
//					巩磊凯篮 措家巩磊甫 救啊赴促.
//	param		 ::	
//
//	Bug	Report	 ::
//-------------------------------------------------------------------------------------------------------
int RedBlackTree::Compare(char* a, char* b)
{
	int iCmp;
	iCmp = _stricmp(a,b);
	if( iCmp > 0 )
		return 1;
	else if ( iCmp < 0 )
		return -1;
	else
		return 0;
}


//-------------------------------------------------------------------------------------------------------
//	Name		 :: RedBlackTreeNode* RedBlackTree::Search(char* q)
//	Create Date	 :: 2004/04/15
//	Description	 :: 巩磊凯狼 器牢磐甫 罐酒辑 弊 巩磊凯阑 八祸窍绊 弊畴靛狼 器牢磐蔼阑 逞败霖促.. 
//					巩磊凯篮 措家巩磊甫 救啊赴促.
//	param		 ::	
//	Bug	Report	 ::
//-------------------------------------------------------------------------------------------------------
RedBlackTreeNode* RedBlackTree::Search(char* q)
{
	RedBlackTreeNode* x=root->left;
	RedBlackTreeNode* _nil=nil;
	int compVal;
	if (x == _nil) return(0);
	compVal=Compare(x->key, q);
	while(0 != compVal)
	{/*assignemnt*/
		if (1 == compVal) /* x->key > q */
			x=x->left;
		else
			x=x->right;
    
		if ( x == _nil) return(0);
		compVal=Compare(x->key, q);
	}
	return(x);
}

RedBlackTreeNode* RedBlackTree::GetRoot()
{
	return root;
}

RedBlackTreeNode* RedBlackTree::GetNil()
{
	return nil;
}