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

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

红黑树的插入操作和BST也差不多，同样在插入以后需要像AVL树那样向上调整，但是红黑树因为每个节点都存在parent指针，所以向上调整可以通过迭代来实现，而不需要像AVL树那样要用递归回溯。红黑树向上调整的过程实际上就是不断将新插入的红节点向上移动，直至它的父节点为黑为止，这样就存在三种情况（之所以不存在其他情况，完全是由于红黑树的性质决定的）。并且红黑树的根节点和根节点的父节点的Color一定是Black，所以这个向上调整的过程就一定会停止，也就是最终一定能跳出循环，在跳出循环之后需要将根节点的Color赋值为Black。以下三种情况均针对待调整节点在其祖父节点的左子树中时进行分析，若在右子树中时，做对称操作即可。

Case One

这种情况中,待调整节点是C节点，C节点的父节点B和父节点B的Sibling节点E的Color均为Red（需要注意的是这里C、D、E的左右子树可能为空，可能不为空，且A节点也可能不是根节点）。遇到这种情况时，将C节点的父节点B和父节点B的Sibling节点E的Color赋值为Black，并将C节点的祖父节点A赋值为Red，同时将待调整节点变为节点A。因为起初父节点的Color为Red，所以根据性质，C的祖父节点A的Color一定为Black，这样同时调整B和E为Black，可以使沿B和E至叶节点的路径上的Black节点数相同，且消除了B、C均为Red的情况，但是这样一来沿A至叶节点的路径上的Black节点数就增加了一个，因此将A赋值为Red，使得沿A至叶节点的路径上的Black节点数保持和调整前的数量一致，然而我们无法排除A的父节点的Color也是Red的情况，所以将待调整节点变为节点A，在下一次循环中继续调整。

Case Two

这种情况中，待调整节点是D节点，D节点的父节点B的Color是Red，但是父节点B的Sibling节点E的Color是Black，且D节点是其父节点B的右子节点。此时仅需要以B节点为Pivot做左旋即可，并将待调整节点变为B。在具体实现时还需要注意将记录父节点的变量FNode变为D节点，并进入Case Three。之所以要这样操作，是因为这里的操作仅仅针对两个Red节点，而对于Black节点的操作（例如C节点），起初沿B的左子节点、D的左（C节点）右子节点至叶节点的路径的Black节点数都是相同的，所以旋转操作中移动以C为根节点的子树后，沿B的子节点和D的子节点至叶节点的路径的Black节点数依然是相同的且保持不变。

Case Three

这种情况中，待调整节点是C节点，C节点的父节点B的Color是Red，但是父节点B的Sibling节点E的Color是Black，且C节点是其父节点B的左子节点。此时仅需要以C节点的祖父节点A作为Pivot做右旋即可，并将原先的父节点B的Color调整为Black，将原先的祖父节点A的Color调整为Red。之所以要这样操作，是因为起初沿C节点的左右子节点、沿D节点和E节点至叶节点的路径的Black节点数是相同的，所以在调整过后沿它们至叶节点的路径上的Black节点数依然是相同的且保持不变，而这样操作却可以通过交换颜色将一个Red节点移动到祖先节点的右子树中，消除了两个Red节点相连的情况，当然旋转后新的子树的根节点B要赋值为Black，以保持从子树的根节点（原先是A，现在是B）的路径的Black节点数保持和原来一样。这里要是Pivot是整棵红黑树的根节点，则需更新Root节点的值。

Source Code

PtrRBT RBInsert（PtrRBT T, ElementType Val）{PtrRBTNode TempNode = T->Root;PtrRBTNode NewNode = RBCreateNode（T, Val）;if（NULL == TempNode）{T->Root = NewNode;NewNode->Parent = T->NullNode;}else{while（T->NullNode ！= TempNode）{if（Val < TempNode->Key）{if（T->NullNode == TempNode->Left）{TempNode->Left = NewNode;NewNode->Parent = TempNode;break;}else{TempNode = TempNode->Left;}}else{if（T->NullNode == TempNode->Right）{TempNode->Right = NewNode;NewNode->Parent = TempNode;break;}else{TempNode = TempNode->Right;}}}}T = RBInsertFixUp（T, NewNode）;return T;}PtrRBT RBInsertFixUp（PtrRBT T, PtrRBTNode CurrentNode）{PtrRBTNode FNode, GNode, UNode;while（Red == CurrentNode->Parent->Color）{FNode = CurrentNode->Parent;GNode = FNode->Parent;if（GNode->Left == FNode）{UNode = GNode->Right;if（Red == FNode->Color&&Red == UNode->Color）{FNode->Color = UNode->Color = Black;GNode->Color = Red;CurrentNode = GNode;}else{if（CurrentNode == FNode->Right）{T = RBLeftRotate（T, FNode）;CurrentNode = FNode;FNode = CurrentNode->Parent;}FNode->Color = Black;GNode->Color = Red;T = RBRightRotate（T, GNode）;}}else{UNode = GNode->Left;if（Red == FNode->Color&&Red == UNode->Color）{FNode->Color = UNode->Color = Black;GNode->Color = Red;CurrentNode = GNode;}else{if（CurrentNode == FNode->Left）{T = RBRightRotate（T, FNode）;CurrentNode = FNode;FNode = CurrentNode->Parent;}FNode->Color = Black;GNode->Color = Red;T = RBLeftRotate（T, GNode）;}}}T->Root->Color = Black;return T;}

