第十三章 紅黑樹
總結：這章介紹了紅黑樹的性質、旋轉，並詳細介紹了紅黑樹的插入和刪除。
1. 紅黑樹的性質
1） 每個節點或是紅的，或是黑的
2） 根節點是黑的
3） 每個葉節點（NIL）是黑的
4） 如果一個節點是紅的，則它的兩個兒子都是黑的
5） 對每個節點，從該節點到其子孫節點的所有路徑上包含相同數目的黑節點。
黑高度：從某個節點x出發到大一個葉節點的任意一條路徑上，黑色節點的個數稱為該節點的黑高度，用bh(x)表示。
紅黑樹是一種好的二叉查找樹，對一棵有n個內節點的紅黑樹的高度至多為2lg(n+1)，STL中的set和map就是用紅黑樹實現的。
紅黑樹的動態集合操作SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR與二叉查找樹的對應操作的實現一樣，且它們的時間復雜度都是O(lgn)
2. 旋轉
復雜度O(1)
左旋：
偽代碼
LEFT-ROTATE(T,x)
y <- right[x]
if left[y]!=NIL[T]
then p[left[y]] <- x
right[x] <- left[y]
p[y] <- p[x]
if p[x]=NIL[T]
then root[T] <- y
else if x=left[p[x]]
then left[p[x]] <- y
else right[p[x]] <- y
p[x] <- y
left[y] <- x
右旋：
偽代碼
RIGHT-ROTATE(T,y)
x <- left[y]
left[y] <- right[x]
if right[x]!=NIL[T]
p[right[x]] <- y
p[x] <- p[y]
if p[y]=NIL[T]
then root[T] <- x
else if y=left[p[y]]
then left[p[y]] <- x
else right[p[y]] <- x
p[y] <- x
right[x] <- y
3. 插入
時間復雜度O(lgn)
插入操作類似二叉查找樹的插入，然後將插入的節點的顏色設為RED，由於插入操作可能破壞紅黑樹的性質2（當插入的是根節點時）和性質4（當父節點為紅色節點時），因此需要額外的RB-INSERT-FIXUP操作來進行紅黑樹性質的保持。
偽代碼
RB-INSERT(T,z)
y <- NIL[T]
x <- root[T]
while x!=NIL[T]
do y <- x
if key[z] < key[x]
then x <- left[x]
else x <- right[x]
p[z] <- y
if y=NIL[T]
then root[T] <- z
else if key[z] < left[y]
then left[y] <- z
else right[y] <- z
left[z] <- NIL[T]
right[z] <- NIL[T]
color[z] <- RED
RB-INSERT-FIXUP(T,z)
分情況討論RB-INSERT-FIXUP：
首先，如果紅黑樹的性質2遭到破壞，那麼只要簡單的將根節點改為黑色即可。
其次，如果紅黑樹的性質4遭到破壞，即插入節點的父節點也為紅節點，那麼該節點一定有祖父節點，否則就不滿足性質2，且該節點的祖父節點一定為黑色，否則不滿足性質4。
設插入節點是z
這裡有兩組可能性，一是p[z]是p[p[z]]的左兒子，二是p[z]是p[p[z]]的右兒子。每組情況中又有三種子情況。僅討論第一組情況。
在第一組條件下，又有三種情況：
Case1: z的叔父節點（即p[p[z]]的右兒子）的顏色為紅色，則將z的父節點及z的叔父節點的顏色改為黑色，將z的祖父節點的顏色改為紅色，然後將z上升至祖父節點，繼續循環，保持紅黑樹的性質。
Case2: z的叔父節點的顏色為黑色，且z是p[z]的右兒子。對於這種情況，我們將Case2變為Case3，然後再處理Case3即可，即將z變為p[z]的左兒子。這可以通過將以p[z]為根的子樹進行左旋，然後z指向原來的p[z]，這樣情況變為Case3。
Case3: 將p[p[z]]設為紅色，將p[z]設為黑色，然後對以p[p[z]]為根的子樹進行右旋。
偽代碼
RB-INSERT-FIXUP(T,z)
while color[p[z]]=RED
do if p[z]=left[p[p[z]]]
then y <- right[p[p[z]]]
if color[y]=RED
then color[y] <- BLACK
color[p[z]] <- BLACK
color[p[p[z]]] <- RED
z <- p[p[z]]
else
then if z=right[p[z]]
then z <- p[z]
LEFT-ROTATE(T,z)
color[p[z]] <- BLACK
color[p[p[z]]] <- RED
RIGHT-ROTATE(T,p[p[z]])
else (same as then clause with “right” and “left” exchanged)
color[root[T]] <- BLACK
4. 刪除
時間復雜度O(lgn)
紅黑樹的刪除操作類似二叉查找樹的刪除操作，但是當刪除的節點是黑色節點時，性質2（刪除的是根節點，且一個紅色孩子成為了新的根節點）、性質4（刪除節點的父節點和孩子節點都為紅色）、性質5（顯然刪除一個黑節點後，性質5無法滿足）可能遭到破壞。因此，需要額外的RB-DELETE-FIXUP操作來進行紅黑樹性質的保持。
偽代碼
RB-DELETE(T,z)
if left[z]=NIL[T] or right[z]=NIL[T]
then y <- z
else y <- TREE-SUCCESSOR(z)
if left[y]!=NIL[T]
then x <- left[y]
else x <- right[y]
p[x] <- p[y]
if p[x]=NIL[T]
then root[T] <- x
else if y=left[p[y]]
then left[p[y]] <- x
else right[p[y]] <- x
if y!=z
then key[z] <- key[y]
if color[y]=BLACK
then RB-DELETE-FIXUP(T,x)
return y
這裡，x為y刪除後替換上去的一個節點。如果x為紅色的話，那麼只要將x變為黑色即可。
但是如果x為黑色的話，情況就復雜了。仍然有兩組情況，一是x為p[x]的左兒子，一是x為p[x]的右兒子。僅討論x是p[x]左兒子的情況。
設w為x的兄弟節點，即w為p[x]的右兒子，且w一定不是nil[T]，否則原來的紅黑樹中不滿足性質5。
分四種情況討論：
Case1： w是紅色的。這種情況下，p[x]一定為黑色的。w的左右兒子一定是黑色的，將Case1轉換為Case2的情況，對以p[x]為根的樹進行左旋，將p[x]設為紅色，原來的w設為黑色，則紅黑性質保持，且問題轉換為Case2,3,或4。
Case2: w是黑色的，如果w的兩個兒子都是黑色的，那麼將w改為紅色，那麼從p[x]出發經過左兒子到葉子節點的路徑上與經過右兒子到葉子節點的路徑上的黑色節點個數相同了（因為刪去y後，左邊的路徑上的黑節點少掉了一個，而把w的顏色改掉後，右邊的路徑上的黑節點也少了一個，因此數量仍舊相等），但是對p[p[x]]而言，經過p[x]的路徑上的黑色節點的個數少了一個，又必須重新保持紅黑樹性質。因此，此時x新指向p[x]，並重新循環。這種情況簡單的說，就是左邊少了個黑色，所以右邊也減去個黑色的，然後整體就少了個黑色的，因此循環下去。
Case3: w是黑色的，w的左兒子是紅色的，右兒子是黑色的。對以w為根的樹進行右旋，將left[w]設為黑色的，w設為紅色，新的w指向原來的left[w]，問題轉變為Case4。
Case4：w是黑色的，w的右兒子是紅色的。通過改變一些節點的顏色，並執行一次左旋，可以將x的額外的黑色去除。這種情況就是左邊少了個黑色的，然後往左邊又加個黑色的。
偽代碼
RB-DELETE-FIXUP(T,z)
while x!=root[T] and color[x]=BLACK
do if x=left[p[x]]
then w <- right[p[x]]
if color[w]=RED
then color[w] <- BLACK
color[p[x]] <- RED
LEFT-ROTATE(T,p[x])
w <- right[p[x]]
if color[left[w]]=BLACK and color[right[w]]=BLACK
then color[w] <- RED
x <- p[x]
else
then if color[right[w]]=BLACK
then color[left[w]] <- BLACK
color[w] <- RED
RIGHT-ROTATE(T,w)
w <- right[p[x]]
color[w] <- color[p[x]]
color[p[x]] <- BLACK
color[right[w]] <- BLACK
LEFT-ROTATE(T,p[x])
x <- root[T]
else (same as then clause with “right” and “left” exchanged)
color[x] <- BLACK
附錄：
C++代碼
#includeusing namespace std; typedef enum col{RED, BLACK} col; template class RBNode { public: RBNode(T k, RBNode *l=NULL, RBNode *r=NULL, RBNode *p=NULL ):key(k),left(l),right(r),parent(p){} ~RBNode(); T key; RBNode *left, *right, *parent; col color; }; template class RBTree { public: RBTree(RBNode *r=NULL):root(r){ NIL=new RBNode (-1); NIL->color=BLACK; root->color=BLACK; root->left=NIL; root->right=NIL; root->parent=NIL; } ~RBTree(); void inorder(RBNode *); RBNode * search(T k, RBNode *x); RBNode * min(RBNode *x); RBNode * max(RBNode *x); RBNode * successor(RBNode *x); void rightRotate(RBNode *z); void leftRotate(RBNode *z); void Insert(RBNode *z); void Insert_fixup(RBNode *x); void Delete(RBNode *z); void Delete_fixup(RBNode *x); RBNode *root; RBNode *NIL; }; template void RBTree ::inorder(RBNode *x) { if(x==NIL) return; inorder(x->left); cout << x->key << " "; inorder(x->right); } template RBNode * RBTree ::search(T k, RBNode *x) { RBNode *p=x; while(p!=NIL && p->key!=k) { if(k < (p->key)) p=p->left; else p=p->right; } return p; } template RBNode * RBTree ::min(RBNode *x) { RBNode *p=x; if(p==NIL) return NIL; while(p->left!=NIL) p=p->left; return p; } template RBNode * RBTree ::max(RBNode *x) { RBNode *p=x; if(p==NIL) return NIL; while(p->right!=NIL) p=p->right; return p; } template RBNode * RBTree ::successor(RBNode *x) { if(x->right!=NIL) return min(x->right); RBNode *y=x; RBNode *p=x->parent; while(p!=NIL && p->right==y) { y=p; p=p->parent; } return p; } template void RBTree ::leftRotate(RBNode *z) { RBNode *y=z->right; if(y->left!=NIL) y->left->parent=z; y->parent=z->parent; if(y->parent==NIL) root=y; else if(z==z->parent->left) z->parent->left=y; else z->parent->right=y; z->right=y->left; z->parent=y; y->left=z; } template void RBTree ::rightRotate(RBNode *z) { RBNode *y=z->left; y->parent=z->parent; if(y->parent==NIL) root=y; else if(z==z->parent->left) z->parent->left=y; else z->parent->right=y; if(y->right!=NIL) y->right->parent=z; z->left=y->right; y->right=z; z->parent=y; } template void RBTree ::Insert(RBNode *z) { RBNode *y=root; RBNode *x; while(y!=NIL) { x=y; if(z->key < y->key) y=y->left; else y=y->right; } z->parent=x; if(x==NIL) root=z; else if(z->key < x->key) x->left=z; else x->right=z; z->color=RED; z->left=NIL; z->right=NIL; Insert_fixup(z); } template void RBTree ::Insert_fixup(RBNode *z) { RBNode *x=z; RBNode *w; while(x->parent->color==RED) { if(x->parent==x->parent->parent->left) { w=x->parent->parent->right; if(w->color==RED) { w->color=BLACK; x->parent->color=BLACK; x->parent->parent->color=RED; x=x->parent->parent; } else { if(x==x->parent->right) { x=x->parent; leftRotate(x); } x->parent->color=BLACK; x->parent->parent->color=RED; rightRotate(x->parent->parent); } } else { w=x->parent->parent->left; if(w->color==RED) { w->color=BLACK; x->parent->color=BLACK; x->parent->parent->color=RED; x=x->parent->parent; } else { if(x==x->parent->left) { x=x->parent; rightRotate(x); } x->parent->color=BLACK; x->parent->parent->color=RED; leftRotate(x->parent->parent); } } } root->color=BLACK; } template void RBTree ::Delete(RBNode *z) { RBNode *y; RBNode *x; if(z->left==NIL || z->right==NIL) y=z; else y=successor(z); if(y->left!=NIL) x=y->left; else x=y->right; x->parent=y->parent; if(y->parent==NIL) root=x; else if(y==y->parent->left) y->parent->left=x; else y->parent->right=x; if(y!=z) z->key=y->key; if(y->color==BLACK) Delete_fixup(x); } template void RBTree ::Delete_fixup(RBNode *z) { RBNode *x=z; RBNode *w; while(x->color==BLACK && x!=root) { if(x==x->parent->left) { w=x->parent->right; if(w->color==RED) { w->color=BLACK; x->parent->color=RED; leftRotate(x->parent); w=x->parent->right; } if(w->left->color==BLACK && w->right->color==BLACK) { w->color=RED; x=x->parent; } else { if(w->right->color==BLACK) { w->color=RED; w->left->color=BLACK; w=w->left; rightRotate(w->parent); } w->right->color=BLACK; w->color=w->parent->color; x->parent->color=BLACK; leftRotate(x->parent); x=root; } } else { w=x->parent->left; if(w->color==RED) { w->color=BLACK; x->parent->color=RED; rightRotate(x->parent); w=x->parent->left; } if(w->left->color==BLACK && w->right->color==BLACK) { w->color=RED; x=x->parent; } else { if(w->left->color==BLACK) { w->color=RED; w->right->color=BLACK; w=w->right; leftRotate(w->parent); } w->left->color=BLACK; w->color=w->parent->color; x->parent->color=BLACK; rightRotate(x->parent); x=root; } } } x->color=BLACK; } int main() { RBNode * a1=new RBNode (6); RBNode * a2=new RBNode (5); RBNode * a3=new RBNode (4); RBNode * a4=new RBNode (3); RBNode * a5=new RBNode (2); RBNode * a6=new RBNode (1); RBTree *T=new RBTree (a1); T->inorder(T->root); cout << endl; T->Insert(a2); T->Insert(a3); T->Insert(a4); T->Insert(a5); T->Insert(a6); RBNode *p=T->search(4,T->root); T->Delete(p); T->inorder(T->root); cout << endl; T->Delete(a6); T->Delete(a5); T->Delete(a4); T->Delete(a2); T->inorder(T->root); cout << endl; T->Delete(a1); T->inorder(T->root); }
