rbtree.h

数据结构课作业

#ifndef RBTREE_H_
#define RBTREE_H_

template<class T> class RBTree;

template<class T> 
class RBTreeNode{
public:
	T key;
	int color;
	RBTreeNode *left, *right, *parent;
};

template<class T>
class RBTree{
public:
	RBTree();
	RBTreeNode<T>* successor(RBTreeNode<T>* x);
	RBTreeNode<T>* insert(T key);
	RBTreeNode<T>* remove(T key);
	RBTreeNode<T>* search(T key);
	RBTreeNode<T>* maxnum(RBTreeNode<T>* x);
	RBTreeNode<T>* minnum(RBTreeNode<T>* x);
//	RBTreeNode<T>* getRoot();
//	void inorder(RBTreeNode<T>* node);
	~RBTree();
private:
	enum{
		Red, Black
	} Color;
	T key;
	int color;
	RBTreeNode<T> *left, *right, *parent;
	RBTreeNode<T> *root;
	RBTreeNode<T> *NIL;

	void left_rotate(RBTreeNode<T>* x);
	void right_rotate(RBTreeNode<T>* x);
	void insert_fixup(RBTreeNode<T>* z);
	void remove_fixup(RBTreeNode<T>* x);
};

template<class T>
RBTree<T>::RBTree(){
	NIL = new RBTreeNode<T>;
	NIL->color = Black;
	NIL->key = 123456;
	NIL->left = 0;
	NIL->right = 0;
	NIL->parent = 0;
	root = NIL;
}

template<class T>
RBTree<T>::~RBTree(){
	delete NIL;
}

template<class T>
RBTreeNode<T>* RBTree<T>::minnum(RBTreeNode<T>* x){
	while (x->left!=NIL)x=x->left;
	return x;
}

template<class T>
RBTreeNode<T>* RBTree<T>::maxnum(RBTreeNode<T>* x){
	while (x->right!=NIL)x=x->right;
	return x;
}


template<class T>
RBTreeNode<T>* RBTree<T>::successor(RBTreeNode<T>* x){
	if (x->right!=NIL)
		return minnum(x->right);
	RBTreeNode<T>* y;
	y = x->parent;
	while ((y!=NIL)&&(x==y->right)){
		x=y;
		y=y->parent;
	}
	return y;
}

template<class T>
void RBTree<T>::left_rotate(RBTreeNode<T> *x){
	RBTreeNode<T> *y;
	y = x->right;
	x->right = y->left;
	if (y->left!=NIL)
		y->left->parent = x;
	y->parent = x->parent;
	if (x->parent==NIL)
		root = y;
	else{
		if (x==x->parent->left)
			x->parent->left = y;
		else
			x->parent->right = y;
	}
	y->left = x;
	x->parent = y;
}

template<class T>
void RBTree<T>::right_rotate(RBTreeNode<T> *x){
	RBTreeNode<T> *y;
	y = x->left;
	x->left = y->right;
	if (y->right!=NIL)
		y->right->parent = x;
	y->parent = x->parent;
	if (x->parent==NIL)
		root = y;
	else{
		if (x==x->parent->left)
			x->parent->left = y;
		else
			x->parent->right = y;
	}
	y->right = x;
	x->parent = y;
}

template<class T>
RBTreeNode<T>* RBTree<T>::insert(T key){
	RBTreeNode<T> *y=NIL;
	RBTreeNode<T> *x=root;
	while (x!=NIL){
		y = x;
		if (key < x->key)
			x = x->left;
		else
			x = x->right;
	}
	
	RBTreeNode<T> *z = new RBTreeNode<T>;
	z->parent = y;
	if (y==NIL)
		root = z;
	else{
		if (key < y->key)
			y->left = z;
		else
			y->right = z;
	}
	z->left = NIL;
	z->right = NIL;
	z->color = Red;
	insert_fixup(z);
	return z;
}

template<class T>
void RBTree<T>::insert_fixup(RBTreeNode<T> *z){
	while (z->parent->color==Red){
		if (z->parent = z->parent->parent->left){
			RBTreeNode<T>* y = z->parent->parent->right;
			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->right){
					z=z->parent;
					left_rotate(z);
				}
				z->parent->color = Black;
				z->parent->parent->color = Red;
				right_rotate(z);
			}
		}
		else{
			RBTreeNode<T>* y = z->parent->parent->left;
			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->left){
					z=z->parent;
					right_rotate(z);
				}
				z->parent->color = Black;
				z->parent->parent->color = Red;
				left_rotate(z);
			}
		}
	}
	root->color = Black;
}

template<class T>
RBTreeNode<T>* RBTree<T>::search(T key){
	RBTreeNode<T>* x=root;
	while (x!=NIL){
		if (key == x->key) return x;
		if (key < x->key)
			x = x->left;
		else
			x = x->right;
	}
	return NIL;
}

template<class T>
RBTreeNode<T>* RBTree<T>::remove(T key){
	RBTreeNode<T>* z = search(key);
	if (z==NIL) return z;
	RBTreeNode<T>* y;
	if ((z->left==NIL)||(z->right==NIL))
		y = z;
	else
		y = successor(z);
	RBTreeNode<T>* x;
	if (y->left!=NIL)
		x = y->left;
	else
		x = y->right;
	x->parent = y->parent;
	if (y->parent==NIL)
		root = x;
	else{
		if (y==y->parent->left)
			y->parent->left = x;
		else
			y->parent->right = x;
	}
	if (y!=z)
		z->key = y->key;
	if (y->color==Black)
		remove_fixup(y);
	return y;
}

template<class T>
void RBTree<T>::remove_fixup(RBTreeNode<T> *x){
	while ((x!=root)&&(x->color ==Black)){
		if (x==x->parent->left){
			RBTreeNode<T>* w = x->parent->right;
			if (w->color == Red){
				w->color = Black;
				x->parent->color = Red;
				left_rotate(x->parent);
				w = x->parent->right;
			}
			if ((w->left->color==Black)&&(w->right->color==Black)){
				w->color = Red;
				x = x->parent;
			}
			else{
				if (w->right->color == Black){
					w->left->color = Black;
					w->color = Red;
					right_rotate(w);
					w = x->parent->right;
				}
				w->color = x->parent->color;
				x->parent->color = Black;
				w->right->color = Black;
				left_rotate(x->parent);
				x=root;
			}
		}
		else{
			RBTreeNode<T>* w = x->parent->left;
			if (w->color == Red){
				w->color = Black;
				x->parent->color = Red;
				right_rotate(x->parent);
				w = x->parent->left;
			}
			if ((w->right->color==Black)&&(w->left->color==Black)){
				w->color = Red;
				x = x->parent;
			}
			else{
				if (w->left->color == Black){
					w->right->color = Black;
					w->color = Red;
					left_rotate(w);
					w = x->parent->left;
				}
				w->color = x->parent->color;
				x->parent->color = Black;
				w->left->color = Black;
				right_rotate(x->parent);
				x=root;
			}
		}
	}
	x->color = Black;
}


#endif