天天看點
傳回

今天完成了紅黑樹的删除操作。插入、删除完成。

#ifndef __BLACK_RED_TREE
#define __BLACK_RED_TREE

#include <iostream>

using namespace std;

#define RED 1
#define BLACK 0

#define OutMsg(FunName) (cout<<FunName<<endl)

#define PRINTFUN() cout<<__FUNCTION__<<endl

template<class T> class BlackTree;

template<class T> class BlackRedNode
{
public:
	template<class T> friend class BlackRedTree;
	BlackRedNode():Color(BLACK),Left(NULL),Right(NULL),Parent(NULL){;}
	BlackRedNode(const T& e,int NodeColor=BLACK,BlackRedNode<T>* LeftNode=NULL,BlackRedNode<T>* RightNode=NULL,BlackRedNode<T>* ParentNode=NULL):Data(e),Color(NodeColor),Left(LeftNode),Right(RightNode),Parent(ParentNode){;}
	

private:
	T Data;
	int Color;//0:black,1:red
	BlackRedNode<T>* Left,*Right;
	BlackRedNode<T>* Parent;

	
};

template<class T> class BlackRedTree
{
public:
	BlackRedTree():Root(NULL){;}
	BlackRedTree(const T& x);
	BlackRedTree<T>& Insert(const T& e);
	BlackRedTree<T>& Delete(const T& e);

	void PrintTree() const{PrintTree(Root,0);}//列印紅黑樹
	

private:

	void PrintTree(BlackRedNode<T>* Node,int Layer)const;

	BlackRedNode<T>* Root;

private:
	
	bool AdjustColorAfterInsert(BlackRedNode<T>* Node); //Node為新插入節點的指針。插入節點之後，判斷是否違反RB2，如果違反則進行調整
	
	//XYr類型，調整之後，可能還需要繼續調整
	bool LXr_AfterInsert(BlackRedNode<T>* Node);//插入之後，如果為LXr形式，則進行相應調整，其他與此類似，Node為插入的元素指針。X為L或者R
	bool RXr_AfterInsert(BlackRedNode<T>* Node);//插入之後為RXr類型：X為R或者L;
	//XYb類型，調整之後不再需要繼續調整
	bool LLb_AfterInsert(BlackRedNode<T>* Node);
	bool LRb_AfterInsert(BlackRedNode<T>* Node);
	bool RRb_AfterInsert(BlackRedNode<T>* Node);
	bool RLb_AfterInsert(BlackRedNode<T>* Node);

	bool IfNeedAdjustAfterDelete(BlackRedNode<T>* Node,bool& NeedFlag);//該函數用來根據Node是否為黑色節點來設定NeedFlag為true或者false
	int GetRedChildNumOfNode(BlackRedNode<T>* Node);//擷取Node的紅色孩子的數量
	
	bool AdjustColorAfterDelete(BlackRedNode<T>* Y,BlackRedNode<T>* Py,int DirectionOfY);//Y為删除節點位置上的新節點，Y可能為NULL;Py表示Y的父節點;DirectionOfY表示Node是Node的父節點的左孩子（0）還是右孩子（1）
	//删除節點之後，顔色調整具體函數
	bool RbZero_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);//參數含義與AdjustColorAfterDelete相同
	bool RbOne_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);//Rb1型調整函數
	bool RbOne_VLeftRed_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);//Rb1型調整函數：v的left是red
	bool RbOne_VRightRed_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);//Rb1型調整函數:v的right是red
	bool RbTwo_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);//
	
	bool RrZero_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);
	bool RrOne_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);
	bool RrOne_VRLr_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);
	bool RrOne_VRRr_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);
	bool RrTwo_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);

	bool LbZero_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);
	bool LbOne_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);//Lb1型調整函數
	bool LbOne_VLeftRed_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);//Lb1型調整函數：v的left是red
	bool LbOne_VRightRed_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);//Lb1型調整函數:v的right是red
	bool LbTwo_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);

	bool LrZero_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);
	bool LrOne_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);
	bool LrOne_VLRr_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);
	bool LrOne_VLLr_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);
	bool LrTwo_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY);

	int GetDirctionOfYInPy(BlackRedNode<T>* Y,BlackRedNode<T>* Py);//擷取Y在Py子樹上的位置：0，左子樹，1：右子樹

};

template<class T> BlackRedTree<T>::BlackRedTree(const T& x)
{
	Root = new BlackRedNode<T>(x);
}

template<class T> BlackRedTree<T>& BlackRedTree<T>::Insert(const T& e)
{
	if(!Root)
	{
		Root = new BlackRedNode<T>(e);
		return *this;
	}
	BlackRedNode<T>* Temp,*pTemp;
	int InsertDirection = 0;//0:左，1：右

	Temp = Root;
	while(Temp)
	{
		pTemp = Temp;
		if(e > Temp->Data)
		{
			Temp = Temp->Right;
			InsertDirection = 1;
		}
		else
		{
			Temp = Temp->Left;
			InsertDirection = 0;
		}
		if(Temp)
		{
			Temp->Parent = pTemp;
		}
	}
	//這裡的temp即為要插入的位置
	Temp = new BlackRedNode<T>(e,RED);
	Temp->Parent = pTemp;
	if(InsertDirection)
	{
		pTemp->Right = Temp;
	}
	else
	{
		pTemp->Left = Temp;
	}
	//接下來調整顔色
	AdjustColorAfterInsert(Temp);
	return *this;

}

