紅黑樹的創建、插入和刪除等源代碼

#ifndef RB_TREE_H
#define RB_TREE_H
#include <iostream>
#include <queue>
#include <stack>
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->parent->parent->lchild;
			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->lchild )
				{
					z = z->parent;
					RightRotate( z );
				}
				z->parent->color = BLACK;
				z->parent->parent->color = RED;
				LeftRotate( z->parent->parent );
			}
		} //endif right
		//		root->color = BLACK;   // 位置是否正確？？？
	} // endwhile
	root->color = BLACK;
}

void RB_Tree::RB_Insert( TreeNode *z )
{
	TreeNode *y = Nil;
	TreeNode *x = root;
	while ( x != Nil )
	{
		y = x;
		if ( z->key < x->key )
		{
			x = x->lchild;
		}
		else
		{
			x = x->rchild;
		}
	}
	z->parent = y;
	if ( y == Nil )
	{
		root = z;  // root.key = z.key?
	}
	else if ( z->key < y->key )
	{
		y->lchild = z; //
	}
	else
	{
		y->rchild = z; //
	}
	z->lchild = Nil;
	z->rchild = Nil;
	z->color = RED;
	RB_InsertFixUp( z );
}

void RB_Tree::RB_Create( int a[], int length )
{
	for ( int i = 0; i != length; ++i )
	{
		TreeNode *p = new TreeNode( a[ i ] );
		RB_Insert( p );
	}
}

TreeNode* RB_Tree::TreeMinimun( TreeNode *x )  // 經過些函數x變了嗎。。。
{
	if ( x == Nil )
	{
		cout << "ERROR" << endl;
		return Nil;
	}
	while ( x->lchild != Nil )
	{
		x = x->lchild;
	}
	return x;
}

TreeNode* RB_Tree::TreeMaxmun( TreeNode *x )
{
	if ( x == Nil )
	{
		cout << "ERROR" << endl;
		return Nil;
	}
	while ( x->rchild != Nil )
	{
		x = x->rchild;
	}
	return x;
}

TreeNode* RB_Tree::TreeSuccessor( TreeNode *x )
{
	if ( x == Nil )
	{
		cout << "ERROR!" << endl;
		return Nil;
	}
	if ( x->rchild != Nil )
	{
		x = x->rchild;
		while ( x->lchild != Nil )
		{
			x = x->lchild;
		}
		return x;
	}
	while ( x == x->parent->rchild )
	{
		x = x->parent;
	}
	x = x->parent;
	return x;
}

TreeNode* RB_Tree::TreePredecessor( TreeNode *x )
{
	if ( x == Nil )
	{
		cout << "ERROR" << endl;
		return Nil;
	}
	if ( x->lchild != Nil )
	{
		x = x->lchild;
		while ( x->rchild != Nil )
		{
			x = x->rchild;
		}
		return x;
	}
	while ( x == x->parent->lchild )
	{
		x = x->parent;
	}
	x = x->parent;
	return x;
}

TreeNode* RB_Tree::TreeSearch( int k )
{
	TreeNode *p = root;
	while ( p != Nil && p->key != k )
	{
		if ( k < p->key )
		{
			p = p->lchild;
		}
		else
		{
			p = p->rchild;
		}
	}
	if ( p->key == k )
	{
		return p;
	}
	else
	{
		return Nil;
	}
}

