2019獨角獸企業(yè)重金招聘Python工程師標準>>>

簡單介紹

紅黑樹（RB-Tree）是根據(jù)節(jié)點顏色來調(diào)整的近平衡二叉樹，也是查找樹(中序遍歷從大到小)的一種，沒有平衡二叉樹那么嚴格，但是性能與其差不多。

紅黑樹的5個性質(zhì)：

每個結(jié)點要么是紅的要么是黑的。 ?

根結(jié)點是黑的。 ?

每個葉結(jié)點（葉結(jié)點即指樹尾端NIL指針或NULL結(jié)點）都是黑的。 ?

如果一個結(jié)點是紅的，那么它的兩個兒子都是黑的。 ?

對于任意結(jié)點而言，其到葉結(jié)點樹尾端NIL指針的每條路徑都包含相同數(shù)目的黑結(jié)點。

?

正是紅黑樹的這5條性質(zhì)，使一棵n個結(jié)點的紅黑樹始終保持了logn的高度（紅黑樹的高度至多為2log(n+1)證明略），從而也就解釋了上面所說的“紅黑樹的查找、插入、刪除的時間復(fù)雜度最壞為O(log?n)”這一結(jié)論成立的原因。?

此圖忽略了葉子和根部的父結(jié)點。同時，上文中我們所說的 "葉結(jié)點" 或"NULL結(jié)點"，如上圖所示，它不包含數(shù)據(jù)而只充當(dāng)樹在此結(jié)束的指示，這些節(jié)點在繪圖中經(jīng)常被省略，望看到此文后的讀者朋友注意。

約定：

要插入的節(jié)點為，N
父親節(jié)點，P
祖父節(jié)點，G
叔叔節(jié)點，U
兄弟節(jié)點，S

紅黑樹的插入

（1）情形1: 新節(jié)點N位于樹的根上，沒有父節(jié)點

當(dāng)前節(jié)點為根節(jié)點，必為黑色

void insert_case1(node n) {
???? if (n->parent == NULL)
???????? n->color = BLACK;
???? else
???????? insert_case2(n);
?}

（2）情形2:?新節(jié)點的父節(jié)點P是黑色

插入后仍為紅黑樹，無須變

void insert_case2(node n) {
???? if (n->parent->color == BLACK)
???????? return; /* 樹仍舊有效 */
???? else
???????? insert_case3(n);
?}

（3）情形3:父節(jié)點P、叔叔節(jié)點U，都為紅色

此時父結(jié)點的父結(jié)點一定存在，否則插入前就已不是紅黑樹。與此同時，又分為父結(jié)點是祖父結(jié)點的左孩子還是右孩子，根據(jù)對稱性，我們只要解開一個方向就可以了。這里只考慮父結(jié)點為祖父左孩子的情況，如下圖所示。

?

對此，我們的解決策略是：將當(dāng)前節(jié)點的父節(jié)點和叔叔節(jié)點涂黑，祖父結(jié)點涂紅，把當(dāng)前結(jié)點指向祖父節(jié)點，從新的當(dāng)前節(jié)點重新開始算法。即如下代碼所示：

void insert_case3(node n) {
???? if (uncle(n) != NULL && uncle(n)->color == RED) {
???????? n->parent->color = BLACK;
???????? uncle(n)->color = BLACK;
???????? grandparent(n)->color = RED;
???????? insert_case1(grandparent(n));?? //因為祖父節(jié)點可能是紅色的，違反性質(zhì)4，遞歸情形1.
???? }
???? else
???????? insert_case4(n);?? //否則，叔叔是黑色的，轉(zhuǎn)到下述情形4處理。

此時新插入節(jié)點N做為P的左子節(jié)點或右子節(jié)點都屬于上述情形3,上圖僅顯示N做為P左子的情形

（4）情形4: 父節(jié)點P是紅色，叔叔節(jié)點U是黑色或NIL，且當(dāng)前節(jié)點、父節(jié)點、祖父節(jié)點不在一條線

當(dāng)前節(jié)點的父節(jié)點是紅色,叔叔節(jié)點是黑色，

1）當(dāng)前節(jié)點是其父節(jié)點的右子且其父節(jié)點是祖父的左邊子，，則左旋

2）當(dāng)前節(jié)點是其父節(jié)點的左子且其父節(jié)點是祖父的右邊子，，則右轉(zhuǎn)

最終的目的是想當(dāng)前節(jié)點、父節(jié)點、祖父節(jié)點在用一條直線上，列舉上面1）中的情況變化前后比較

紅黑樹變之前的：

?

變化成：

轉(zhuǎn)為一條線上后可進行情形5操作，具體代碼如下：

void insert_case4(node n) {
???? if (n == n->parent->right && n->parent == grandparent(n)->left) {
???????? rotate_left(n->parent);
???????? n = n->left;
???? } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
???????? rotate_right(n->parent);
???????? n = n->right;
???? }
???? insert_case5(n);??? //轉(zhuǎn)到下述情形5處理。

（5）情形5: 父節(jié)點P是紅色，叔叔節(jié)點U是黑色或NIL，且當(dāng)前節(jié)點、父節(jié)點、祖父節(jié)點在一條線

解決對策是：父節(jié)點變?yōu)楹谏?#xff0c;祖父節(jié)點變?yōu)榧t色，在祖父節(jié)點為支點右旋或左旋，具體是當(dāng)前節(jié)點、父親、祖父所在直線往左，則右旋，反之亦然。

