redblacktree.h

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

// RedBlackTree.h: interface for the RedBlackTree class.
//
//////////////////////////////////////////////////////////////////////
#ifndef  __RBTREE_MAP_H
#define  __RBTREE_MAP_H

#include "limits.h"

#define MAX_INT INT_MAX // some architechturs define INT_MAX not MAX_INT
const int MIN_INT=-MAX_INT;
//#if _MSC_VER > 1000
//#pragma once
//#endif // _MSC_VER > 1000

//class RedBlackEntry {
//	
//public:
//	RedBlackEntry() {}
//
//	RedBlackEntry(char* k) 
//	{
//		if(k != NULL)
//			strcpy(key,k);
//	}
//	~RedBlackEntry();
//	char* GetKey() 
//	{
//		return key;
//	}
//	char* SetKey(char *);
//protected:
//	char key[121];
//
//	char* pValue;
//};
class AccountEntry 
{
public:
	AccountEntry()  {}
	~AccountEntry() {}
	char* SetKey(char *ckey)
	{
		strcpy(key,ckey);
		return key;
	}
protected:
	char key[121];

	char* pValue;
};


class RedBlackTreeNode {
	//friend class RedBlackTree;
public:
	RedBlackTreeNode();
//	RedBlackTreeNode(RedBlackEntry *);
//	RedBlackEntry * GetEntry() ;
	~RedBlackTreeNode();
	RedBlackTreeNode * GetLeftChild();
	RedBlackTreeNode * GetRightChild();	 
	int SetKey(char* ckey);
	char* GetKey();
	int GetColor();
public:
	AccountEntry storedEntry;
	char *key;

	int red; /* if red=0 then the node is black */
	RedBlackTreeNode * left;
	RedBlackTreeNode * right;
	RedBlackTreeNode * parent;
};

template<class Type>
class RedBlackTree {
public:
  RedBlackTree();
  ~RedBlackTree();
  BOOL  DeleteNode(Type *);
  Type* Insert(Type *);
  Type* GetSuccessorOf(Type *) const;
  Type* Search(char* q);
  Type* GetRoot();
  Type* GetNil();

protected:
  /*  A sentinel is used for root and for nil.  These sentinels are */
  /*  created when RedBlackTreeCreate is caled.  root->left should always */
  /*  point to the node which is the root of the tree.  nil points to a */
  /*  node which should always be black but has aribtrary children and */
  /*  parent and no key or info.  The point of using these sentinels is so */
  /*  that the root and nil nodes do not require special cases in the code */
  Type * root;
  Type * nil;
  void LeftRotate(Type *);
  void RightRotate(Type *);
  int TreeInsertHelp(Type *);
  void DeleteFixUp(Type *);
  int Compare(char *a,char *b);
};

/*--------------------------------------------------------------------------------------------------------
// 备泅
--------------------------------------------------------------------------------------------------------*/

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

template<class Type>
RedBlackTree<Type>::~RedBlackTree()
{
	if(nil != NULL)
        delete nil;
	if(root != NULL)
		delete root;
}


//-------------------------------------------------------------------------------------------------------
//	Name		 :: LeftRotate(Type* x)
//	Create Date	 :: 2004/04/15
//	Description	 :: 飘府狼 闭屈阑 嘎冕促.
//	param		 ::	
//	Bug	Report	 ::
//-------------------------------------------------------------------------------------------------------
template<class Type>
void RedBlackTree<Type>::LeftRotate(Type* x)
{
	Type* 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(Type* y)
//	Create Date	 :: 2004/04/15
//	Description	 :: 飘府狼 闭屈阑 嘎冕促.
//	param		 ::	
//	Bug	Report	 ::
//-------------------------------------------------------------------------------------------------------
template<class Type>
void RedBlackTree<Type>::RightRotate(Type* y)
{
	Type* 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(Type* z)
//	Create Date	 :: 2004/04/15
//	Description	 :: 飘府俊 z畴靛甫 牢辑飘 秦林绰何盒.
//	param		 ::	insert且 畴靛甫 罐绰促.
//	Bug	Report	 ::
//-------------------------------------------------------------------------------------------------------
template<class Type>
int RedBlackTree<Type>::TreeInsertHelp(Type* z)
{
	//  this funtion篮 坷肺瘤 RedBlackTree::Insert 俊辑父 静咯柳促.
	Type* x;
	Type* 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(Type* z)
//	Create Date	 :: 2004/04/15
//	Description	 :: 飘府俊 货肺款 畴靛甫 牢辑飘 秦林绊 闭屈阑 嘎眠绰 何盒.
//					insert窍扁傈俊 z 畴靛绰 捞固 技泼登绢 乐绢具 茄促.
//	param		 ::	insert且 畴靛甫 罐绰促.
//
//	Bug	Report	 ::
//-------------------------------------------------------------------------------------------------------
template<class Type>
Type * RedBlackTree<Type>::Insert(Type * newNode)
{
	Type * y;
	Type * 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_ */
/***********************************************************************/
template<class Type>
Type * RedBlackTree<Type>::GetSuccessorOf(Type * x) const
{ 
	Type* 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_ */
/***********************************************************************/
template<class Type>
void RedBlackTree<Type>::DeleteFixUp(Type* x)
{
	Type * w;
	Type * 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(Type * z)
//	Create Date	 :: 2004/04/15
//	Description	 :: 畴靛甫 昏力矫 龋免 茄促.. 昏力饶浚 罐靛矫 弊畴靛狼 皋葛府甫 馆吵窍磊..
//	param		 ::	
//	Bug	Report	 ::
//-------------------------------------------------------------------------------------------------------
template<class Type>
BOOL RedBlackTree<Type>::DeleteNode(Type * z)
{
	Type* y;
	Type* 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 TRUE;
}


//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	 ::
//-------------------------------------------------------------------------------------------------------
template<class Type>
int RedBlackTree<Type>::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		 :: Type* RedBlackTree::Search(char* q)
//	Create Date	 :: 2004/04/15
//	Description	 :: 巩磊凯狼 器牢磐甫 罐酒辑 弊 巩磊凯阑 八祸窍绊 弊畴靛狼 器牢磐蔼阑 逞败霖促.. 
//					巩磊凯篮 措家巩磊甫 救啊赴促.
//	param		 ::	
//	Bug	Report	 ::
//-------------------------------------------------------------------------------------------------------
template<class Type>
Type* RedBlackTree<Type>::Search(char* q)
{
	Type* x=root->left;
	Type* _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);
}

template<class Type>
Type* RedBlackTree<Type>::GetRoot()
{
	return root;
}

template<class Type>
Type* RedBlackTree<Type>::GetNil()
{
	return nil;
}
#endif // !defined(AFX_REDBLACKTREE_H__CCCCF5E8_ED0F_474B_952F_BD43E3752D30__INCLUDED_)