當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

漫画：什么是红黑树

發布時間：2023/12/3 编程问答 22 豆豆

生活随笔收集整理的這篇文章主要介紹了漫画：什么是红黑树小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

轉載自?玻璃貓程序員小灰

————————————

二叉查找樹（BST）具備什么特性呢？

1.左子樹上所有結點的值均小于或等于它的根結點的值。

2.右子樹上所有結點的值均大于或等于它的根結點的值。

3.左、右子樹也分別為二叉排序樹。

下圖中這棵樹，就是一顆典型的二叉查找樹：

1.查看根節點9：

2.由于10 > 9，因此查看右孩子13：

3.由于10 < 13，因此查看左孩子11：

4.由于10 < 11，因此查看左孩子10，發現10正是要查找的節點：

假設初始的二叉查找樹只有三個節點，根節點值為9，左孩子值為8，右孩子值為12：

接下來我們依次插入如下五個節點：7,6,5,4,3。依照二叉查找樹的特性，結果會變成什么樣呢？

1.節點是紅色或黑色。

2.根節點是黑色。

3.每個葉子節點都是黑色的空節點（NIL節點）。

4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)

5.從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

下圖中這棵樹，就是一顆典型的紅黑樹：

什么情況下會破壞紅黑樹的規則，什么情況下不會破壞規則呢？我們舉兩個簡單的栗子：

1.向原紅黑樹插入值為14的新節點：

2.向原紅黑樹插入值為21的新節點：

由于父節點22是紅色節點，因此這種情況打破了紅黑樹的規則4（每個紅色節點的兩個子節點都是黑色），必須進行調整，使之重新符合紅黑樹的規則。

變色：

為了重新符合紅黑樹的規則，嘗試把紅色節點變為黑色，或者把黑色節點變為紅色。

下圖所表示的是紅黑樹的一部分，需要注意節點25并非根節點。因為節點21和節點22連續出現了紅色，不符合規則4，所以把節點22從紅色變成黑色：

但這樣并不算完，因為憑空多出的黑色節點打破了規則5，所以發生連鎖反應，需要繼續把節點25從黑色變成紅色：

此時仍然沒有結束，因為節點25和節點27又形成了兩個連續的紅色節點，需要繼續把節點27從紅色變成黑色：

左旋轉：

逆時針旋轉紅黑樹的兩個節點，使得父節點被自己的右孩子取代，而自己成為自己的左孩子。說起來很怪異，大家看下圖：

圖中，身為右孩子的Y取代了X的位置，而X變成了自己的左孩子。此為左旋轉。

右旋轉：

順時針旋轉紅黑樹的兩個節點，使得父節點被自己的左孩子取代，而自己成為自己的右孩子。大家看下圖：

圖中，身為左孩子的Y取代了X的位置，而X變成了自己的右孩子。此為右旋轉。

我們以剛才插入節點21的情況為例：

首先，我們需要做的是變色，把節點25及其下方的節點變色：

此時節點17和節點25是連續的兩個紅色節點，那么把節點17變成黑色節點？恐怕不合適。這樣一來不但打破了規則4，而且根據規則2（根節點是黑色），也不可能把節點13變成紅色節點。

變色已無法解決問題，我們把節點13看做X，把節點17看做Y，像剛才的示意圖那樣進行左旋轉：

由于根節點必須是黑色節點，所以需要變色，變色結果如下：

這樣就結束了嗎？并沒有。因為其中兩條路徑(17 -> 8 -> 6 -> NIL)的黑色節點個數是4，其他路徑的黑色節點個數是3，不符合規則5。

這時候我們需要把節點13看做X，節點8看做Y，像剛才的示意圖那樣進行右旋轉：

最后根據規則來進行變色：

如此一來，我們的紅黑樹變得重新符合規則。這一個例子的調整過程比較復雜，經歷了如下步驟：

變色 -> 左旋轉 -> 變色 -> 右旋轉 -> 變色

幾點說明：

1. 關于紅黑樹自平衡的調整，插入和刪除節點的時候都涉及到很多種Case，由于篇幅原因無法展開來一一列舉，有興趣的朋友可以參考維基百科，里面講的非常清晰。

2.漫畫中紅黑樹調整過程的示例是一種比較復雜的情形，沒太看明白的小伙伴也不必鉆牛角尖，關鍵要懂得紅黑樹自平衡調整的主體思想。