void RB_Tree::RB_DeleteFixUp( TreeNode *x )
{
	while ( x != root && x->color == BLACK )
	{
		if ( x == x->parent->lchild )
		{
			TreeNode *w = x->parent->rchild;
			if ( w->color == RED )  // case 1
			{
				x->parent->color = RED;
				w->color = BLACK;
				LeftRotate( x->parent );
				w = x->parent->rchild;
			}
			// case 2, 3, 4
			if ( w->lchild->color == BLACK && w->rchild->color == BLACK ) // case 2
			{
				w->color = RED;
				x = x->parent;
			}
			else  // case 3, 4
			{
				if ( w->lchild->color == RED && w->rchild->color == BLACK ) // case 3
				{
					w->color = RED;
					w->lchild->color = BLACK;
					RightRotate( w );
					w = x->parent->rchild;
				}
				w->color = x->parent->color;
				x->parent->color = BLACK;
				w->rchild->color = BLACK;
				LeftRotate( x->parent );
				x = root;
			}
		}
		else
		{
			TreeNode *w = x->parent->lchild;
			if ( w->color == RED )  // case 1
			{
				w->color = BLACK;
				x->parent->color = RED;
				RightRotate( x->parent );
				w = x->parent->lchild;
			}
			//case 2, 3, 4
			if ( w->lchild->color == BLACK && w->rchild->color == BLACK ) // case 2
			{
				w->color = RED;
				x = x->parent;
			}
			else
			{
				if ( w->lchild->color == BLACK )
				{
					w->color = RED;
					w->rchild->color = BLACK;
					LeftRotate( w );
					w = x->parent->lchild;
				}
				w->color = x->parent->color;
				x->parent->color = BLACK;
				w->lchild->color = BLACK;
				RightRotate( x->parent );
				x = root;
			}
		} //end if
	} //end while
	x->color = BLACK;
}

TreeNode* RB_Tree::RB_Delete( TreeNode *z )
{
	TreeNode *y = Nil;
	TreeNode *x = Nil;
	if ( z->lchild == Nil || z->rchild == Nil )
	{
		y = z;
	}
	else
	{
		y = TreeSuccessor( z );
	}
	if ( y->lchild != Nil )
	{
		x = y->lchild;
	}
	else if ( y->rchild != Nil )
	{
		x = y->rchild;
	}
	x->parent = y->parent;
	if ( y->parent == Nil )
	{
		x = root;
	}
	else if ( y == y->parent->lchild )
	{
		y->parent->lchild = x;
	}
	else if ( y == y->parent->rchild )
	{
		y->parent->rchild = x;
	}
	if ( y != z )
	{
		z->key = y->key;
	}
	if ( y->color == BLACK )
	{
		RB_DeleteFixUp( x );
	}
	return y;
}

void RB_Tree::PrintElem( TreeNode *x )
{
	cout << x->key << "(" << x->color << ")" << " ";
}

void RB_Tree::LevelOrderTraverse()
{
	queue<TreeNode*> q;
	if ( root != Nil )
	{
		q.push( root );
	}
	while ( !q.empty() )
	{
		TreeNode *x = q.front();
		PrintElem( x );
		if ( x->lchild != Nil )
		{
			q.push( x->lchild );
		}
		if ( x->rchild != Nil )
		{
			q.push( x->rchild );
		}
		q.pop();
	}
}

void RB_Tree::PreOrderTraverse()
{
	stack<TreeNode*> stk;
	TreeNode *p = root;
	while ( p != Nil || !stk.empty() )
	{
		while ( p != Nil )
		{
			PrintElem( p );
			stk.push( p );
			p = p->lchild;
		}
		if ( !stk.empty() )
		{
			p = stk.top()->rchild;
			stk.pop();
		}
	}
}

void RB_Tree::InOrderTraverse()
{
	stack<TreeNode*> stk;
	TreeNode *p = root;
	while ( p != Nil || !stk.empty() )
	{
		while ( p != Nil )
		{
			stk.push( p );
			p = p->lchild;
		}
		if ( !stk.empty() )
		{
			PrintElem( stk.top() );
			p = stk.top()->rchild;
			stk.pop();
		}
	}
}

void RB_Tree::PostOrderTraverse()
{
	stack<TreeNode*> stk;
	TreeNode *pre = Nil;
	TreeNode *cur = Nil;
	stk.push( root );
	while ( !stk.empty() )
	{
		cur = stk.top();
		if ( ( cur->lchild == Nil && cur->rchild == Nil ) || 
			( pre != Nil && ( pre == cur->lchild || pre == cur->rchild ) ) )
		{
			PrintElem( cur );
			pre = cur;
			stk.pop();
		}
		else
		{
			if ( cur->rchild != Nil )
			{
				stk.push( cur->rchild );
			}
			if ( cur->lchild != Nil )
			{
				stk.push( cur->lchild );
			}
		}
	}
}