所以紅黑樹由之前的：

變化成：

具體代碼為：

void insert_case5(node n) {
???? n->parent->color = BLACK;
???? grandparent(n)->color = RED;
???? if (n == n->parent->left && n->parent == grandparent(n)->left) {
???????? rotate_right(grandparent(n));
???? } else {
???????? /* 反情況，N 是其父節(jié)點的右孩子，而父節(jié)點P又是其父G的右孩子 */
???????? rotate_left(grandparent(n));
???? }
?}

參考算法導(dǎo)論第三版13.3-2題目：41、38、31、12、19、8依次插入為空的紅黑樹

更多從無到有構(gòu)建實例可以參考http://blog.csdn.net/jimoshuicao/article/details/8618043

紅黑樹的刪除

"我們刪除的節(jié)點的方法與常規(guī)二叉搜索樹中刪除節(jié)點的方法是一樣的，如果被刪除的節(jié)點不是有雙非空子女，則直接刪除這個節(jié)點，用它的唯一子節(jié)點頂替它的位置，如果它的子節(jié)點分是空節(jié)點，那就用空節(jié)點頂替它的位置，如果它的雙子全為非空，我們就把它的直接后繼節(jié)點內(nèi)容復(fù)制到它的位置，之后以同樣的方式刪除它的后繼節(jié)點，它的后繼節(jié)點不可能是雙子非空，因此此傳遞過程最多只進行一次?！?/p>

二叉查找樹的刪除

繼續(xù)講解之前，補充說明下二叉樹結(jié)點刪除的幾種情況，待刪除的節(jié)點按照兒子的個數(shù)可以分為三種：

沒有兒子，即為葉結(jié)點。直接把父結(jié)點的對應(yīng)兒子指針設(shè)為NULL，刪除兒子結(jié)點就OK了。

只有一個兒子。那么把父結(jié)點的相應(yīng)兒子指針指向兒子的獨生子，刪除兒子結(jié)點也OK了。

有兩個兒子。這是最麻煩的情況，因為你刪除節(jié)點之后，還要保證滿足搜索二叉樹的結(jié)構(gòu)。其實也比較容易，我們可以選擇左兒子中的最大元素或者右兒子中的最小元素放到待刪除節(jié)點的位置，就可以保證結(jié)構(gòu)的不變。當(dāng)然，你要記得調(diào)整子樹，畢竟又出現(xiàn)了節(jié)點刪除。習(xí)慣上大家選擇左兒子中的最大元素，其實選擇右兒子的最小元素也一樣，沒有任何差別，只是人們習(xí)慣從左向右。這里咱們也選擇左兒子的最大元素，將它放到待刪結(jié)點的位置。左兒子的最大元素其實很好找，只要順著左兒子不斷的去搜索右子樹就可以了，直到找到一個沒有右子樹的結(jié)點。那就是最大的了

“在刪除節(jié)點后，原紅黑樹的性質(zhì)可能被改變，如果刪除的是紅色節(jié)點，那么原紅黑樹的性質(zhì)依舊保持，此時不用做修正操作，如果刪除的節(jié)點是黑色節(jié)點，原紅黑樹的性質(zhì)可能會被改變，我們要對其做修正操作。那么哪些樹的性質(zhì)會發(fā)生變化呢，如果刪除節(jié)點不是樹唯一節(jié)點，那么刪除節(jié)點的那一個支的到各葉節(jié)點的黑色節(jié)點數(shù)會發(fā)生變化，此時性質(zhì)5被破壞。如果被刪節(jié)點的唯一非空子節(jié)點是紅色，而被刪節(jié)點的父節(jié)點也是紅色，那么性質(zhì)4被破壞。如果被刪節(jié)點是根節(jié)點，而它的唯一非空子節(jié)點是紅色，則刪除后新根節(jié)點將變成紅色，違背性質(zhì)2?！?/p>

