紅黑樹原理詳解

1、紅黑樹原理詳解（上）前言:之所以要寫這篇文章，第一個目的是為了各位朋友在查看我寫的源代碼之前有一個 可以理解理論的文章因為紅黑樹還是有點難的，如果不想搞懂理論，而直接看代碼，那絕對是云里霧里，不知所云。第二個目的是我覺得網(wǎng) 上雖然后不少我文章也在講，但是我就是理解不上有點困難，在我參考了很多文章之后，認真閱讀才慢慢摸透了其中的原理，所以我想用 自己的方式來表達，希望有助于各位的朋友理解。你可以在這里獲得配套源代碼紅黑樹由來：他是在1972年由Rudolf Bayer 發(fā)明的，他稱之為“對稱二叉B樹”，它現(xiàn)代的名字是 Leo J. Guibas 和 Robert Sedgewick 于 1978

2、年寫的一篇論文中獲得的。它是復雜的，但它的操作有著良好的最壞情況運行時間，并且在實踐中是 高效的：它可以在O（log n）時間內(nèi)做查找，插入和刪除，這里的 n是樹中元素的數(shù)目。紅黑樹性質(zhì)：1. 每個結(jié)點或紅或黑。2. 根結(jié)點為黑色。3. 每 個葉結(jié)點（實際上就是NULL指針）都是黑色的。4. 如果一個結(jié)點是紅色的，那么它的周邊3個節(jié)點都是黑色的。5. 對于每個結(jié)點，從該結(jié)點到其所有子孫葉結(jié)點的路徑中所包含的黑色結(jié)點個數(shù)都一樣。討論的前提：1, 我們只討論往樹的左邊和從樹的左邊刪除的情況，與之對稱的情況一樣。2, 假設(shè)我們要刪除一個元素的方法都是采取刪除后繼節(jié)點，而非前驅(qū)節(jié)點。3, NL或全 黑

3、表示黑空節(jié)點，也可以不用畫出。4, “=>”這個符號 我們用來表示 變成”的意思。一. 插入當紅黑樹中沒有節(jié)點的時候，新節(jié)點直接涂黑就可以了。當樹中已有節(jié)點，我們就將新節(jié)點涂紅，并且底下掛兩個黑空節(jié)點。1.1新節(jié)點的父親為黑色這種情況最簡單，只接插入將新節(jié)點可以了，不會出現(xiàn)紅色警戒。1.2新節(jié)點的父親為紅色這種情況出現(xiàn)紅色警戒，并且通過紅色的父親，我們可以推出一定有一個黑色的父, 父親不可能為樹根（樹根必須為黑）。并且圖 1.2.1-1這種情況需要修復。1.2.1新 節(jié)點的叔叔是紅色。（紅叔）以此為新點, 繼續(xù)判定是否造成紅色警 戒將問題往 上推.如果祖 是樹根則直接深黑繼續(xù)判定基條將問

4、題往 上推0如果祖 是樹根則直接 涂里圖 1.2.1-2注解：在這種情況下，我們可以通過這樣的方式來修復紅黑樹的性質(zhì)。因為遇到紅色警戒所以我們首先可以想到的就是將父親變成黑色，但這樣祖父的左子樹的黑高就增加了，為了達到祖父的平衡，我們紅叔變成黑色，這樣祖父就平衡了。但是整 個祖父這顆樹的高度增高了，所以再此將祖父的顏色變成紅色來保持祖父這顆樹的方法：父=> 黑；叔=> 黑；祖=> 紅；往上遍歷;1.2.2新節(jié)點的叔叔是黑色（黑叔）圖 1.2.2-1圖 1.2.2-2變。因為祖父變成了紅色，因此往上遍歷。注解：首先可以說明的是，這種情況下我們都可以通過改變顏色和旋轉(zhuǎn)的方式到達平

