rbtree.cpp

红黑树是一种自平衡二叉查找树

template <typename Type>
struct TreeNode
{
	Type key;
	int color; 
	TreeNode *parent,*left,*right;
};

template <typename Type>
class RBTree
{
private:
	enum
	{
		RED,BLACK
	}Color;
	Type key;
	int color; 
	TreeNode<Type> *parent,*left,*right;
	TreeNode<Type> *NIL;
	TreeNode<Type> *ROOT;
	void left_rotate(TreeNode<Type> *&rotate);
	void right_rotate(TreeNode<Type> *&rotate);
	void RB_insert_fixup(TreeNode<Type>* &node);
	void RB_delete_fixup(TreeNode<Type>* &node);
public:
	//const static TreeNode<Type>* nil;
	RBTree();
	TreeNode<Type> *successor(const TreeNode<Type> *node);
	TreeNode<Type>* insert(Type key);
	TreeNode<Type>* search(Type key);
	TreeNode<Type>* remove(Type key);
	TreeNode<Type> *maxnum(TreeNode<Type>*node);
	TreeNode<Type>* minnum(TreeNode<Type>*node);
	TreeNode<Type>* getRoot();
	void inorder(TreeNode<Type>*node);
	void test()
	{
		this->insert(1);
		this->insert(2);
		left_rotate(ROOT);
	}
	~RBTree();
};
//template <typename Type>
//const  TreeNode<Type>* RBTree<Type>::nil=NIL;
template <typename Type>
RBTree<Type>::RBTree()
{
	NIL=new TreeNode<Type>;
	NIL->color=BLACK;
	NIL->key=123456;
	NIL->left=0;
	NIL->right=0;
	NIL->parent=0;
	ROOT=NIL;
}
template<typename Type>
RBTree<Type>::~RBTree()
{
	delete NIL;
}
template<typename Type>
TreeNode<Type>* RBTree<Type>::maxnum(TreeNode<Type>*node)
{
	//如果是空树
	if (node == NULL)
	{
		return NULL;
	}

	TreeNode<Type> *max=node;
	while(max->right!=NIL)
		max=max->right;
	return max;
}
template<typename Type>
TreeNode<Type>*  RBTree<Type>::minnum(TreeNode<Type>*node)
{
	//如果是空树
	if (node == NULL)
	{
		return NULL;
	}

	TreeNode<Type> *min=node;
	while(min->left!=NIL)
		min=min->left;
	return min;
}
template<typename Type>
TreeNode<Type>* RBTree<Type>::successor(const TreeNode<Type>* node)
{
	if(node->right!=NIL)
		return minnum(node->right);

	const TreeNode<Type>*s=node;
	const TreeNode<Type>*p=s->parent;
	while( p!=NIL && s==p->right )
	{
		s=p;p=s->parent;
	}
	return const_cast<TreeNode<Type>*>(p);
}
template<typename Type>
TreeNode<Type>* RBTree<Type>::getRoot()
{
	TreeNode<Type>*root=ROOT;
	return root;
}
template<typename Type>
void  RBTree<Type>::left_rotate(TreeNode<Type>*& _rotate)
{
	if(_rotate->right==NIL){cout<<"没有右孩子，不能左旋";return ;}//right child is nil, so can not left rotate
	TreeNode<Type>* r = _rotate->right;
	TreeNode<Type>*t,*rotate=_rotate;
	//deal with r->left
	rotate->right=r->left;
	r->left->parent=rotate;

	//deal with r
	// t=rotate->parent;
	// r->parent=t;//rotate 被修改成了NIL 为什么？
	// rotate=rotate->parent;
	if(rotate->parent==NIL)
	{
		ROOT=r;
		r->parent=NIL;
	}
	else if(rotate==rotate->parent->left)
		rotate->parent->left=r;
	else
		rotate->parent->right=r;
	r->parent=rotate->parent;
	//deal with rotate
	rotate->parent=r;
	r->left=rotate;
}
template<typename Type>
void  RBTree<Type>::right_rotate(TreeNode<Type>* &_rotate)
{
	TreeNode<Type>*rotate=_rotate;//不知道为什么，如果直接对_rotate操作，在过程中会改变_rotate得值
	if(rotate->left==NIL)
		return ;//left child is NIL, so can not right rotate
	TreeNode<Type>* l = rotate->left;
	//deal with l->right
	//cout<<"key"<<rotate->parent->key<<endl;
	l->right->parent=rotate;
	rotate->left=l->right;
	//deal with l
	l->parent=rotate->parent;
	if(rotate->parent==NIL)
	{
		ROOT=l;
		l->parent=NIL;
	}
	else if(rotate==rotate->parent->left)
		rotate->parent->left=l;
	else
		rotate->parent->right=l;
	//deal with rotate
	rotate->parent=l;
	l->right=rotate;
}
template<typename Type>
TreeNode<Type>* RBTree<Type>::insert(Type key)
{
	TreeNode<Type> *node=new TreeNode<Type>;
	TreeNode<Type> *down=ROOT;
	TreeNode<Type> *s=NIL;
	while(down!=NIL)
	{
		s=down;
		if(key<down->key)
			down=down->left;
		else
			down=down->right;
	}//找到合适位置
	node->parent=s;
	if(s==NIL)
	{
		ROOT=node;
		node->parent=NIL;
	}
	else if(key<s->key)
		s->left=node;
	else
		s->right=node;
	node->key=key;
	node->left=NIL;
	node->right=NIL;
	node->color=RED;
	RB_insert_fixup(node);
	return node;
}
template<typename Type>
void RBTree<Type>::RB_insert_fixup(TreeNode<Type>*& change)
{
	// TreeNode<Type>*change=node;
	TreeNode<Type>*father;
	TreeNode<Type>*uncle;
	while(change->parent->color==RED)
	{
		father=change->parent;
		if(father==father->parent->left)
		{
			uncle=father->parent->right;//父节点的兄弟
			if(uncle->color==RED)//uncle同样为red
			{
				father->color=BLACK;
				uncle->color=BLACK;
				father->parent->color=RED;
				change=father->parent;//进行循环
			}else 
			{
				//cout<<"uncle node color=black"<<endl;
				if(change==father->right)//内插入，左旋
				{
					change=father;
					//cout<<"before rotate key:"<<change->key<<" color "<<change->color<<endl;
					left_rotate(change);
					father=change->parent;
					//cout<<"after rotate key:"<<change->key<<" color "<<change->color<<endl;
					// cout<<"内插入"<<endl;
				}
				//外插入
				father->color=BLACK;
				father->parent->color=RED;//改变颜色
				// cout<<"before rotate key:"<<change->key<<" color "<<change->color<<endl;
				right_rotate(father->parent);
				// cout<<"before rotate key:"<<change->key<<" color "<<change->color<<endl;
			}
		}
		else
		{
			uncle=father->parent->left;//父节点的兄弟
			if(uncle->color==RED)//uncle同样为red
			{
				father->color=BLACK;
				uncle->color=BLACK;
				father->parent->color=RED;
				change=father->parent;//进行循环
			}else
			{
				if(change==father->left)//内插入
				{
					change=father;
					right_rotate(change);
					father=change->parent;
				}
				//外插入
				father->color=BLACK;
				father->parent->color=RED;
				left_rotate(father->parent);
			}
		}
	}
	ROOT->color=BLACK;
}
template<typename Type>
TreeNode<Type>* RBTree<Type>::search(Type key)
{
	TreeNode<Type> *p=ROOT;
	while(p!=NIL&&p->key!=key)
	{
		if(key<p->key)
			p=p->left;
		else
			p=p->right;
	}
	return p;
}
template<typename Type>
TreeNode<Type>* RBTree<Type>::remove(Type key)
{
	TreeNode<Type> *p = this->search(key);
	if(p==NIL)
		return p;
	//rn 为需要改变的节点，找到得key节点，如果只有一个孩子或者没有孩子，则需要被删除的就是该节点，否则（两个孩子）
	//需要删除的是直接后继节点（首先将key节点用后继节点代替）后继节点没有左孩子
	//最后rn最多只有一个孩子
	TreeNode<Type> *rn=NIL;
	TreeNode<Type> *act;
	if(p->left==NIL || p->right==NIL)
		rn = p;
	else
		rn = this->successor(p);
	if(rn->left!=NIL)//如果被删除的节点左孩子不空，则使用act纪录(key节点只有左孩子的情况)
		act=rn->left;
	else//act纪录key没有孩子，有右孩子，双子情况
		act=rn->right;

	act->parent=rn->parent;//更新父节点
	if(rn->parent==NIL)
		ROOT=act;//已经将act得parent修改成NIL了
	else if(rn == rn->parent->left)
		rn->parent->left=act;
	else
		rn->parent->right=act;
	if(rn!=p)//key有两个孩子时，实际删除的是p的直接后继rn节点，所以需要将后继节点的信息复制key节点中
		p->key=rn->key;
	if(rn->color==BLACK)
		RB_delete_fixup(act);
	return rn;
}
//删除一个黑色节点后导致两边的bh不同。
template<typename Type>
void RBTree<Type>::RB_delete_fixup(TreeNode<Type> *&_node)
{
	TreeNode<Type>*father,*brother,*node;
	node=_node;
	father=node->parent;
	while(node!=ROOT&&node->color==BLACK)//如果color(x)为red，只需要讲color(x)=black就行了
	{
		if(node=father->left)//color(node)=black,father左孩子得black nodes(m-1) =father右孩子的black nodes(m) -1
		{
			brother=father->right;
			if(brother->color==RED)//color(father)=black,********************case 1
			{
				brother->color=BLACK;
				father->color=RED;
				left_rotate(father);//修改了树结构,这一步后brother为node得祖父节点并且brother右孩子的black nodes = m不变
				brother=parent->right;//修正node得兄弟节点，现在color(father)=black right(father)=black,并且father->left得
				//black nodes还为m-1,father->right得black nodes = m
			}
			//如果兄弟为黑，则根据兄弟的孩子来区分,color(Node)=black,color(brother)=black,color(father)未知
			if(brother->left->color==BLACK&&brother->right->color==BLACK)//********************case 2
			{
				brother->color=RED;//fater右孩子的black nodes = m-1
				node=father;//如果father为red，则循环结束，将father改为black，则整个以father为根的子树左右孩子的black nodes都为m
			}
			else 
			{
				if(brother->right->color==BLACK)//右孩子为黑色********************case 3
				{
					brother->left->color=BLACK;
					brother->color=RED;
					right_rotate(brother);     
					brother=father->right;//brother的右孩子为red
				}
				//if(brother->right->color==RED)************************case 4
				father->color=BLACK;
				brother->right->color=BLACK;//red修改成black
				brother->color=father->color;
				//执行旋转后，brother为node得祖父，brother右孩子得black nodes=m,做孩子的black nodes=m(+father为黑色)
				left_rotate(father);
				node=ROOT;//结束
			}
		}
	}
	node->color=BLACK;
}
template<typename Type>
void RBTree<Type>::inorder(TreeNode<Type>*node)
{
	if(node!=NIL)
	{
		inorder(node->left);
		if(node->color==RED)
			if(node->left->color==RED||node->right->color==RED)
				cout<<"wrong"<<" ";
		cout<<node->key<<" ";
		inorder(node->right);
	}

}