“上面的修復(fù)情況看起來有些復(fù)雜，下面我們用一個分析技巧：我們從被刪節(jié)點后來頂替它的那個節(jié)點開始調(diào)整，并認為它有額外的一重黑色。這里額外一重黑色是什么意思呢，我們不是把紅黑樹的節(jié)點加上除紅與黑的另一種顏色，這里只是一種假設(shè)，我們認為我們當(dāng)前指向它，因此空有額外一種黑色，可以認為它的黑色是從它的父節(jié)點被刪除后繼承給它的，它現(xiàn)在可以容納兩種顏色，如果它原來是紅色，那么現(xiàn)在是紅+黑，如果原來是黑色，那么它現(xiàn)在的顏色是黑+黑。有了這重額外的黑色，原紅黑樹性質(zhì)5就能保持不變?，F(xiàn)在只要恢復(fù)其它性質(zhì)就可以了，做法還是盡量向根移動和窮舉所有可能性。"--saturnman。

如果是以下情況，恢復(fù)比較簡單：

????a)當(dāng)前節(jié)點是紅+黑色

????????????解法，直接把當(dāng)前節(jié)點染成黑色，結(jié)束此時紅黑樹性質(zhì)全部恢復(fù)。

????b)當(dāng)前節(jié)點是黑+黑且是根節(jié)點，

????????????解法：什么都不做，結(jié)束。

????c)但如果是以下情況呢？：

• 刪除修復(fù)情況1：當(dāng)前節(jié)點是黑+黑且兄弟節(jié)點為紅色(此時父節(jié)點和兄弟節(jié)點的子節(jié)點分為黑)
• 刪除修復(fù)情況2：當(dāng)前節(jié)點是黑加黑且兄弟是黑色且兄弟節(jié)點的兩個子節(jié)點全為黑色
• 刪除修復(fù)情況3：當(dāng)前節(jié)點顏色是黑+黑，兄弟節(jié)點是黑色，兄弟的左子是紅色，右子是黑色
• 刪除修復(fù)情況4：當(dāng)前節(jié)點顏色是黑-黑色，它的兄弟節(jié)點是黑色，但是兄弟節(jié)點的右子是紅色，兄弟節(jié)點左子的顏色任意

下面，咱們便來分別來處理所有的刪除修復(fù)情況。

（1）情況1:?N 是新的根。

void delete_case1(struct node *n)
{
??????? if (n->parent != NULL)
??????????????? delete_case2(n);
}

（2）情形2：兄弟節(jié)點S是紅色

解法：把父節(jié)點染成紅色，把兄弟結(jié)點染成黑色，之后重新進入算法（我們只討論當(dāng)前節(jié)點是其父節(jié)點左孩子時的情況）。此變換后原紅黑樹性質(zhì)5不變，而把問題轉(zhuǎn)化為兄弟節(jié)點為黑色的情況(注：變化前，原本就未違反性質(zhì)5，只是為了把問題轉(zhuǎn)化為兄弟節(jié)點為黑色的情況)。 即如下代碼操作

void delete_case2(struct node *n)
{
??????? struct node *s = sibling(n);
?
??????? if (s->color == RED) {
??????????????? n->parent->color = RED;
??????????????? s->color = BLACK;
??????????????? if (n == n->parent->left)
??????????????????????? rotate_left(n->parent);? //左旋
??????????????? else
??????????????????????? rotate_right(n->parent);
??????? }?
??????? delete_case3(n);
}

變化前：

?

變化后：?

?

情況 3: 兄弟節(jié)點S是黑色的，且S的倆個兒子都是黑色的。但N的父節(jié)點P，是黑色。

解法：把當(dāng)前節(jié)點和兄弟節(jié)點中抽取一重黑色追加到父節(jié)點上，把父節(jié)點當(dāng)成新的當(dāng)前節(jié)點，重新進入算法。（此變換后性質(zhì)5不變），
void delete_case3(struct node *n)
{
??????? struct node *s = sibling(n);
?
??????? if ((n->parent->color == BLACK) &&
??????????? (s->color == BLACK) &&
??????????? (s->left->color == BLACK) &&
??????????? (s->right->color == BLACK)) {
??????????????? s->color = RED;
??????????????? delete_case1(n->parent);
??????? } else
??????????????? delete_case4(n);
}

?

情況4:?兄弟節(jié)點S 是黑色的、S 的兒子也都是黑色的，但是 N 的父親P，是紅色。