template<class T> bool BlackRedTree<T>::AdjustColorAfterInsert(BlackRedNode<T>* Node)
{

	BlackRedNode<T>* PNode,*GNode;
	if(Node == Root)
	{
		Root->Color = BLACK;
		return true;
	}
	PNode = Node->Parent;
	if(PNode->Color == BLACK)
	{
		cout<<"PNode->Color == BLACK,這時候不需要調整顔色"<<endl;
		return true;
	}
	//既然PNode是紅色的，那麼一定有GNode存在,而且GNode一定是黑色的
	GNode = PNode->Parent;
	
	//一共有8種情況：LLr,LRr,RRr,RLr,LLb,LRb,RRb,RLb.(這種情況包括gu的另一個孩子是外部節點的情況)
	if(PNode == GNode->Left && (GNode->Right!=NULL && GNode->Right->Color == RED))//LXr
	{
		LXr_AfterInsert(Node);
		return AdjustColorAfterInsert(GNode);
	}

	if(PNode == GNode->Right && (GNode->Left!=NULL && GNode->Left->Color == RED))//RXr
	{
		RXr_AfterInsert(Node);
		return AdjustColorAfterInsert(GNode);
	}

	if(PNode == GNode->Left && Node == PNode->Left && (GNode->Right ==NULL || (GNode->Right!=NULL && GNode->Right->Color == BLACK) ))//LLb
	{
		return LLb_AfterInsert(Node);
	}
	
	if(PNode == GNode->Left && Node == PNode->Right && (GNode->Right ==NULL || (GNode->Right!=NULL && GNode->Right->Color == BLACK) ))//LRb
	{
		return LRb_AfterInsert(Node);
	}
	if(PNode == GNode->Right && Node == PNode->Right && (GNode->Left == NULL || (GNode->Left!=NULL && GNode->Left->Color == BLACK)))//RRb
	{
		return RRb_AfterInsert(Node);
	}
	if(PNode == GNode->Right && Node == PNode->Left && (GNode->Left == NULL || (GNode->Left!=NULL && GNode->Left->Color == BLACK)))//RLb
	{
		return RLb_AfterInsert(Node);
	}

}

template<class T> bool BlackRedTree<T>::LXr_AfterInsert(BlackRedNode<T>* Node)
{
	OutMsg("LXr_AfterInsert");
	BlackRedNode<T>* PNode,*GNode;
	PNode = Node->Parent;
	GNode = PNode->Parent;
	if( PNode!= GNode->Left || GNode->Right == NULL || (GNode->Right!=NULL && GNode->Right->Color!=RED) )
	{
		cout<<"插入節點之後，不是LXr類型"<<endl;
		return true;
	}
	//根據資料結構上給出的算法進行顔色調整
	GNode->Color = RED;
	PNode->Color = BLACK;
	GNode->Right->Color = BLACK;
	//這樣調整完之後，可能還存在違反RB2，這個交給AdjustColorAfterInsert函數來處理
	return true;
}

template<class T> bool BlackRedTree<T>::RXr_AfterInsert(BlackRedNode<T>* Node)
{
	OutMsg("RXr_AfterInsert");
	BlackRedNode<T>* PNode,*GNode;
	PNode = Node->Parent;
	GNode = PNode->Parent;
	if(PNode!= GNode->Right || (GNode->Left!=NULL && GNode->Left->Color!=RED))
	{
		cout<<"插入節點之後，不是RXr類型"<<endl;
		return true;
	}
	//根據資料結構上給出的算法進行顔色調整
	GNode->Color = RED;
	PNode->Color = BLACK;
	GNode->Left->Color = BLACK;
	//這樣調整完之後，可能還存在違反RB2，這個交給AdjustColorAfterInsert函數來處理
	return true;
}


