71
技術社區[雲棲]
什麼是紅黑樹？
寫這篇紅黑樹算法的目的：一是為了自己學習的總結；二是能夠與大家一起交流溝通一起努力。文中有些內容學習自《算法導論》一書，部分來自於維基百科，我會在文中標注出來，有不明白的地方可以通過留言大家一起溝通。
首先，什麼是紅黑樹呢？ 紅黑樹是一種“平衡的”二叉查找樹，它是一種經典高效的算法，能夠保證在最壞的情況下動態集合操作的時間為O（lgn）。紅黑樹每個節點包含5個域，分別為color,key,left,right和p。 color是在每個節點上增加的一個存儲位表示節點的顏色，可以是RED或者BLACK。key為結點中的value值，left,right為該結點的左右孩子指針，沒有的話為NIL，p是一個指針，是指向該節的父節點。如下圖（來自維基百科）表示就是一顆紅黑樹，NIL為指向外結點的指針。（外結點視為沒有key的結點）
紅黑樹有什麼性質呢？一般稱為紅黑性質，有以下五點：
1）每個結點或者是紅的或者是黑的；
2）根結點是黑的；
3）每個葉結點（NIL）是黑的；
4）如果一個結點是紅的，則它的兩個孩子都是黑的；
5）對每個結點，從該結點到其他其子孫結點的所有路徑上包含相同數目的黑結點。
為了後麵的分析，我們還得知道以下知識點。
（1）黑高度：從某個結點x出發（不包括該結點）到達一個葉結點的任意一條路徑上，黑色結點的個數稱為該結點x的黑高度。
（2）一顆有n個內結點的紅黑樹的高度至多為2lg(n+1)。 （內結點視為紅黑樹中帶關鍵字的結點）
（3）包含n個內部節點的紅黑樹的高度是 O(log(n))。
證明（來自維基百科）：
定義:
- h(v) = 以節點v為根的子樹的高度。
- bh(v) = 從v到子樹中任何葉子的黑色節點的數目(如果v是黑色則不計數它)(也叫做黑色高度)。
引理: 以節點v為根的子樹有至少2bh(v) − 1個內部節點。
引理的證明(通過歸納高度):
基礎: h(v) = 0
如果v的高度是零則它必定是 nil，因此 bh(v) = 0。所以:
2bh(v) − 1 = 20 − 1 = 1 − 1 = 0
歸納假設: h(v) = k 的v有 2bh(v) − 1 − 1 個內部節點暗示了 h(v') = k+1 的v'有2bh(v') − 1 個內部節點。
因為 v' 有 h(v') > 0 所以它是個內部節點。同樣的它有黑色高度要麼是 bh(v') 要麼是 bh(v')-1 (依據v'是紅色還是黑色)的兩個兒子。通過歸納假設每個兒子都有至少2bh(v') − 1 − 1 個內部接點，所以v' 有:
2bh(v') − 1 − 1 + 2bh(v') − 1 − 1 + 1 = 2bh(v') − 1
個內部節點。
使用這個引理我們現在可以展示出樹的高度是對數性的。因為在從根到葉子的任何路徑上至少有一半的節點是黑色(根據紅黑樹屬性4)，根的黑色高度至少是h(root)/2。通過引理我們得到:
因此根的高度是O(log(n))。
到這裏，紅黑樹基本的概念理解就到一段落，我會在下一篇文章中寫關於紅黑樹的插入以及刪除的操作。
最後更新：2017-04-02 06:51:59