5、衡，并且不再出現(xiàn)紅色警戒，因為無需往上遍歷。圖1.2.2-1 :首先我們將紅父變成 黑色，祖父變成紅色，然后對祖父進行右旋轉(zhuǎn)。這樣我們可以看到，整顆樹的黑高不變，并且這顆樹的左右子樹也達到平衡。新的樹根為黑色。因此無需往上遍歷。方法：圖1.2.2-1 父=> 黑；祖=> 紅；祖父右旋轉(zhuǎn)；圖1.2.2-2 新=> 黑；祖=> 紅；父左旋轉(zhuǎn)；祖右旋轉(zhuǎn)；插入我們就算做完了，與之對稱的右邊插入的情況完全一樣，請自己下來分析；一.刪除刪除是比較經(jīng)典但也是最困難的一件事了，所以我們必須一步一步地理解。為了中途思想不混亂，請始終記住一點，下面我們刪除的節(jié)點都已經(jīng)表示的是實際要刪除的后

6、繼節(jié)點 了。因此可以得出一下結(jié)論。首先，可以肯定的 是我們要刪除的節(jié)點 要么是紅色，要么是黑色。其次，既然我們要 刪除的結(jié)點是后繼節(jié)點，那么要刪除的節(jié)點的左子樹一定為空。所 以當刪除的節(jié)點為黑色時只剩下兩種情況。最后，如果刪除的 節(jié)點為紅色，那么它必為葉子節(jié)點。（自己好好想象為什么）。請在看下面的內(nèi)容前先牢記上面的結(jié)論，這樣更加方便讓你理解下面的知識。a：當刪除的節(jié)點為黑色時刪黑a刪黑bb：當刪除的節(jié)點為紅色時上面的幾附圖都是很簡單的。因為你可以將空節(jié)點 除的節(jié)點要么有一個右孩子，要么為葉子節(jié)點。去掉不看。所就形成了要刪下面我們就開始真正的刪除操作了2.1刪除紅色節(jié)點注解：這種情況是最簡單的，

7、因為根據(jù) 上面的結(jié)論 我們可以推出子節(jié)點一定為空，也就是說刪除的紅色節(jié)點為葉子節(jié)點。只需將這個舊節(jié)點的右孩子付給父親的左孩子就可以了，高度不變。 方法：略2.2刪除黑色節(jié)點遇到黑色節(jié)點情況就將變得復雜起來，因此我們一定要慢慢來，仔細分析。2.2.1當刪除的節(jié)點有一個紅色子孩子注解：這種情況其實就是上面我們分析的三種情況之一，如圖"刪黑b"。這種情 況是非常簡單的，只需將舊節(jié)點的右孩子取代舊節(jié)點，并將子孩子的顏色變?yōu)楹谏?，樹平衡；方法：子取代舊；子=> 黑；2.2.2當刪除的節(jié)點無左右孩子這種情況其實就是上面我們分析的三種情況之一，如圖"刪黑a"。我

8、 們推出子節(jié)點定為 空，請務(wù)必記住這點，不然在后面你將很容易被混淆，父親的顏色我們標記為綠色,是表示，父親的顏色可為紅或黑。黃色的子節(jié)點 后面分析。其實就是一個黑空節(jié)點，這樣方便其實這個子節(jié)JK 點一定是空葉a：紅兄注解：當我們刪除的節(jié)點擁有一個紅色的兄弟時，這種情況還相對比較簡單，因為兄弟為 黑色，我們可以推出父親一定為黑色。因為父節(jié)點的左樹高度減一，所以我們可以通過左旋轉(zhuǎn)父節(jié)點，來將節(jié)點1旋轉(zhuǎn)到左邊來恢復左邊的高度。然后將父變成紅，兄變成黑。這樣整顆樹的高度不變，父節(jié)點也平衡記住子節(jié)點羊為空所以可以刪除看，這樣便于理解。其實我們也可以推出1, 2為空，但這里沒有必要。方法：父=> 紅

9、；兄=> 黑；左旋轉(zhuǎn)父節(jié)點；紅黑樹原理詳解（下）b :黑兄遇到黑兄就又麻煩了，我們又必須引入要刪除的節(jié)點的侄子了。所以我們這里再次細分為b1:黑兄雙黑侄b2:黑兄左黑侄右紅侄 b3:黑兄右黑侄左紅侄。 可能你會問b4 呢，雙紅侄的情況呢？其實雙紅侄的情況同屬于b2,b3的 情況，所以 可以默認用b2,b3其中一種情況來處理就可以了。 現(xiàn)在我們開始了bl 黑兄雙黑侄注解：我們首先可以肯定的是父節(jié)點的左子樹高度減一了，所以我們必須想方設(shè)法來彌補 這個缺陷。如果我們把父節(jié)點的右子樹高度也減一（兄變成紅色）那么父節(jié)點這 顆樹就可以保持平衡了，但整顆樹的高度減一，所以我們可以判斷，如果父親是紅色，