template<class T>  bool BlackRedTree<T>::LLb_AfterInsert(BlackRedNode<T>* Node)
{
	OutMsg("LLb_AfterInsert");
	BlackRedNode<T>* PNode,*GNode;
	PNode = Node->Parent;
	GNode = PNode->Parent;
	if(PNode!= GNode->Left || Node!= PNode->Left || (GNode->Right!=NULL && GNode->Right->Color!=BLACK))
	{
		cout<<"插入節點之後，不是LLb類型"<<endl;
		return true;
	}
	//根據資料結構上給出的算法進行旋轉
	BlackRedNode<T>* NewNode,*NodeToDelete; 
	NewNode = new BlackRedNode<T>(GNode->Data,RED);
	NodeToDelete = GNode->Left;

	NewNode->Left = NodeToDelete->Right;
	NewNode->Right = GNode->Right;
	
	GNode->Left = NodeToDelete->Left;
	GNode->Right = NewNode;
	GNode->Data = NodeToDelete->Data;
	//調整父節點
	if(NewNode)
	{
		NewNode->Parent = GNode;
		if(NewNode->Left)
		{
			NewNode->Left->Parent = NewNode;
		}
		if(NewNode->Right)
		{
			NewNode->Right->Parent = NewNode;
		}
	}
	if(GNode->Left)
	{
		GNode->Left->Parent = GNode;
	}
	if(GNode->Right)
	{
		GNode->Right->Parent = GNode;
	}

	//删除節點

	if(!NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = NULL;
	}
	return true;

}

template<class T>  bool BlackRedTree<T>::LRb_AfterInsert(BlackRedNode<T>* Node)
{
	OutMsg("LRb_AfterInsert");
	BlackRedNode<T>* PNode,*GNode;
	PNode = Node->Parent;
	GNode = PNode->Parent;
	if(PNode!= GNode->Left || Node!= PNode->Right || (GNode->Right!=NULL && GNode->Right->Color!=BLACK))
	{
		cout<<"插入節點之後，不是LRb類型"<<endl;
		return true;
	}
	//根據資料結構上給出的算法進行旋轉
	BlackRedNode<T>* NewNode,*NodeToDelete; 
	NewNode = new BlackRedNode<T>(GNode->Data,RED);
	NodeToDelete = PNode ->Right;

	NewNode->Left = NodeToDelete->Right;
	NewNode->Right = GNode->Right;
	
	GNode->Left->Right = NodeToDelete->Left;
	GNode->Right = NewNode;
	GNode->Data = NodeToDelete->Data;

	PNode->Right = NodeToDelete ->Left;

	//調整父節點
	if(NewNode)
	{
		if(NewNode->Left)
		{
			NewNode->Left->Parent = NewNode;
		}
		if(NewNode->Right)
		{
			NewNode->Right->Parent = NewNode;
		}
	}
	if(GNode->Left->Right)
	{
		GNode->Left->Right->Parent = GNode;
	}
	if(GNode->Right)
	{
		GNode->Right->Parent = GNode;
	}
	if(PNode->Right)
	{
		PNode->Right->Parent = PNode;
	}

	//删除節點
	if(!NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = 0;
	}
	return true;
}

template<class T> bool BlackRedTree<T>::RRb_AfterInsert(BlackRedNode<T>* Node)
{
	OutMsg("RRb_AfterInsert");
	BlackRedNode<T>* PNode,*GNode;
	PNode = Node->Parent;
	GNode = PNode->Parent;
	if(PNode!= GNode->Right || Node!= PNode->Right || (GNode->Left!=NULL && GNode->Left->Color!=BLACK))
	{
		cout<<"插入節點之後，不是RRb類型"<<endl;
		return true;
	}
	//進行旋轉
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode = new BlackRedNode<T>(GNode->Data,RED);
	NodeToDelete = PNode;

	NewNode->Left = GNode->Left;
	NewNode->Right = NodeToDelete->Left;
	
	GNode->Data = NodeToDelete->Data;
	GNode->Left = NewNode;
	GNode->Right = NodeToDelete->Right;

	//調整父節點
	if(NewNode)
	{
		if(NewNode->Left)
		{
			NewNode->Left->Parent = NewNode;
		}
		if(NewNode->Right)
		{
			NewNode->Right->Parent = NewNode;
		}
	}
	if(GNode->Left)
	{
		GNode->Left->Parent = GNode;
	}
	if(GNode->Right)
	{
		GNode->Right->Parent = GNode;
	}
	//删除節點
	if(!NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = 0;
	}
	return true;

}

template<class T> bool BlackRedTree<T>::RLb_AfterInsert(BlackRedNode<T>* Node)
{
	OutMsg("RLb_AfterInsert");
	BlackRedNode<T>* PNode,*GNode;
	PNode = Node->Parent;
	GNode = PNode->Parent;
	if(PNode!= GNode->Right || Node!= PNode->Left || (GNode->Left!=NULL && GNode->Left->Color!=BLACK))
	{
		cout<<"插入節點之後，不是RLb類型"<<endl;
		return true;
	}
	//進行旋轉
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode = new BlackRedNode<T>(GNode->Data,RED);
	NodeToDelete = PNode->Left;

	NewNode->Left = GNode->Left;
	NewNode->Right = NodeToDelete->Left;
	
	GNode->Data = NodeToDelete->Data;
	GNode->Left = NewNode;
	GNode->Right->Left = NodeToDelete->Right;

	//調整父節點
	if(NewNode)
	{
		if(NewNode->Left)
		{
			NewNode->Left->Parent = NewNode;
		}
		if(NewNode->Right)
		{
			NewNode->Right->Parent = NewNode;
		}
	}
	if(GNode->Left)
	{
		GNode->Left->Parent = GNode;
	}
	if(GNode->Right->Left)
	{
		GNode->Right->Left->Parent = GNode;
	}
	//删除節點
	if(!NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = 0;
	}
	return true;
}

