rbtree.h

红黑树——一种数据结构的可视化画法

#ifndef RBTREE_H
#define RBTREE_H

#pragma once

#include<string.h>
#include"MainFrm.h"


enum Coulor{RED,BLACK};
typedef struct Node
{

	Coulor color;
	int key;
	Node *p,*left,*right;
	int size;
	char *name;               //the description data that the  node contained

}Node,*pNode;

 

 /*
 Nil.color=BLACK;
 Nil.size=0;
 Nil.p=0;
 Nil.left=0;
 Nil.right=0;
 //Nil.name=new char[4];
 //strcpy(Nil.name,"nil");
 /*/
extern Node Nil;  //哨兵
extern const pNode nil;
class rbTree
{
public:
	pNode root;
    pNode  cur;
public:
	rbTree(){root=cur=&Nil;};
	////////////////////////////
	void setName(pNode x,const char*na)
	{ 
	  x->name=new char[strlen(na)+1];
	  strcpy(x->name,na);
	}

    pNode newNode(int k,const char*na="N",pNode pa=nil,pNode le=nil,pNode ri=nil)
	{
		pNode ne=new Node;
		ne->key=k;
		ne->color=RED;
		ne->left=le;
		ne->p=pa;
		ne->right=ri;
		ne->size=1;
		setName(ne,na);
		return ne;
	}
	////////////////////////////////////////
	//访问p,left,right等
	pNode &p(pNode x){return x->p;};
	pNode &left(pNode x){return x->left;};
	pNode &right(pNode x){return x->right;};
    int   &size(pNode x){return x->size;};
	Coulor &color(pNode x){return x->color;};
	int   &key(pNode x){return x->key;};

	//
	const pNode  P(pNode x){return x->p;};
	const pNode  Left(pNode x){return x->left;};
	const pNode  Right(pNode x){return x->right;};
    const int    Size(pNode x){return x->size;};
	const Coulor Color(pNode x){return x->color;};
	const int    Key(pNode x){return x->key;};

