红黑树的旋转、查找和删除（附源代码）

Red Black Tree Basic

红黑树的节点声明，其中Parent指针是指向某一节点的父节点的指针：

typedef struct TreeNode *PtrRBTNode; typedef struct TreeNode RBTNode; struct TreeNode{ ElementType Key; ColorType Color; PtrRBTNode Left; PtrRBTNode Right; PtrRBTNode Parent; };

红黑树的总体声明，该声明中包含了指向红黑树根节点的指针和指向用作sentinel的dummy node的指针：

typedef struct Tree *PtrRBT; struct Tree{ PtrRBTNode Root; PtrRBTNode NullNode; };

一些其他的相关函数：

PtrRBT RBInit(PtrRBT T){ T = (PtrRBT)malloc(sizeof(struct Tree)); T->Root = NULL; T->NullNode = (PtrRBTNode)malloc(sizeof(RBTNode)); T->NullNode->Key = -1; T->NullNode->Color = Black; T->NullNode->Left = T->NullNode->Right = T->NullNode->Parent = NULL; return T; } PtrRBTNode RBCreateNode(PtrRBT T, ElementType Val){ PtrRBTNode NewNode = (PtrRBTNode)malloc(sizeof(RBTNode)); NewNode->Key = Val; NewNode->Color = Red; NewNode->Left = NewNode->Right = T->NullNode; return NewNode; } PtrRBTNode RBSearch(PtrRBT T, ElementType Val){ PtrRBTNode TempNode = T->Root; if(NULL == TempNode){ return NULL; } while(T->NullNode != TempNode){ if(TempNode->Key > Val){ TempNode = TempNode->Left; } else if(TempNode->Key < Val){ TempNode = TempNode->Right; } else{ return TempNode; } } return NULL; } PtrRBTNode RBFindSuccessor(PtrRBT T, PtrRBTNode Root){ while(T->NullNode != Root->Left){ Root = Root->Left; } return Root; }

Rotate

红黑树的旋转操作和AVL树的旋转操作差不多，但是还是有几个需要特别注意的地方。

首先，应当注意红黑树的每个节点都有Parent指针，在旋转操作时不能遗漏对于Parent指针的操作。

第二，对于某一节点中Parent指针的操作需要访问该节点，这时就应当注意该节点是否为NULL节点。例如下图中的C节点就可能为NULL节点，如果不是NULL节点，在旋转时要将C的Parent指针指向B。当然在处理NULL节点时，我们可以利用一个dummy node来作为一个sentinel，所有的叶节点的Left和Right指针都指向这个sentinel，而根节点的Parent指针也指向sentinel，sentinel的Color为Black，其余成员值为任意。

第三，在旋转时应该注意根节点。当旋转的Pivot节点就是根节点时，应当注意更改struct Tree结构中的Root指针，将其指向新的根节点。当旋转的Pivot节点不是根节点时，应当注意更改Pivot的父节点的Left或Right指针，这里就需要加以分类讨论（到底新的根节点，如上图中的D节点，是其父节点的左子树还是右子树），可以利用Pivot->Parent来访问Pivot的父节点。

Source Code

PtrRBT RBLeftRotate(PtrRBT T, PtrRBTNode Pivot){ PtrRBTNode TempNode = Pivot->Right; Pivot->Right = TempNode->Left; if(T->NullNode != TempNode->Left){ TempNode->Left->Parent = Pivot; } TempNode->Left = Pivot; TempNode->Parent = Pivot->Parent; if(T->Root == Pivot){ T->Root = TempNode; } else{ if(Pivot == Pivot->Parent->Left){ Pivot->Parent->Left = TempNode; } else{ Pivot->Parent->Right = TempNode; } } Pivot->Parent = TempNode; return T; } PtrRBT RBRightRotate(PtrRBT T, PtrRBTNode Pivot){ PtrRBTNode TempNode = Pivot->Left; Pivot->Left = TempNode->Right; if(T->NullNode != TempNode->Right){ TempNode->Right->Parent = Pivot; } TempNode->Right = Pivot; TempNode->Parent = Pivot->Parent; if(T->Root == Pivot){ T->Root = TempNode; } else{ if(Pivot == Pivot->Parent->Left){ Pivot->Parent->Left = TempNode; } else{ Pivot->Parent->Right = TempNode; } } Pivot->Parent = TempNode; return T; }

Insert