template <class T> void BlackRedTree<T>::PrintTree(BlackRedNode<T> *t,int layer) const{
    if(t == NULL ) return;
	if(t->Right) PrintTree(t->Right,layer+1);
    for(int i =0;i<layer;i++) cout<<"  ";
	cout<<t->Data<<":"<<t->Color<<endl;
	if(t->Left) PrintTree(t->Left,layer+1);
}

template<class T> BlackRedTree<T>& BlackRedTree<T>::Delete(const T& e)
{
	BlackRedNode<T>* Temp;
	Temp=Root;
	//先找到e值的節點
	while(Temp)
	{
		if(e > Temp->Data)
		{
			Temp = Temp->Right;
		}
		if(e< Temp->Data)
		{
			Temp = Temp->Left;
		}
		if(e == Temp->Data)
		{
			break;
		}
	}
	if(!Temp)
	{
		cout<<"沒有找到節點："<<e<<endl;
		return *this;
	}
	//到這裡Temp即為找到的值為e的節點
	
	//如果沒有孩子則可直接删除
	//如果在temp隻有一個孩子則将Temp的父節點指向其唯一孩子即可
	//如果有兩個孩子，隻需将該元素替換為它的左子樹中的最大元素
	BlackRedNode<T> *Y;//代替被删除節點位置的節點
	BlackRedNode<T>* Py;//y的父節點
	int DirectionOfYInPy=0;//y是py左孩子，則為0，否則為1
	bool NeedAdjustFlag=false;//是否需要調整顔色的标志，如果删除的是黑色節點，需要調整顔色
	if(Temp->Left==NULL && Temp->Right==NULL)
	{
		if(Temp == Root)
		{
			delete Temp;
			Temp=NULL;
			return *this;
		}
		Py = Temp->Parent;
		if(Temp==Py->Left)
		{
			DirectionOfYInPy=0;
			Py->Left =NULL;
		}
		else
		{
			DirectionOfYInPy=1;
			Py->Right =NULL;
		}
		IfNeedAdjustAfterDelete(Temp,NeedAdjustFlag);

		delete Temp;
		Temp=NULL;
		Y=NULL;
	}
	else 
		if((Temp->Left==NULL && Temp->Right!=NULL) || (Temp->Left!=NULL && Temp->Right==NULL))
		{
			if(Temp==Root)
			{
				Py=Root;
			}
			else
			{
				Py = Temp->Parent;
			}
			
			if(Temp->Left)
			{
				Y=Temp->Left;
			}
			else
			{
				Y=Temp->Right;
			}
			Y->Parent = Py;
			if(Temp==Py->Left)
			{
				Py->Left = Y;
				DirectionOfYInPy =0;
			}
			else
			{
				Py->Right = Y;
				DirectionOfYInPy=1;
			}
			IfNeedAdjustAfterDelete(Temp,NeedAdjustFlag);
			if(Temp == Root)
			{
				Root = Py;
			}
			delete Temp;
			Temp=NULL;

		}
		else if(Temp->Left && Temp->Right)
		{
			Y=Temp->Left;
			Py=Temp;
			DirectionOfYInPy = 0;
			while(Y->Right)
			{
				Py=Y;
				Y=Y->Right;
				DirectionOfYInPy = 1;
			}
			Temp->Data = Y->Data;
			if(Y->Left)
			{
				if(DirectionOfYInPy == 1)
				{
					DirectionOfYInPy = 1;
				}
				else
				{
					DirectionOfYInPy = 0;
				}
				Temp=Y;
				Y->Left->Parent=Py;
				Py->Right = Y->Left;//根據Y是Temp左子樹的最大孩子，知道Y一定是Py的右孩子
			}
			else
			{
				//Y已經是葉子節點
				if(DirectionOfYInPy == 1)
				{
					DirectionOfYInPy = 1;
				}
				else
				{
					DirectionOfYInPy = 0;
				}
				Temp = Y;
				Y = NULL;

				if(DirectionOfYInPy == 0)
				{
					Py->Left=NULL;
				}
				if(DirectionOfYInPy == 1)
				{
					Py->Right=NULL;
				}
				
			}
			IfNeedAdjustAfterDelete(Temp,NeedAdjustFlag);
			delete Temp;
			Temp=NULL;

			

		}
	//已經删除節點，并且y是删除節點的位置，py為y的父節點
	//進行顔色調整
	if(!NeedAdjustFlag)
	{
		return *this;
	}
	
	AdjustColorAfterDelete(Y,Py,DirectionOfYInPy);

	return *this;

}

