歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

紅黑樹的原理分析和算法設計

紅黑樹是60年代中期計算機科學界找尋一種算法復雜度穩定,容易實現的數據存儲算法的產物。在優先級隊列、字典等實用領域都有廣泛地應用,更是70年代提出的關系數據庫模型--B樹的鼻祖。在Linux kernel中,高精度定時器也工作在紅黑樹之上。為便於初學者掌握其基本算法,本文一步一步地演示了紅黑樹的創建過程。

首先回顧一下紅黑樹的基本性質:

1. 紅黑樹本質上是一個二叉查找樹(BST),但是它從根到最遠葉子的長度不會超過到最近葉子長度的兩倍,因此是近似平衡的。

2. 紅黑樹的節點不是黑的就是紅的,不會有第三種顏色。

3. 樹根必須是黑色。

4. 葉子所指的空節點必須是黑色。

5. 如果某個節點是紅色,那麼它的兩個兒子必須都是黑色。

6. 從任意節點出發的所有向下的路徑上包含相同個數的黑節點。這個個數我們稱為黑高度Bh。

有了上面的認識,我們要從無到有構造一顆紅黑樹的話,心裡就有底了。這個構造的過程可以分兩步:

第一步:執行BST的插入算法;

第二步:對節點著色;

第一步不會有什麼問題,關鍵是第二步怎麼對節點著色才不會違反紅黑樹的基本性質;

這是一個難點,我在寫這篇文章的時候腦子也卡了一下,節點不多的時候好辦,但是如果節點很多了,就必須找到一種普遍適用的算法來處理。通過這兩天的觀察,我發現這六條性質中最關鍵的其實是最後一條---從任意結點出發的任意路徑黑高度相等!這才是紅黑樹算法保持近似平衡的精華所在!其它性質要麼是這條性質的產物,要麼就是為這條性質服務的。

現在我演示一下怎麼從無到有生成一棵紅黑樹。

例如我們有一組數:{9,7,15,6,11,19},現在按照從左到右的順序存放在一顆紅黑樹中。

第一個數是9,很自然地成為了樹根,如圖:

圖-1

每個新節點都默認地被渲染成了紅色,為什麼要這麼做呢?後面我們將會看到它的好處!現在先忽略不談。

根節點9是紅色,這違背了性質3,所以必須改成黑色,如圖:

圖-2

下一個數字是7,顯然要被插入到9的左邊,並且這時滿足紅黑樹的所有性質,如圖:

圖-3

下一個數字是15,要插入到9的右邊,並且也滿足紅黑樹的所有性質,如圖:

圖-4

下一個數字是6,要插入到7的左邊,這回似乎有麻煩了,性質5被違背了,如圖:

圖-5

可能有人會說,那很簡單,既然違背了性質5,那我改一下6的顏色不就OK了?

圖-6

現在,恭喜你---也走進了我曾經走過的誤區:)你的無意之舉改變了新增節點路徑上面的黑高度,這棵樹已經不是紅黑樹了!

寫代碼的人都知道,對樹的遍歷,最簡單的方法就是遞歸,那麼樹的數學模型就是一個可窮舉的遞歸式。遞歸式中每一步的正確性都建立在前一步正確的基礎之上。現在我們回過頭來想想為什麼每次插入的新節點都被渲染成紅色呢?你肯定猜到了,因為我們要保證紅黑樹的核心性質--黑高度不發生變化,雖然犧牲了性質5,但這是可以補救的,並且代價很小。再來看看圖-5

既然我們不能通過改變新插入節點的顏色來維持紅黑樹的性質,那麼就只好從原來的樹結構入手了。

我們注意到新插入的節點的父親是一個紅節點,其叔叔也是一個紅節點。那麼假如我把它的父親改成黑色,則恢復了性質5,可是從樹根出發的黑高度還是不相等,干脆把它的叔叔也改成黑色吧!結果如下:

圖-7

現在它滿足紅黑樹所有的性質。好了,我們繼續。

插入數字11和19的過程平淡無奇,不深入探討,最終的樹如圖:

圖-8

如果現在要插入數字10怎麼辦?它肯定會是11的左節點:

圖-9

明顯違背了性質5!難道依葫蘆畫瓢,把11和19都改成黑色?這樣從樹根出發的左邊路徑黑高度還是2,而右邊兩條路徑的黑高度將變成了3,老辦法失效了!

圖-10

其實不然,改了新增節點的父親和叔叔的顏色以後,右邊路徑黑高度全加一,但我們只要把它的爺爺改成紅色不就又減去了多出來的黑高度嗎?

圖-11

如果你認真看到這裡,我想你的潛意識一定告訴你---這裡存在某種規律等著我們去發現。

讓我們再仔細審視一下圖-5

在生成樹的過程中,我們已經兩次遇到類似情況了,歸納一下,這個場景就是:新節點的父親是紅色,叔叔也是紅色。

至於別的節點,我們大可不必關心,因為很顯然,這個場景是原子的。

我們的處理辦法是把7和15渲染成黑色,就像圖-7那樣,可是因為這是一個普遍適用的場景,所以要做一個擴展:假設在這個原子樹的每個節點上還有別的分支。那麼圖-7就不能保證所有路徑的黑高度相等了,即使把9改成紅色也無濟於事,因為9也許還有父節點,所以也許它的父節點又是紅色,這就再次違反了性質5。我最喜歡的作家之一--柯南.道爾,曾說過:“歷史就像車輪的輻條,每一根都終將再次轉回來。”眼前的場景正是如此---我們設計的原子場景再次出現。

一個清晰的遞歸算法呈現在我們面前:

1. 新增節點渲染成紅色;

2. 如果它的父親是紅色,則違反了性質5;

3. 如果它的叔叔也是紅色,則通過同時修改其父親和叔叔的顏色為黑色來恢復性質5;

4. 如果它的爺爺不是根節點,則有可能在另外的路徑上再次違反性質5,於是我們把它的爺爺改成紅色;

5. 可是如果他的太爺爺也是紅色呢?很自然地,我們重新回到步驟2;

6. 不斷循環,直到第二步滿足就可以結束。

最後留給感興趣的同學兩個問題:

1. 如果新增節點的父親是紅色,但它的叔叔是黑色,該怎麼辦?(提示:使用旋轉)

2. 有人說,下面這種場景,我設計的算法就失效了,真的嗎?(粉色的6是新插入的節點)

Linux內核之於紅黑樹and AVL樹  http://www.linuxidc.com/Linux/2015-07/119425.htm

AVL樹 VS 紅黑樹  http://www.linuxidc.com/Linux/2014-04/99736.htm

紅黑樹插入操作的C++實現  http://www.linuxidc.com/Linux/2012-11/74483.htm

Copyright © Linux教程網 All Rights Reserved