Delete

红黑树的删除和BST的删除也是类似的，区别在于红黑树删除后需要保持性质。这就同样需要在删除过后进行调整。而红黑树的删除主要是对于单支黑节点（即一个黑节点只有左子树或只有右子树）的操作。

因为删除红色叶节点对于红黑树的性质没有影响，删除黑色叶节点因为存在着sentinel节点，所以可以归入删除黑色internal节点的情况。
而对于删除internal节点，则分为左右子树均非空的节点，单支黑节点，单支红节点三种情况：

如果该internal节点左右子树均非空，则像BST那样在右子树中找中缀后继节点，用后继节点的值来替换待删除的internal节点的值，internal节点的其余成员值保持不变，就相当于删除了该节点，同时继续对后继节点进行删除操作，实际上就可以归入删除单支节点的情况；
如果该internal节点为单支红节点，则不论其子节点是红是黑，均不符合红黑树的性质，所以实际上并不存在此种情况；
如果该internal节点为单支黑节点，那么像BST那样将其子树接上，就相当于是删除了该节点。而这样一来，因为删除了一个黑节点，对于红黑树的第五个性质造成了破坏，这里就需要对红黑树进行调整。

因此实际上在具体实现中我们仅在被删除节点为黑节点时进行调整，所以在具体实现的PtrRBT RBDelete（PtrRBT T, ElementType Val）中，需要用一个临时变量DeleteNode来记录待删除节点，并在删除执行完之后判断待删除节点的颜色，以便确定是否需要调用PtrRBT RBDeleteFixUp（PtrRBT T, PtrRBTNode FixUpNode）函数进行调整：if（Black == DeleteNode->Color）{T = RBDeleteFixUp（T, FixUpNode）;}而以上所说的调整则是需要根据被删除的单支黑节点的子节点的Color来判断的。如果其子节点是黑色的，则有四种不同的情况，在RBDeleteFixUp函数的具体实现中需要进入一个while循环来处理，如果其子节点是红色的，则无需进入循环，直接执行循环后的FixUpNode->Color = Black;，就是将其子节点的Color变为黑色，相当于增加了一个黑节点来消除删除一个黑节点对红黑树性质的影响。对于四种不同情况，《算法导论》上介绍的很明白了，下面主要说明Case2、4的情况，并通过注释来介绍Case1、3和具体实现：当然需要特别注意的是，所谓的待调整节点其实就是沿待调整节点比沿待调整节点的Sibling节点至叶节点的Black节点数少1，所以在调整过程中我们只在待调整节点为黑且不为根节点时做调整，因为待调整节点为红时仅需将其置为黑既能保持红黑树性质，而待调整节点为根节点时相当于这一次删除最终使得整棵红黑树中根节点至叶节点的路径的Black节点数均减少1，但仍然符合红黑树性质。

Case Two

此情况下，不论祖父节点B是何种颜色，均将父节点的Sibling节点D颜色置为Red，这样可以使上图情况2中沿A节点和D节点至叶节点的路径具有相同的Black节点数，但是却使得图中沿B节点至叶节点的路径的Black节点数减少1，这样相当于B节点等价于一个待调整节点，因为待调整节点的一个特点就是沿待调整节点比沿待调整节点的Sibling节点至叶节点的Black节点数少1，因此将待调整节点变为B即可，并继续循环，若B为红则跳出循环后将其颜色置为黑，若B为黑则继续循环判断是Case1、2、3、4中的何种情况。更多详情见请继续阅读下一页的精彩内容： http://www.linuxidc.com/Linux/2017-01/139950p2.htm