template<class T> bool BlackRedTree<T>::AdjustColorAfterDelete(BlackRedNode<T>* Y,BlackRedNode<T>* Py,int DirectionOfY)
{
	if(Py==NULL)
	{
		Root ->Color=BLACK;
		return true;
	}
	/*
	if(DirectionOfY!=0 || DirectionOfY!=1)
	{
		cout<<"Error,AdjustColorAfterDelete,DirectionOfY:"<<Y<<endl;
		return false;
	}
	*/

	BlackRedNode<T>* AnotherChildOfPy;//Y的父節點的另外一個孩子的指針
	int OldColorOfPy ;

	if(DirectionOfY==1)//右孩子
	{
		AnotherChildOfPy = Py->Left;
		if(AnotherChildOfPy->Color == BLACK)
		{
			
			switch( GetRedChildNumOfNode(AnotherChildOfPy) )
			{
			case 0:
				OldColorOfPy = Py->Color;
				RbZero_AfterDelete(Py,DirectionOfY);
				if(OldColorOfPy == BLACK)
				{
					Y= Py;
					Py= Py->Parent;
					
					return AdjustColorAfterDelete(Y,Py,GetDirctionOfYInPy(Y,Py));
				}
				break;
			case 1:
				RbOne_AfterDelete(Py,DirectionOfY);
				break;
			case 2:
				RbTwo_AfterDelete(Py,DirectionOfY);
				break;
			}
		}
		else
		{
			switch( GetRedChildNumOfNode(AnotherChildOfPy->Right) )
			{
			case 0:
				RrZero_AfterDelete(Py,DirectionOfY);
				break;
			case 1:
				RrOne_AfterDelete(Py,DirectionOfY);
				break;
			case 2:
				RrTwo_AfterDelete(Py,DirectionOfY);
				break;
			}

		}
	}
	else
	{
		AnotherChildOfPy = Py->Right;
		if(AnotherChildOfPy->Color == BLACK)
		{
			
			switch( GetRedChildNumOfNode(AnotherChildOfPy) )
			{
			case 0:
				OldColorOfPy = Py->Color;
				LbZero_AfterDelete(Py,DirectionOfY);
				if(OldColorOfPy == BLACK)
				{
					Y= Py;
					Py= Py->Parent;
					
					return AdjustColorAfterDelete(Y,Py,GetDirctionOfYInPy(Y,Py));
				}

				break;
			case 1:
				LbOne_AfterDelete(Py,DirectionOfY);
				break;
			case 2:
				LbTwo_AfterDelete(Py,DirectionOfY);
				break;
			}
		}
		else
		{
			switch( GetRedChildNumOfNode(AnotherChildOfPy) )
			{
			case 0:
				LrZero_AfterDelete(Py,DirectionOfY);
				break;
			case 1:
				LrOne_AfterDelete(Py,DirectionOfY);
				break;
			case 2:
				LrTwo_AfterDelete(Py,DirectionOfY);
				break;
			}

		}

	}
	return true;

}

template<class T> bool BlackRedTree<T>::IfNeedAdjustAfterDelete(BlackRedNode<T>* Node,bool& NeedFlag)
{
	if(Node->Color == BLACK)
	{
		NeedFlag = true;
	}
	else
	{
		NeedFlag = false;
	}
	return true;
}

template<class T> int BlackRedTree<T>::GetRedChildNumOfNode(BlackRedNode<T>* Node)
{
	int Count=0;
	if(Node->Left)
	{
		if(Node->Left->Color == RED)
		{
			Count+=1;
		}
	}
	if(Node->Right)
	{
		if(Node->Right->Color == RED)
		{
			Count+=1;
		}
	}
	return Count;
}

template<class T> int BlackRedTree<T>:: GetDirctionOfYInPy(BlackRedNode<T>* Y,BlackRedNode<T>* Py)
{
	if(!Py)
	{
		return -1;
	}
	if(Y==Py->Left)
	{
		return 0;
	}
	if(Y==Py->Right)
	{
		return 1;
	}
	return -1;
}

template<class T> bool BlackRedTree<T>:: RbZero_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	Py->Color = BLACK;

	/*
	if(DirectionOfY==0)
	{
		Py->Right->Color = RED;
	}
	*/	
	Py->Left->Color = RED;
	return true;
}

template<class T> bool BlackRedTree<T>::RbOne_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	if(Py->Left->Left && Py->Left->Left->Color == RED)
	{
		RbOne_VLeftRed_AfterDelete(Py,DirectionOfY);
	}
	else
	{
		RbOne_VRightRed_AfterDelete(Py,DirectionOfY);
	}
	return true;
}

template<class T>  bool BlackRedTree<T>::RbOne_VLeftRed_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode= new BlackRedNode<T>(Py->Data,BLACK);
	NodeToDelete = Py->Left;

	NewNode->Left = NodeToDelete->Right;
	NewNode->Right = Py->Left;

	Py->Left = NodeToDelete->Left;
	Py->Right = NewNode;
	Py->Data = NodeToDelete->Data;

	//調整父節點資訊
	if(Py->Left)
	{
		Py->Left->Parent = Py;
	}
	if(Py->Right)
	{
		Py->Right->Parent = Py;
	}
	if(NewNode->Left)
	{
		NewNode->Left->Parent = NewNode;
	}
	if(NewNode->Right)
	{
		NewNode->Right->Parent = NewNode;
	}
	
	//調整顔色
	if(Py->Left)
	{
		Py->Left->Color = BLACK;
	}

	if(NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = NULL;
	}
	return true;

}

