# 紅黑樹 ????? 紅黑樹是很多平衡樹的一種，保證最壞情況下基本動態幾何操作時間復雜度為O(log(n)) **1、紅黑樹性質** (1)???每個節點是紅色的，或者是黑色的 (2)???根節點是黑色的 (3)???每個葉節點(nil)是黑色的 (4)???如果一個節點是黑色的，則它的連個子節點都是黑色的 (5)???對每個節點，從該節點到其后代葉節點的簡單路徑上，均包含相同數目的黑色節點  **2、旋轉** ????? 旋轉是保持二叉搜索樹局部性質的操作，包括左旋和右旋。當在節點x上做左旋時，假設它的右孩子為y而不是T.nil，X可為其右孩子不是T.nil的任何節點，同理，X做右旋也是一樣的。  ** ** **偽代碼如下(左旋)**  **旋轉代碼(左旋-C)** ~~~ static void left_rotate(rbTree *T, rbtreeNode * x) { rbtreeNode *y = x->right; x->right = y->left; if(y->left != T->nil) y->left->p = x; y->p = x->p; if(x->p == T->nil) T->root = y; else if(x == x->p->left) x->p->left = y; else x->p->right = y; y->left = x; x->p = y; } ~~~ 3、插入 ? ? ? ?在O(log(n))時間內插入一個節點，RB-INSERT過程完成該操作，像一個普通的二叉搜索樹一樣，然后將要插入的節點Z著為紅色。為了保持紅黑樹的性質，調用一個輔助函數RB-INSERT-FIXUP來對節點從新著色并旋轉。待插入節點Z已保存了數據項。 **RB-INSERT過程偽代碼**  ** ** **RB-INSERT-FIXUP過程偽代碼**   **注意：**Case1屬于if判斷條件中，Case2和Case3輸入else語句中的，Case2是else語句中的if判斷語句的。具體可以看代碼 **RB-INSERT代碼實現(C)** ~~~ int rbtree_insert(rbTree *T, DataTypedef num) { rbtreeNode *y = T->nil; rbtreeNode *x = T->root; rbtreeNode *z = NULL; if(!rbtree_in(T, num)) { z = (rbtreeNode *)malloc(sizeof(rbtreeNode)); if(z == NULL) err_sys("no space for z in rbtree"); z->data = num; } else return ERR; while(x != T->nil) //y is parent point of x { y = x; if(z->data < x->data) x = x->left; else x = x->right; } z->p = y; if(y == T->nil) T->root = z; else if(z->data < y->data) y->left = z; else y->right = z; z->left = T->nil; z->right = T->nil; z->color = RED; if( rbtree_fixup(T, z) ) return OK; else return ERR; } ~~~ **RB-INSERT-FIXUP過程分析** 第1-15行的while循環在每次迭代的開始始終保持以下3個條件是不變的 (1)???節點z是紅節點 (2)???如果z.p是根節點，則z.p是黑節點 (3)???如果有任何紅黑樹性質貝破壞，則至多有一條被破壞，或是性質2，或是性質4(各個性質見紅黑樹性質總結)。如果性質2被破壞，則因為z是根節點且是紅節點。性質4被破壞則是因為z和z.p都是紅節點。 **循環終止條件：** ? ? ?循環終止因為z.p是黑色的(如果z是根節點，則z.p是黑色哨兵節點)，這樣，在循環終止時并沒有違反性質4，唯一可能不成立的就是性質2，不過第16行恢復了這個性質。 **循環保持條件：** ????? 循環保持有6中條件，其中3種和另外3種是對稱的，這取決于z的父節點z.p是z的祖父節點z.p.p的左孩子還是右孩子。情況1、2、3的區別就在于z的父節點的兄弟節點(z的叔節點)的顏色不同，加入y指向z的叔節點，如果y的顏色是紅色的，則執行情況1，否則轉向情況2和3。在所有的3種情況中，z的祖父節點z.p.p是黑色的，因為他的父節點z.p是紅色的，故性質4只有在z和z.p之間被破壞了。  **情況1：z的叔節點y是紅色的** ????? 此時對應Case1，將z.p和y都著成黑色，解決z和z.p都是紅色的問題，將z.p.p著成紅色保持性質5，然后把z.p.p作為新節點z來繼續進行while循環，指針z上移兩層  **情況2：z的叔節點y是黑色的且z是一個右孩子** **情況3：z的叔節點y是黑色的且z是一個左孩子** ????? 兩種情況中，y都是黑色的，通過z是左孩子還是右孩子來區分，情況2中可以通過一個左旋來轉化為情況3，此時z為左孩子。因為z和z.p都是紅節點，對黑高(從某個節點出發，不含該節點，到達一個葉節點的任意一條簡答路徑上的黑色節點數為該節點的黑高)和性質5都無影響。在情況3中，改變某些節點顏色并做一次右旋，保持性質5，這樣不在有兩個紅色節點相鄰，處理完畢，此時z.p是黑色的，所以無需再執行while循環了。  **RB-INSERT-FIXUP代碼實現(C)** ~~~ static int rbtree_fixup(rbTree *T, rbtreeNode *z) { rbtreeNode *y = NULL; /* * while循環在每次迭代的開頭都保持3個部分的不變式 * 1 節點z是紅色節點 * 2 如果z.p是根節點，則z.p是黑節點 * 3 如果有任何紅黑性質被破壞，則至多只有一條被破壞，或是性質2(根為黑色節點)，或是性質4(如果一個節點是紅色的， * 則它的兩個子節點都是黑色的) */ while(z->p->color == RED) { if(z->p == z->p->p->left)//在所有的情況中，z的祖父節點z.p.p是黑色的，以為z.p是紅色的 { y = z->p->p->right; // Case1: z uncle node y is red if(y->color == RED) { z->p->color = BLACK; y->color = BLACK; z->p->p->color = RED; z = z->p->p; } else { // Case2: z uncle node y is black, but z is right node if(z == z->p->right) { z = z->p; left_rotate(T, z); } // Case3: z uncle node y is black, but z is left node z->p->color = BLACK; z->p->p->color = RED; right_rotate(T, z->p->p); } } else { y = z->p->p->left; if(y->color == RED) { z->p->color = BLACK; y->color = BLACK; z->p->p->color = RED; z = z->p->p; } else { if(z == z->p->left) { z = z->p; right_rotate(T, z); } z->p->color = BLACK; z->p->p->color = RED; left_rotate(T, z->p->p); } } } T->root->color = BLACK; return OK; } ~~~ **4、刪除** ????? 刪除操作與插入操作相比，略顯復雜，與插入操作一樣，也要花費O(log(n))時間。 從紅黑樹中刪除節點，需設計一個供TREE-DELETE調用的子過程TRANSPLANT，并應用到紅黑樹中，TRANSPLANT過程用來調整兩個節點的關系，其中的一個節點要替換掉另一個節點 **TRANSPLANT過程** ????? u節點表示將要被替換掉的節點，v節點是準備替換u節點的  **RB-TRANSPLANT代碼實現(C)** ~~~ static void rbtree_transplant(rbTree *T, rbtreeNode *u, rbtreeNode *v) { if(u->p == T->nil) { T->root = v; } else if(u == u->p->left) { u->p->left = v; } else { u->p->right = v; } v->p = u->p; } ~~~ **RB-DELETE過程** ????? RB-DELETE中，z節點是要被刪除的節點，其中記錄了節點y的蹤跡，y有可能導致紅黑樹性質破壞，當想刪除節點z，且z的子節點少于2個時，z從書中刪除，并讓y稱為z。當z有兩個子節點時，y應該是z的后繼，并且將y移到z的位置。在節點被刪除或者移動時，必須記住y的顏色，并且記錄節點x的蹤跡，將x移到y的原來的位置，因為節點x可能引起紅黑樹性質破壞。刪除節點z后，RB-DELETE-FIXUP過程通過改變顏色和執行旋轉來恢復紅黑樹性質。  ? ? ?我們保存節點x的蹤跡，使它移至節點y的原來位置。第4、7和11行的賦值語句令x或指向y的唯一子節點或指向y哨兵T.nil(y沒有子節點的話)。 ????? 第5、8或14行調用RB-TRANSPLANT時，傳遞的第2個參數與x相同 ? ???如果y是黑色的，則有可能引入一個或多個破壞紅黑色的情況，所以在第22行調用RB-TRANSPLANT來恢復紅黑樹性質。如果y是紅色的，當y被刪除或移動時，紅黑樹性質依然成立，因為(1) 樹中黑高沒有變化 (2) 不存在兩個相鄰的紅節點，因為y在樹中占據了z的位置，z的位置肯定不會違反紅黑樹性質的。另外，如果y是z的右孩子，則y的原右孩子x代替y，如果y是紅色的，則x一定是黑色的，一次用x替代y不會使兩個紅節點相鄰。 (3) 如果y是紅色的，就不會是根節點，所以根節點仍然是黑色的。 **y為黑節點情況分析**  **RB-DELETE代碼實現(C)** ~~~ void rbtree_delete(rbTree *T, DataTypedef data) { rbtreeNode *z = rbtree_find(T, data); rbtreeNode *y; rbtreeNode *x; enum ColorTypedef y_oldcolor; if(z == T->nil) { printf("the rbtree hasn't %d\n", data); return; } y = z; y_oldcolor = y->color; if(z->left == T->nil) { x = z->right; rbtree_transplant(T, z, z->right); } else if(z->right == T->nil) { x = z->left; rbtree_transplant(T, z, z->left); } else { y = rbtree_findmin(T, z->right); y_oldcolor = y->color; x = y->right; if(y->p == z) { x->p = y; } else { rbtree_transplant(T, y, y->right); y->right = z->right; y->right->p = y; } rbtree_transplant(T, z, y); y->left = z->left; y->left->p = y; y->color = z->color; } if(y_oldcolor == BLACK) rbtree_delete_fixup(T, x); free(z); //printf("free the node is ok\n\n"); } ~~~ RB-DELETE-FIXUP過程  ps：圖片上的情況層次關系對應不是很齊，可以看碼來的清楚 **4中情況的轉換關系** 1 -> 2、3、4 2 -> 1、2、3、4、修復 (只有Case2是節點上移，所有有可能會使x=root) 3 -> 4 4 -> 修復 無論哪個Case，要么是為了到達平衡兩個節點，路徑上黑色數目相同的目的，要么是通過變形間接達到這個目的。 while循環的目標是將額外的黑色沿樹上移，直到： (1)???x指向紅黑節點，此時在第23行處將x著為(單個)黑色 (2)???x指向根節點，此時可以簡單地移除額外的黑色 (3)???執行適當的旋轉和重新著色  **代碼中的4種情況圖示** **** ? ???上圖給出了代碼中出現的四種情況，再具體研究每一個情況時，先看看如何證實每種情況中的變換保證性質5。關鍵思想是在每種情況下，從子樹的跟(包括跟)到每棵子樹之間的黑色節點個數(包括x的額外黑色)并不被變換改變，因此，如果性質5在變換之前成立，則在變換之后也成立。比如：在情況1中，在變換前后，根節點到子樹a或b之間的黑色節點數是3(因為x增加了一層黑色)，類似的，在變換前后根節點到其余的4個子樹的葉節點中的任何一個的黑節點數是2。在圖13-7(b)中，計數是還要包括所示子樹的根節點的color屬性的值，它是RED或是BLACK，如果定義count(RED)=0以及count(BLACK)=1，那么變換前后根節點至a的黑節點都為2+count(c)。在此情況下，變換之后新節點x具有color屬性的c，但是這個節點的顏色是紅黑(如果c=RED)或者雙重黑色的(如果c=BLACK)。其他情況可以類似加以驗證。 **情況1：x的兄弟節點w是紅色的** ????? 情況1(見RB-DELETE-FIXUP的第5-8行和圖13-7(a))發生在節點x的兄弟節點w為紅色時。因為w必須有黑色子節點，所有可以改變w的x.p的顏色，然后對x.p做一次左旋而不違反紅黑樹的任何性質。現在x的新兄弟節點是旋轉之前w的某個子節點，其顏色為黑色。這樣，就將情況1轉變為了情況2、3或者4。 ????? 當節點w為黑色時，屬于情況2、3或者4；這些情況有w的子節點顏色來區分了。 **情況2：x的兄弟節點w是黑色的，而且w的兩個子節點都是黑色的** ????? 在情況2(見RB-DELETE-FIXUP的第10-11行和圖13-7(b))，w的兩個子節點都是黑色的，因為w也是黑色的，所以從x和w上去掉一重黑色，使得x只有一重黑色而w為紅色。為了補償從x和w中去掉的一重黑色，在原來是紅色或黑色的x.p上增加一重額外的黑色。通過將x.p作為新節點x來重復while循環。注意到，如果通過情況1進入到情況2，則新節點x就是紅黑色的，因為原來的x.p是紅色的，因此，新節點x的color屬性值為RED，并且在測試循環條件后循環終止。然后，在第23行處將新節點x著為(單一)黑色。 **情況3：x的兄弟節點w是黑色的，w的左孩子是紅色的，w的右孩子是黑色的** ????? 情況3(見RB-DELETE-FIXUP的第13-16行和圖13-7(c))發生在w為黑色且其左孩子為紅色，右孩子為黑色時。可以交換w和其左孩子w.left的顏色，然后對w進行右旋而不違反紅黑樹的性質。現在x的新節點w是一個有紅色右孩子的黑色節點，這樣我們就從情況3轉換成了情況4。 **情況4：x的兄弟節點w是黑色的，且w的右孩子是紅色的** ????? 情況4(見RB-DELETE-FIXUP的第17-21行和圖13-7(d))發生在節點x的兄弟節點w為黑色且w的右孩子為紅色時，通過進行某些顏色修改并對x.p做一次左旋，可以去掉x的額外黑色，從而使它變為單重黑色，而且不破壞紅黑樹性質。將x設為設為根root后，當while循環測試其循環條件時，循環終止。 **RB-DELETE-FIXUP代碼實現(C)** ~~~ static void rbtree_delete_fixup(rbTree *T, rbtreeNode *x) { rbtreeNode *w; while(x != T->root && x->color == BLACK)//while循環中，x總是指向一個具有雙重黑色的非根界節點 { if(x == x->p->left) { w = x->p->right; if(w->color == RED) //情況1：x的兄弟節點w是紅色 { w->color = BLACK; x->p->color = RED; left_rotate(T, x->p); w = x->p->right; } if(w->left->color == BLACK && w->right->color == BLACK) //情況2:x的兄弟節點w是黑色，而且w的兩個子節點都是黑色的 { w->color = RED; x = x->p; } else { if(w->right->color == BLACK) //情況3：x的兄弟節點w是黑色的，w的左孩子是紅色的，w的右孩子是黑色的 { w->left->color = BLACK; w->color = RED; right_rotate(T, w); w = x->p->right; } w->color = x->p->color; //情況4：x的兄弟節點w是黑色的，且w的右孩子是紅色的 x->p->color = BLACK; w->right->color = BLACK; left_rotate(T, x->p); x = T->root; } } else//x = x->p->right { w = x->p->left; if(w->color == RED) { w->color = BLACK; x->p->color = RED; right_rotate(T, x->p); w = x->p->left; } if(w->left->color == BLACK && w->right->color == BLACK) { w->color = RED; x = x->p; } else { if(w->left->color == BLACK) { w->right->color = BLACK; w->color = RED; left_rotate(T, w); w = x->p->left; } w->color = x->p->color; x->p->color = BLACK; w->left->color = BLACK; right_rotate(T, x->p); x = T->root; } } } x->color = BLACK; } ~~~ **刪除分析：**  參考資料： 1、《算法導論》第13章 紅黑樹 2、《數據結構與算法分析基礎》-C語言描述 3、完整的工程代碼實現見：[http://download.csdn.net/detail/u012796139/8673483](http://download.csdn.net/detail/u012796139/8673483)