10、那么我們可以通過把父親變成黑色來彌補這一缺陷。但如果父親是 黑色呢，既然遇到到黑色了我們就只好往上遍歷了。方法：兄=> 紅；子=黑；紅父=> 黑；往上遍歷（黑父）;補充：其實子節(jié)點就是空節(jié)點，沒有必要變。就算遍歷上去，父節(jié)點也為黑b2黑兄左黑侄右紅侄注解：綠色表示，顏色不影響修復的方式。依然我們可以肯定父節(jié)點的左子樹高度減一，所以我們可以通過將父節(jié)點旋轉(zhuǎn)下來并且變?yōu)楹谏珌韽浹a，但由丁兄弟被旋 轉(zhuǎn)上去了， 乂導致右子樹高度減一，但我們這有一個紅侄，所以可以通過紅子侄變成黑色來彌補。父親所在位置的顏色不變；（子為空）方法：兄=父色；父=黑；侄=黑；（子=黑）；左旋轉(zhuǎn)父節(jié)點；b3黑兄左紅

11、侄右黑侄注解：綠色表示，顏色不影響修復的方式。依然我們可以肯定父節(jié)點的左子樹高 度減一，同樣我們通過父節(jié)點左旋轉(zhuǎn)到左子樹來彌補這一缺陷。但如果直接旋轉(zhuǎn)的 話，我們可以推出左右子樹將不平衡（黑父），或者兩個紅色節(jié)點相遇（紅父）；這 樣將會更加的復雜，甚至不可行。因此，我們考慮首先將兄弟所在子樹右旋轉(zhuǎn)， 然 后再左旋轉(zhuǎn)父子樹。這樣我們就可以得到旋轉(zhuǎn)后的樹。然后通過修改顏色來使其 達到平衡，且高度不變。方法：侄=父色；父=黑；右旋轉(zhuǎn)兄；左旋轉(zhuǎn)父；總結(jié):如果我們通過上面的情況畫出所有的分支圖，我們可以得出如下結(jié)論插入操作：解決的是紅-紅問題刪除操作：解決的是黑-黑問題即你可以從分支圖中看出，需要往上遍

12、歷的情況為紅紅 （插入）；或者為黑黑黑（刪除）的情 況，如果你認真分析并總結(jié)所有的情況后， 并堅持下來，紅黑樹也就沒 有想象中的那么恐怖了, 并且很美妙；程序樣列:surit ch (uncle->calor) case REDt /*參考圖1.2. 1-2還有一種未畫出的情況 這種情況部分叔與父的位置關(guān)系*/(sub root p)->color 二 BLACK :/* 父=>黑 */uncle->color = BLACK:/* 叔=黑 */?rand->color = RED：/*祖=>紅 汶種情況會往上遍歷*/break:case BLACK: /*

13、 參考圖 1. 2, 2-2 */if (grand->right = uncle) V* 叔在右1 邊 */(*sub_root_p)->right->color = BLACK ; /* S=>® */Stnd->coLor = RED;/*父左放轉(zhuǎn)#/rotat eleft(sub_roat_p):if Cgrand->parent = BNULL)/* 祖父 有旅轉(zhuǎn) */rot at e_right(r ont_p):elffe if(g rand->parent->left - gtand)rotatU (grand->

14、parent->left:elserotate_right U(grand->parent->right):felse(/* I叔在左別，未畫出*/(*sub_roct_p)->color = BLACK :/* 父二黑 */srnd->color = RED；/* 祖=，紅 */if (grand->prent = BNULL)/* | 祖父左旋轉(zhuǎn) #/rot at e_left froot_p):else if(grand->parent->left - grand)rot at(應(yīng)(grand->parenf ->left):elserot at e left (grand->parent-bright)5 :break;break;點擊這里下載源碼聲明：此文檔為C語言常用數(shù)據(jù)結(jié)構(gòu)源代碼全注解-紅黑樹源碼所寫，此文檔遵循GNU FDL協(xié)議，你可以修改重發(fā)，但因保留原