红黑树的创建、插入和删除等源代码 (一)

#ifndef RB_TREE_H
#define RB_TREE_H
#include 
#include 
#include 
using namespace std;

enum RB_COLOR { BLACK, RED };

// class RB_Tree;

// 树结点
class TreeNode
{
	friend class RB_Tree;
public:
	TreeNode() : color( BLACK ), key( 0 ), 
		parent( NULL ), lchild( NULL ), rchild( NULL )
	{
	}
	TreeNode( int k ) : color( BLACK ), key( k ), 
		parent( NULL ), lchild( NULL ), rchild( NULL )
	{
	}
	TreeNode( const TreeNode &rhs )
	{
		color = rhs.color;
		key = rhs.key;
		parent = rhs.parent;
		lchild = rhs.lchild;
		rchild = rhs.rchild;
	}
	~TreeNode()
	{
		parent = 0;
		lchild = 0;
		rchild = 0;
	}

	int key;
//	RB_COLOR color;
private:
	RB_COLOR color;
//	int key;
	TreeNode *parent;
	TreeNode *lchild;
	TreeNode *rchild;
};

// 红黑树
class RB_Tree
{
public:
	RB_Tree()
	{
		Nil = new TreeNode();
		Nil->parent = Nil;
		Nil->lchild = Nil;
		Nil->rchild = Nil;
		root = Nil;
	}
	~RB_Tree()
	{
		delete Nil;
		Nil = NULL;
		root = NULL;
	}
	// 左旋
	void LeftRotate( TreeNode *x );
	void RightRotate( TreeNode *x );
	void RB_InsertFixUp( TreeNode *z );
	void RB_Insert( TreeNode *z );
	void RB_Create( int a[], int length );

	TreeNode* TreeMinimun( TreeNode *x );
	TreeNode* TreeMaxmun( TreeNode *x );
	TreeNode* TreeSuccessor( TreeNode *x );
	TreeNode* TreePredecessor( TreeNode *x );
	TreeNode* TreeSearch( int k );

	void RB_DeleteFixUp( TreeNode *x );
	TreeNode* RB_Delete( TreeNode *z );

	void PrintElem( TreeNode *x );
	
	void LevelOrderTraverse();

	void PreOrderTraverse();
	void InOrderTraverse();
	void PostOrderTraverse();



private:
	TreeNode *root;
	TreeNode *Nil;
};




#endif

/**
 * @brief RED_BLACK_TREE 
 * @author An
 * @data  2013.7.18                                                                  
**/
#include "RB_Tree.h"


void RB_Tree::LeftRotate( TreeNode *x )
{
	TreeNode *y = x->rchild;
	x->rchild = y->lchild;
	if ( y->lchild != Nil )
	{
		y->lchild->parent = x;
	}
	y->parent = x->parent;

	// 设置指向y的指针
	if ( x->parent == Nil )
	{
		root = y;   // root.key = y.key   
	}
	else if ( x == x->parent->lchild )
	{
		x->parent->lchild = y;
	}
	else
	{
		x->parent->rchild = y;
	}

	x->parent = y;  // 测试这两条顺序
	y->lchild = x;
}

void RB_Tree::RightRotate( TreeNode *x )
{
	TreeNode *y = x->lchild;
	x->lchild = y->rchild;
	if ( y->rchild != Nil )
	{
		y->rchild->parent = x;
	}
	y->parent = x->parent;

	if ( x->parent == Nil )
	{
		root = y;
	}
	else if ( x == x->parent->lchild )
	{
		x->parent->lchild = y;
	}
	else
	{
		x->parent->rchild = y;
	}

	x->parent = y;   // 测试这两条顺序
	y->rchild = x;
}

void RB_Tree::RB_InsertFixUp( TreeNode *z )
{
	while ( z->parent->color == RED )
	{
		if ( z->parent == z->parent->parent->lchild )  // z->parent->parent 是否存在？？？
		{
			TreeNode *y = z->parent->parent->rchild;
			if ( y->color == RED ) // case 1
			{
				z->parent->color = BLACK;
				y->color = BLACK;
				z->parent->parent->color = RED;
				z = z->parent->parent;
			}
			else // case 2, 3
			{
				if ( z == z->parent->rchild ) //case 2
				{
					z = z->parent;
					LeftRotate( z );
				}
				z->parent->color = BLACK;    //case 3   检查流程是否正确？？？
				z->parent->parent->color = RED;
				RightRotate( z->parent->parent );	
			}

		}  //endif  left
		else
		{
			TreeNode *y = z->