template<class T> bool BlackRedTree<T>::RbOne_VRightRed_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode= new BlackRedNode<T>(Py->Data,BLACK);
	NodeToDelete = Py->Left->Right;

	NewNode->Left = NodeToDelete->Right;
	NewNode->Right = Py->Right;

	Py->Left->Right = NodeToDelete->Left;
	Py->Right = NewNode;
	Py->Data = NodeToDelete->Data;

	//調整父節點資訊
	if(Py->Left->Right)
	{
		Py->Left->Right->Parent = Py->Left;
	}
	if(Py->Right)
	{
		Py->Right->Parent = Py;
	}
	if(NewNode->Left)
	{
		NewNode->Left->Parent = NewNode;
	}
	if(NewNode->Right)
	{
		NewNode->Right->Parent = NewNode;
	}
	
	//調整顔色
	

	if(NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = NULL;
	}
	return true;
}

template<class T> bool  BlackRedTree<T>:: RbTwo_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode= new BlackRedNode<T>(Py->Data,BLACK);
	NodeToDelete = Py->Left->Right;

	NewNode->Left = NodeToDelete->Right;
	NewNode->Right = Py->Right;

	Py->Left->Right = NodeToDelete->Left;
	Py->Right = NewNode;
	Py->Data = NodeToDelete->Data;

	//調整父節點資訊
	if(Py->Left->Right)
	{
		Py->Left->Right->Parent = Py->Left;
	}
	if(Py->Right)
	{
		Py->Right->Parent = Py;
	}
	if(NewNode->Left)
	{
		NewNode->Left->Parent = NewNode;
	}
	if(NewNode->Right)
	{
		NewNode->Right->Parent = NewNode;
	}
	
	//調整顔色

	if(NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = NULL;
	}
	return true;
}

template<class T> bool BlackRedTree<T>::RrZero_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode = new BlackRedNode<T>(Py->Data,BLACK);
	NodeToDelete = Py->Left;

	NewNode->Left = NodeToDelete->Right;
	NewNode->Left->Color = RED;
	NewNode->Right = Py->Right;

	Py->Data = NodeToDelete->Data;
	Py->Left = NodeToDelete->Left;
	Py->Right = NewNode;

	//調整父指針
	if(NewNode->Left)
	{
		NewNode->Left->Parent = NewNode;
	}
	if(NewNode->Right)
	{
		NewNode->Right->Parent = NewNode;
	}
	if(Py->Left)
	{
		Py->Left->Parent = Py;
	}
	if(Py->Right)
	{
		Py->Right ->Parent =Py;
	}
	if(NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = NULL;
	}
	return true;
}

template<class T> bool BlackRedTree<T>::RrOne_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	if(Py->Left->Right->Left!=NULL && Py->Left->Right->Left->Color==RED)
	{
		return RrOne_VRLr_AfterDelete(Py,DirectionOfY);
	}
	else
	{
		return RrOne_VRRr_AfterDelete(Py,DirectionOfY);
	}
}

template<class T> bool BlackRedTree<T>:: RrOne_VRLr_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode= new BlackRedNode<T>(Py->Data,BLACK);
	NodeToDelete = Py->Left->Right;

	NewNode->Left = NodeToDelete->Right;
	NewNode->Right = Py->Right;

	Py->Left->Right = NodeToDelete->Left;
	Py->Left->Right->Color = BLACK;
	Py->Right = NewNode;
	Py->Data = NodeToDelete->Data;

	//調整父節點資訊
	if(Py->Left->Right)
	{
		Py->Left->Right->Parent = Py->Left;
	}
	if(Py->Right)
	{
		Py->Right->Parent = Py;
	}
	if(NewNode->Left)
	{
		NewNode->Left->Parent = NewNode;
	}
	if(NewNode->Right)
	{
		NewNode->Right->Parent = NewNode;
	}
	
	//調整顔色

	if(NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = NULL;
	}
	return true;
}

template<class T> bool BlackRedTree<T>:: RrOne_VRRr_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode= new BlackRedNode<T>(Py->Data,BLACK);
	NodeToDelete = Py->Left->Right->Right;

	NewNode->Left = NodeToDelete->Right;
	NewNode->Right = Py->Right;

	Py->Left->Right->Right = NodeToDelete->Left;
	
	Py->Right = NewNode;
	Py->Data = NodeToDelete->Data;

	//調整父節點資訊
	if(Py->Left->Right->Right)
	{
		Py->Left->Right->Right->Parent = Py->Left->Right;
	}
	if(Py->Right)
	{
		Py->Right->Parent = Py;
	}
	if(NewNode->Left)
	{
		NewNode->Left->Parent = NewNode;
	}
	if(NewNode->Right)
	{
		NewNode->Right->Parent = NewNode;
	}
	
	//調整顔色

	if(NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = NULL;
	}
	return true;
}

