redblack.h

基于vc++6.0的一个关于红黑树的插入和删除程序,并计算了它的时间复杂度.经典啊

//RedBlack.h
#ifndef REDBLACK_INCLUDE
#define REDBLACK_INCLUDE

template<typename T>
class RedBlackTree
{
	struct Node
	{
		T key;         //结点值
		bool color;        //颜色: 0为Black,1为Red
		Node* parent;     //双亲
		Node* left;      //左孩子
		Node* right;    //右孩子
		//构造函数
		Node(T data_, bool color_, Node* p, Node* l, Node* r)
			:key(data_),color(color_),parent(p),left(l),right(r){}
	}; 
	Node* NIL;  //NIL指针
	Node* root;   //根结点指针
	bool RED ;    //红
	bool BLACK ;    //黑
 
	public:
         
		 //构造函数
		RedBlackTree(T data=0, bool str=false, Node* p=NULL, Node* q=NULL, Node* e=NULL):RED(true),BLACK(false)
		{ 
			NIL = new Node(0, BLACK, NIL, NIL, NIL);//哨兵结点
			root = NIL;
		}

		~RedBlackTree()   //析构函数
		{

			DeleteTree(root);
			delete NIL;
		}

		void LeftRotate(Node* x);     //左旋
		void RightRotate(Node* y);     //右旋
        void RBInsert(T data);         //插入结点
		void RBInsertFixup(Node* z);   //插入后调整红黑树各结点颜色
		void RBDelete(T data);         //删除结点
		void RBDeleteFixUp(Node* x);   //删除后调整红黑树各结点颜色
		Node* TreeSearchNumber(Node* x, T k);
		Node* TreeSuccessor(Node* x);
		void DeleteTree(Node* x);     //删除整棵红黑树
		void PrintTree(Node* x);       //输出红黑树各结点
		Node* GetNode(void);           
		Node* TreeMinIMUM(Node* x );   //值最小的结点
};

#endif