redblacktree.h

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

// RedBlackTree.h: interface for the RedBlackTree class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_REDBLACKTREE_H__CCCCF5E8_ED0F_474B_952F_BD43E3752D30__INCLUDED_)
#define AFX_REDBLACKTREE_H__CCCCF5E8_ED0F_474B_952F_BD43E3752D30__INCLUDED_
#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 RedBlackTreeNode {
	friend class RedBlackTree;
public:
	RedBlackTreeNode();
	RedBlackTreeNode(RedBlackEntry *);
	RedBlackEntry * GetEntry() ;
	~RedBlackTreeNode();
	RedBlackTreeNode * GetLeftChild();
	RedBlackTreeNode * GetRightChild();	 
	int SetKey(char* );
	char* GetKey();
	int GetColor();
protected:
	RedBlackEntry storedEntry;
	char* key;
	int red; /* if red=0 then the node is black */
	RedBlackTreeNode * left;
	RedBlackTreeNode * right;
	RedBlackTreeNode * parent;
};

class RedBlackTree {
public:
  RedBlackTree();
  ~RedBlackTree();
  RedBlackEntry * DeleteNode(RedBlackTreeNode *);
  RedBlackTreeNode * Insert(RedBlackTreeNode *);
  RedBlackTreeNode * GetSuccessorOf(RedBlackTreeNode *) const;
  RedBlackTreeNode * Search(char* q);
  RedBlackTreeNode * GetRoot();
  RedBlackTreeNode * 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 */
  RedBlackTreeNode * root;
  RedBlackTreeNode * nil;
  void LeftRotate(RedBlackTreeNode *);
  void RightRotate(RedBlackTreeNode *);
  int TreeInsertHelp(RedBlackTreeNode *);
  void DeleteFixUp(RedBlackTreeNode *);
  int Compare(char *a,char *b);
};

#endif // !defined(AFX_REDBLACKTREE_H__CCCCF5E8_ED0F_474B_952F_BD43E3752D30__INCLUDED_)