template<class T> bool BlackRedTree<T>::RrTwo_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode= new BlackRedNode<T>(Py->Data,BLACK);
	NodeToDelete = Py->Left->Right->Right;

	NewNode->Left = NodeToDelete->Right;
	NewNode->Right = Py->Right;

	Py->Left->Right->Right = NodeToDelete->Left;
	
	Py->Right = NewNode;
	Py->Data = NodeToDelete->Data;

	//調整父節點資訊
	if(Py->Left->Right->Right)
	{
		Py->Left->Right->Right->Parent = Py->Left->Right;
	}
	if(Py->Right)
	{
		Py->Right->Parent = Py;
	}
	if(NewNode->Left)
	{
		NewNode->Left->Parent = NewNode;
	}
	if(NewNode->Right)
	{
		NewNode->Right->Parent = NewNode;
	}
	
	//調整顔色

	if(NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = NULL;
	}
	return true;
}

template<class T> bool BlackRedTree<T>::LbZero_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	Py->Color = BLACK;

	if(DirectionOfY==0)
	{
		Py->Right->Color = RED;
	}	
	return true;
}


template<class T> bool BlackRedTree<T>::LbOne_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)//Lb1型調整函數
{
	PRINTFUN();
	if(Py->Right->Left && Py->Right->Left->Color == RED)
	{
		LbOne_VLeftRed_AfterDelete(Py,DirectionOfY);
	}
	else
	{
		LbOne_VRightRed_AfterDelete(Py,DirectionOfY);
	}
	return true;
}
template<class T> bool BlackRedTree<T>::LbOne_VLeftRed_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)//Rb1型調整函數：v的left是red
{
	PRINTFUN();
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode= new BlackRedNode<T>(Py->Data,BLACK);
	NodeToDelete = Py->Left;

	NewNode->Left = Py->Left ;
	NewNode->Right = NodeToDelete->Left;

	Py->Left = NewNode ;
	Py->Right->Left = NodeToDelete->Right;
	Py->Data = NodeToDelete->Data;

	//調整父節點資訊
	if(Py->Left)
	{
		Py->Left->Parent = Py;
	}
	if(Py->Right->Left)
	{
		Py->Right->Left->Parent = Py->Right;
	}
	if(NewNode->Left)
	{
		NewNode->Left->Parent = NewNode;
	}
	if(NewNode->Right)
	{
		NewNode->Right->Parent = NewNode;
	}
	
	//調整顔色


	if(NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = NULL;
	}
	return true;


}
template<class T> bool BlackRedTree<T>::LbOne_VRightRed_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)//Rb1型調整函數:v的right是red
{
	PRINTFUN();
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode= new BlackRedNode<T>(Py->Data,BLACK);
	NodeToDelete = Py->Right;

	NewNode->Left = Py->Left;
	NewNode->Right = NodeToDelete->Left;

	Py->Left =NewNode ;
	Py->Right = NodeToDelete->Right;
	Py->Data = NodeToDelete->Data;

	//調整父節點資訊
	if(Py->Left)
	{
		Py->Left->Parent = Py;
	}
	if(Py->Right)
	{
		Py->Right->Parent = Py;
	}
	if(NewNode->Left)
	{
		NewNode->Left->Parent = NewNode;
	}
	if(NewNode->Right)
	{
		NewNode->Right->Parent = NewNode;
	}
	
	//調整顔色
	if(Py->Right)
	{
		Py->Right->Color = BLACK;
	}

	if(NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = NULL;
	}
	return true;
}

template<class T> bool BlackRedTree<T>::LbTwo_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode= new BlackRedNode<T>(Py->Data,BLACK);
	NodeToDelete = Py->Right->Left;

	NewNode->Left = Py->Left ;
	NewNode->Right = NodeToDelete->Left;

	Py->Right->Left = NodeToDelete->Right;
	Py->Left = NewNode;
	Py->Data = NodeToDelete->Data;

	//調整父節點資訊
	if(Py->Right->Left)
	{
		Py->Right->Left->Parent = Py->Right;
	}
	if(Py->Left)
	{
		Py->Left->Parent = Py;
	}
	if(NewNode->Left)
	{
		NewNode->Left->Parent = NewNode;
	}
	if(NewNode->Right)
	{
		NewNode->Right->Parent = NewNode;
	}
	
	//調整顔色

	if(NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = NULL;
	}
	return true;
}

