紅黑樹—Red Black Tree

紅黑樹是具有以下五條性質的二叉查找樹：

1. 每個結點要麼是紅的要麼是黑的。  
2. 根結點是黑的。  
3. 每個葉結點（葉結點即指樹尾端NIL指針或NULL結點）都是黑的。  
4. 如果一個結點是紅的，那麼它的兩個兒子都是黑的。  
5.  對于任意結點而言，其到葉結點樹尾端NIL指針的每條路徑都包含相同數目的黑結點。 

正是由于紅黑樹的以上五個性質，使得其高度最多是2log(N+1)，進而保證紅黑樹的查找、插入、删除的時間複雜度最壞為O(log n)。具體關于紅黑樹的基本介紹，以及插入操作，和删除操作的算法的具體分析可參考博文：教你透徹了解紅黑樹（其結構之法、算法之道系列文章整體不錯，可以多多參考學習）。 在插入、删除過程中最關鍵的就是時刻保證RBT的五個性質。

以下主要給出RBT的插入算法的具體實作，删除操作目前還沒徹底弄清楚，後續再補充。其中的左旋轉，右旋轉，以及雙旋轉操作與平衡二叉樹中的操作一樣，

具體見：平衡二叉樹（AVLTree）。

插入操作：首先按查找二叉樹的方法找到正确的插入位置，并将新節點X設為紅色。則主要分為以下4中情況：

1、其父節點P為黑色，則直接插入，完成。

2、其父節點P為紅色（則祖父節點GP一定為黑色），X為P（GP的左節點，為右節點時，對稱情況）的左子節點（為右節點時，對稱情況），其叔父節點S（即      GP的       右節點）為黑色，則執行一次左單旋轉即可。 （對稱情況執行一次右單旋轉）。

3、其父節點P為紅色（則祖父節點GP一定為黑色），X為P（GP的左節點，為右節點時，對稱情況）的右子節點（為左節點時，對稱情況），其叔父節點S（即      GP的       右節點）為黑色，則執行一次雙旋轉即可。 （對稱情況類似執行一次雙旋轉）。

4、其父節點P為紅色（則祖父節點GP一定為黑色），其叔父節點S為紅色。 這種情況相對較為複雜。基本思路是，在插入新節點的自頂向下周遊過程中，将遇到的所有         雙紅兒子節點（其父節點一定為黑）的情況進行顔色翻轉，即将父節點設為紅，兩兒子改為黑，進而将第4種情況轉化為2或3的情況。

具體代碼如下：

<span style="font-size:18px;">typedef enum ColorType {Red,Black} ColorType;
typedef int ElementType;
typedef struct RedBlackNode* RedBlackTree;
typedef struct RedBlackTree Position;


//節點
struct RedBlackNode
{
 ElementType Element;//節點value值
 RedBlackTree Left;//節點左指針
 RedBlackTree Right;//節點右指針
 ColorType Color;//節點顔色
 
};

/*旋轉處理函數
根據需要進行單旋轉（雙旋轉由兩次單旋轉完成）
參數：
Item:新節點value值
Parent：插入新節點後的曾祖父節點
傳回值：
旋轉後的新樹根（新節點的祖父節點）指針
*/
static Position Rotate(ElementType Item,Position Parent)
{
 if(Item<Parent->Element)
	return  Parent->Left=Item<Parent->Left->Element?
		SingleRotateWithLeft(Parent->Left)://“一”形
		SingleRotateWithRight(Parent->Left);//“之”形
 else
	return Parent->Right=Item>Parent->Right->Element?
		SingleRotateWithRight(Parent->Right)://“一”形
		SingleRotateWithLeft(Parent->Right);//“之”形
}

static Position X,P,GP,GGP;


/*樹形調整函數*/
static void HandleRrorient(ElementType Item,RedBlackTree T)
{
 //在自頂向下周遊時遇到雙子節點均為紅時，執行顔色翻轉
 X->Color=Red;
 X->Left->Color=Black;
 X->Right->Color=Black;
 
  if(P->Color==Red)//當父節點需要執行旋轉操作
  {
    GP->Color=Red;
	if(Item<P->Element != P->Element<GP->Element)//為”之“形，需要執行雙旋轉
		P=Rotate(Item,GP);//對X和P執行一次單旋轉(雙旋轉的第一次單旋轉)
	X=Rotate(Item,GGP);//為”一“形，旋轉後X為新子樹的樹根
	X->Color=Black；//確定樹根為黑色
  }

}

RedBlackTree Insert(ElementType Item ,RedBlackTree T)
{
 X=P=GP=GGP=T;
 /*Position NullNode=malloc(sizeof(struct RedBlackNode));
 NullNode->Left=Right=NULL;
 NullNode->Color=Red;
 */
 NullNode->Element=Item;
 while(X->Element!=Item && 	X!=NullNode)//自定向下周遊，并處理雙紅兒子節點，以及帶來的旋轉操作
 {
  GGP=GP;GP=P;P=X;
  if(X<X->Element)
	X=X->Left;
  else
	X=X->Right;
	if(X->Left->Color==Red && X->Right->Color==Red)//雙紅兒子節點
		 HandleRrorient(Item,T);
 }

 if(X!=NullNode)//原來一存在該值的節點
	return NullNode；
	
 X=malloc(sizeof(struct RedBlackNode));
 if(X=NULL)
   printf("Out of space \n");
 X->Element=Item;
 X->Left=X->Right=NullNode;
 
 //将新節點插入到樹葉
 if(Item<P->Element)
	P->Left=X;
 else 
   P->Right=X;
 //最後插入節點後可能使得不滿足紅黑樹的性質，是以需要最後一次調整（因為已不存在其叔父節點為紅的情況，是以隻需要進行一次單或者雙旋轉即可）
  HandleRrorient(Item,T);
  
  return T;
}
</span>