	////////////////////////////////////////
	pNode successor(pNode x)
	{
		if(Right(x) != nil)
			return minimum(Right(x));
		pNode y= P(x);
		while ( y!=nil && x==Right(y) )
		{
			x=y;
			y=P(y);
		}
		return y;
	}
	//////////////////////////
	pNode minimum( pNode x)
	{
		while (Left(x)!=nil)
			x=Left(x);
		return x;
	}
	////////////////////////////
	int Bheight(pNode x)
	{
		pNode y=x;
		int k=0;
		while(y!=nil)
		{
			if(Color(y)==BLACK)
				k++;
			y=Left(y);
		}
		return k;
	}
	////////////////////////////////////////////////////////////
	//左旋转
   void lrotate(pNode x)
   {
	   pNode y=Right(x);
	   //维护size;
	   int sx=x->size;
	   int sy=y->size;
	   size(y)=sx;
	   size(x)=sx-size(Right(y))-1;

	   right(x)=Left(y);
	   p(Left(y))=x;
	   p(y)=P(x);
	   if(P(x)==nil)
	   {
		   root=y;
	   }
	   else if( x == Left(P(x)) )
	   {
		   left(P(y))=y;
	   }
	   else
		   right(P(x))=y;
       left(y)=x;
	   p(x)=y;
   }
   //右旋转
   void rrotate(pNode x)
   {
	   pNode y=Left(x);
	   
	   //维护size;
	   
	   size(y)=Size(x);
	   size(x)=Size(x)-Size(Left(y))-1;

	   left(x)=Right(y);
	   p(Right(y))=x;
	   p(y)=P(x);
	   if(P(x)==nil)
	   {
		   root=y;
	   }
	   else if(x==Left(P(x)))
	   {
		   left(P(y))=y;
	   }
	   else
		   right(P(x))=y;
       right(y)=x;
	   p(x)=y;
   }
   ///////////////////////////////////////////////
   //插入及其调整
   //插入
   void rbInsert(pNode z)
   {
	   pNode y=nil;
	   pNode x=root;

	   while(x!=nil)
	   {
		   y=x;
		   size(x)=Size(x)+1;
		   if(Key(z) < Key(x))
			   x=Left(x);
		   else
			   x=Right(x); 
	   }
	   p(z)=y;
	   if(y == nil)
		   root=z;
	   else if(Key(z) <Key(y))
		   left(y)=z;
	   else
		   right(y)=z;
	   rbInsertFixUp(z);


   }
   //调整
   void rbInsertFixUp(pNode z)
   {
	   while(Color(P(z)) == RED)
	   {
		   if( P(z) == Left(P(P(z))))
		   {
			   pNode y=Right(P(P(z)));
		       if(Color(y) == RED)
			   {
				   color(P(z)) = BLACK;
				   color(y)= BLACK;
				   color(P(P(z))) =RED;
				   z=P(P(z));
			   }
			   else 
			   { 
				   if(z == Right(P(z)))
				   {
					   z=P(z);
				       lrotate(z);
				   }
				   color(P(z))=BLACK;
				   color(P(P(z)))=RED;
				   rrotate(p(P(z)));
			   }
		   }
		   else
		   {
			   pNode y=Left(P(P(z)));
		       if(Color(y) == RED)
			   {
				   color(P(z)) = BLACK;
				   color(y)= BLACK;
				   color(P(P(z))) =RED;
				   z=P(P(z));
			   }
			   else 
			   { 
				   if(z == Left(P(z)))
				   {
					   z=P(z);
				       rrotate(z);
				   }
				   color(P(z))=BLACK;
				   color(P(P(z)))=RED;
				   lrotate(p(P(z)));
			   }
		   }
	   }
      color(root)=BLACK;

   }
   //////////////////////////////////////////////
   //删除及其调整
   //删除
   pNode rbDelete(pNode z)
   {
	   pNode x,y;
	   if(Left(z) == nil ||Right(z)==nil)
		   y=z;
	   else
		   y=successor(z);
	   if(Left(y) !=nil)
		    x=Left(y);
	   else
		   x=Right(y);
	   p(x)=P(y);

	   if(P(y) ==nil)
		   root=x;
	   else if(y==Left(P(y)) )
		   left(P(y))=x;
       else
		   right(P(y))=x;
	   if(y!=z)
	   {
		   key(z)=Key(y);//
	   }
       rbDeleteMaitainSize(y);
	   if(Color(y)==BLACK)
		   rbDeleteFixUp(x);
	   return y;

   }
   //调整
   void rbDeleteFixUp(pNode x)
   {
	   while(x!=root && Color(x)==BLACK)
	   {
		   if(x ==Left(P(x)) )
		   {
			   pNode w=Right(P(x));
			   //case1 
               if(Color(w)==RED)
			   {
				   color(w)=BLACK;
				   color(P(x))=RED;
				   lrotate(P(x));
				   w=Right(P(x));
			   }

               //case 2,3,4
			   if(Color(Left(w))==BLACK && Color(Right(w)) ==BLACK)
			   {
				   color(w)=RED;
				   x=P(x);
			   }
			   else if(Color(Right(w)) == BLACK)
			   {
				   color(Left(w))=BLACK;
				   color(w)=RED;
				   rrotate(w);
				   w=Right(P(x));
			   }
			   else
			   {
				   color(w)=Color(P(x));
				   color(P(x))=BLACK;
				   lrotate(P(x));
				   x=root;
			   }
		   }
		   else
			   {
			   pNode w=Left(P(x));
			   //case1 
               if(Color(w)==RED)
			   {
				   color(P(x))=RED;
				   rrotate(P(x));
				   w=Left(P(x));
			   }

               //case 2,3,4
			   if(Color(Left(w))==BLACK && Color(Right(w)) ==BLACK)
			   {
				   color(w)=RED;
				   x=P(x);
			   }
			   else if(Color(Left(w)) == BLACK)
			   {
				   color(Right(w))=BLACK;
				   color(w)=RED;
				   lrotate(w);
				   w=Left(P(x));
			   }
			   else
			   {
				   color(w)=Color(P(x));
				   color(P(x))=BLACK;
				   rrotate(P(x));
				   x=root;
			   }
		   }   
	   }
	   color(x)=BLACK;
   }
   /////////////////////
   //维护size
   void rbDeleteMaitainSize(pNode x)
   {
	   cur=P(x);
	   while(cur!=nil)
	   {
		   size(cur)--;
		   cur=P(cur);
	   }
   }
   int Rank(pNode x)
   {
	   int r= Size(Left(x))+1;
	   pNode y=x;
	   while(y!=root)
	   {
		   if(   y  == Right( P(y) )    )
		   {
			   r=r+Size(Left( P(y) ) )+1;
		   }
		   y=P(y);
	   }
		  return r;
   }
 
   pNode OS_Select(pNode x,int i)
   {
	   if(i>Size(x))
		   return nil;

	   int r=Size(Left(x))+1;
	   if(i==r)
		   return x;
	   else if(i<r)
		   return  OS_Select(Left(x),i);
	   else
		   return  OS_Select(Right(x),i-r);
   }

   friend class CMyWnd;//显示红黑树的图形界面类；
};

#endif