template<class T> bool BlackRedTree<T>::LrZero_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode = new BlackRedNode<T>(Py->Data,BLACK);
	NodeToDelete = Py->Right;

	NewNode->Left = Py->Left;
	NewNode->Right = NodeToDelete->Left;
	NewNode->Right->Color = RED;

	Py->Data = NodeToDelete->Data;
	Py->Left =NewNode ;
	Py->Right =NodeToDelete->Right ;

	//調整父指針
	if(NewNode->Left)
	{
		NewNode->Left->Parent = NewNode;
	}
	if(NewNode->Right)
	{
		NewNode->Right->Parent = NewNode;
	}
	if(Py->Left)
	{
		Py->Left->Parent = Py;
	}
	if(Py->Right)
	{
		Py->Right ->Parent =Py;
	}
	if(NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = NULL;
	}
	return true;
}

template<class T> bool BlackRedTree<T>::LrOne_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	if(Py->Right->Left->Left!=NULL && Py->Right->Left->Left->Color == RED)
	{
		return LrOne_VLLr_AfterDelete(Py,DirectionOfY);
	}
	else
	{
		return LrOne_VLRr_AfterDelete(Py,DirectionOfY);
	}
}


template<class T> bool BlackRedTree<T>:: LrOne_VLRr_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode= new BlackRedNode<T>(Py->Data,BLACK);
	NodeToDelete = Py->Right->Left;

	NewNode->Left = Py->Left;
	NewNode->Right =NodeToDelete->Left;

	Py->Right->Left = NodeToDelete->Right;
	Py->Left = NewNode;

	Py->Data = NodeToDelete->Data;

	//調整父節點資訊
	if(Py->Right->Left)
	{
		Py->Right->Left->Parent =Py->Right;
	}
	if(Py->Left)
	{
		Py->Left->Parent = Py;
	}
	if(NewNode->Left)
	{
		NewNode->Left->Parent = NewNode;
	}
	if(NewNode->Right)
	{
		NewNode->Right->Parent = NewNode;
	}
	
	//調整顔色
	Py->Right->Left->Color = BLACK;

	if(NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = NULL;
	}
	return true;
}
template<class T> bool BlackRedTree<T>::LrOne_VLLr_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode= new BlackRedNode<T>(Py->Data,BLACK);
	NodeToDelete = Py->Right->Left->Left;

	NewNode->Left = Py->Left;
	NewNode->Right = NodeToDelete->Left;

	Py->Right->Left->Left = NodeToDelete->Right;
	
	Py->Left = NewNode;
	Py->Data = NodeToDelete->Data;

	//調整父節點資訊
	if(Py->Right->Left->Left)
	{
		Py->Right->Left->Left->Parent =Py->Right->Left;
	}
	if(Py->Left)
	{
		Py->Left->Parent = Py;
	}
	if(NewNode->Left)
	{
		NewNode->Left->Parent = NewNode;
	}
	if(NewNode->Right)
	{
		NewNode->Right->Parent = NewNode;
	}
	
	//調整顔色

	if(NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = NULL;
	}
	return true;
}

template<class T> bool BlackRedTree<T>::LrTwo_AfterDelete(BlackRedNode<T>* Py,int DirectionOfY)
{
	PRINTFUN();
	BlackRedNode<T>* NewNode,*NodeToDelete;
	NewNode= new BlackRedNode<T>(Py->Data,BLACK);
	NodeToDelete = Py->Right->Left->Left;

	NewNode->Left = Py->Left;
	NewNode->Right = NodeToDelete->Left;

	Py->Right->Left->Left = NodeToDelete->Right;
	
	Py->Left = NewNode;
	Py->Data = NodeToDelete->Data;

	//調整父節點資訊
	if(Py->Right->Left->Left)
	{
		Py->Right->Left->Left->Parent =Py->Right->Left;
	}
	if(Py->Left)
	{
		Py->Left->Parent = Py;
	}
	if(NewNode->Left)
	{
		NewNode->Left->Parent = NewNode;
	}
	if(NewNode->Right)
	{
		NewNode->Right->Parent = NewNode;
	}
	
	//調整顔色

	if(NodeToDelete)
	{
		delete NodeToDelete;
		NodeToDelete = NULL;
	}
	return true;
}

#endif

//practise.cpp

#include "BlackRedTree.h"

void main()
{
	BlackRedTree<int> Bl;
	int a[] = {1,2,3,4,5,6,7,8,9,10,11,12,14,90,88,60};
	for(int i= 0;i<sizeof(a)/sizeof(int);i++)
	{
		//cout<<"a[i]:"<<a[i]<<endl;
		cout<<"===================="<<endl;
		Bl.Insert(a[i]);
		
		
	}
	Bl.PrintTree();
	cout<<"輸入要删除的節點值"<<endl;

	int DelItem;
	cin >> DelItem;
	Bl.Delete(DelItem);
	Bl.PrintTree();

	return;
}
紅黑樹 插入 删除 資料結構 算法
上一篇: SpringBoot整合HttpClient
下一篇: Modelsim Se-64仿真帶ROM的Quartus II 13.1程式時，ROM資料異常解決辦法安裝缺失的convert_hex2ver.dll在Modelsim檢查ROM是否初始化成功

繼續閱讀