[還是對應(yīng)我第二篇文章中，情況2：x的兄弟w是黑色的，且w的倆個孩子都是黑色的。
(這里，父節(jié)點P為紅)]
void delete_case4(struct node *n)
{
??????? struct node *s = sibling(n);
?
??????? if ((n->parent->color == RED) &&
??????????? (s->color == BLACK) &&
??????????? (s->left->color == BLACK) &&
??????????? (s->right->color == BLACK)) {
??????????????? s->color = RED;
??????????????? n->parent->color = BLACK;
??????? } else
??????????????? delete_case5(n);
}

情況5:?兄弟S為黑色，S 的左兒子是紅色，S 的右兒子是黑色，而N是它父親的左兒子。

//此種情況，最后轉(zhuǎn)化到下面的情況6。
[對應(yīng)我第二篇文章中，情況3：x的兄弟w是黑色的，w的左孩子是紅色，w的右孩子是黑色。]
void delete_case5(struct node *n)
{
??????? struct node *s = sibling(n);
?
??????? if? (s->color == BLACK)?
??????????????? if ((n == n->parent->left) &&
??????????????????? (s->right->color == BLACK) &&
??????????????????? (s->left->color == RED)) {?
??????????????????????? // this last test is trivial too due to cases 2-4.
??????????????????????? s->color = RED;
??????????????????????? s->left->color = BLACK;
??????????????????????? rotate_right(s);
??????????????? } else if ((n == n->parent->right) &&
?????????????????????????? (s->left->color == BLACK) &&
?????????????????????????? (s->right->color == RED)) {
?????????????????????? // this last test is trivial too due to cases 2-4.
??????????????????????? s->color = RED;
??????????????????????? s->right->color = BLACK;
??????????????????????? rotate_left(s);
??????????????? }
??????? }
??????? delete_case6(n);? //轉(zhuǎn)到情況6。

?

情況6:?兄弟節(jié)點S是黑色，S的右兒子是紅色，而 N 是它父親的左兒子。

[對應(yīng)我第二篇文章中，情況4:x的兄弟w是黑色的，且w的右孩子時紅色的。]
void delete_case6(struct node *n)
{
??????? struct node *s = sibling(n);
?
??????? s->color = n->parent->color;
??????? n->parent->color = BLACK;
?
??????? if (n == n->parent->left) {
??????????????? s->right->color = BLACK;
??????????????? rotate_left(n->parent);
??????? } else {
??????????????? s->left->color = BLACK;
??????????????? rotate_right(n->parent);
??????? }
}

?

紅黑樹的插入、刪除情況時間復(fù)雜度的分析

因為每一個紅黑樹也是一個特化的二叉查找樹，
因此紅黑樹上的只讀操作與普通二叉查找樹上的只讀操作相同。
然而，在紅黑樹上進行插入操作和刪除操作會導(dǎo)致不再符合紅黑樹的性質(zhì)。

恢復(fù)紅黑樹的屬性需要少量(O(log n))的顏色變更(實際是非?？焖俚?和
不超過三次樹旋轉(zhuǎn)(對于插入操作是兩次)。
雖然插入和刪除很復(fù)雜，但操作時間仍可以保持為 O(log n) 次。

ok，完。

后記：
此紅黑樹系列，前前后后，已經(jīng)寫了4篇文章，如果讀者讀完了這4篇文章，
對紅黑樹有一個相對之前來說，比較透徹的理解，
那么，也不枉費，我花這么多篇幅、花好幾個鐘頭去畫紅黑樹了。

真正理解一個數(shù)據(jù)結(jié)構(gòu)、算法，最緊要的還是真正待用、實踐的時候體會。
歡迎，各位，將現(xiàn)在、或以后學(xué)習(xí)、工作中運用此紅黑樹結(jié)構(gòu)、算法的經(jīng)驗與我分享。
謝謝。:D。

?

參考文獻：

第一篇：教你透徹了解紅黑樹：
http://blog.csdn.net/v_JULY_v/archive/2010/12/29/6105630.aspx
第二篇：紅黑樹算法的層層剖析與逐步實現(xiàn)
http://blog.csdn.net/v_JULY_v/archive/2010/12/31/6109153.aspx
第三篇：教你徹底實現(xiàn)紅黑樹：紅黑樹的c源碼實現(xiàn)與剖析
http://blog.csdn.net/v_JULY_v/archive/2011/01/03/6114226.aspx

第四篇：一步一圖一代碼，一定要讓你真正徹底明白紅黑樹

一步一圖一代碼，一定要讓你真正徹底明白紅黑樹

?

轉(zhuǎn)載于:https://my.oschina.net/zlb1992/blog/869447

總結(jié)

以上是生活随笔為你收集整理的红黑树及其操作的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。