紅黑樹的python實現的簡單介紹

本文目錄一覽：

• 1、python的字典怎麼擴展成C呢？拿什麼數據結構接收？100分 詳細進來~
• 2、紅黑樹(Red-black tree)
• 3、紅黑樹詳解
• 4、紅黑樹——一個自平衡的二叉搜索樹

python的字典怎麼擴展成C呢？拿什麼數據結構接收？100分 詳細進來~

1、直接用PyObject。上策

2、轉換成C++ STL的Map容器是直接對應的。中策

3、使用的是數據，而不是結構，只要能讓中間的數據發揮作用，就沒必要一樣的結構，也就是轉換成具體適合你那接下來C中應用的結構。比如只用到某幾個鍵和某幾個值。如果C中根本不應用，就回到1。中策

4、自己在C中實現這種字典。建立散列表或者紅黑樹表。或者最簡單的兩個一維數組，實現key[],value[]的一一對應。下策

紅黑樹(Red-black tree)

樹 是一種 抽象數據類型 ，或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的 數據集合 。

紅黑樹 是一種自平衡二叉查找樹，典型的用途是實現 關聯數組 ，它是複雜的，但它的操作有着良好的最壞情況運行時間,並且在實踐中是高效的 O(log n ) 時間內做查找，插入和刪除，這裡的 n 是樹中元素的數目。

一個由n個節點隨機構成的二叉查找樹的高度為(log n ).證明如下：

而時間複雜度是以某個基礎數據操作的重複次數作為量度。紅黑樹的是二叉搜索樹，左子樹上所有節點的值均小於他的根節點的值，右子樹上所有節點均大於根節點的值，左右子節樹相對根節點按大小分布。如果把每次節點值的比較看成基礎數據操作，那麼最差的查找情況是一直查找到高度最大的根節點，那麼查找的時間複雜度即與高度成正比，可表示成 O(log n ) 。

簡單了解了紅黑樹的字面定義，下面動手感受下紅黑樹的相關操作。當你插入或者刪除一個節點時，可能會破壞紅黑樹的性質，所以需要對樹節點進行重新着色或者旋轉，來保持紅黑樹的結構。首先看下二叉樹的旋轉。

假設pivot節點不為空，其右子樹不為空，那麼左旋即是：使pivot的右孩子Y為子樹的根，pivot節點為子樹根節點的左孩子，pivot左孩子、Y節點的右孩子不改變，Y節點左孩子變為pivot節點右孩子。

假設pivot節點不為空，其左子樹不為空，那麼右旋：使pivot的左孩子Y為子樹的根，pivot節點為子樹根節點的右孩子，pivot的右孩子、Y節點的左孩子不變，Y節點的右孩子變為pivot節點的左孩子。

實戰演練之增加、刪除節點時，如何保證紅黑樹的性質不被破壞。

往一個空的紅黑樹中，依次插入數據：12 1 9 2 0 11 7 19 4

節點為根節點，所以為黑色，兩個null節點為黑色節點。

按照二叉搜索樹的邏輯，9小於12、大於1，應該是1節點的右孩子。但，新增的兩個NIL節點已經使得12，1，9，NI這條路徑的黑色節點至少為兩個，而12，NIL這條路徑的黑色節點只有兩個。所以要對1節點進行左旋，9節點變為12節點的左孩子，發現問題還是存在。繼續，對12節點進行右旋，9節點為根節點，1、12分別為9節點的左右孩子。嘗試着色，9節點必須為黑色，而1，12節點可以為紅色，也可以為黑色。

0節點直接作為1節點的左孩子，保持跟2節點相同的顏色即可。左右子樹依舊保持平衡。

從二叉查找樹的性質看，7節點作為2節點的右孩子即可。這時來分析着色問題，我們先看最短路徑的黑色分布，9，12，NIL這條路徑，有三個黑色節點，以此為參考，嘗試改變9節點左子樹的着色。目前最長的路徑是9，1，2，7，NIL這條路徑。保持三個黑色節點的話，9跟NIL已經為黑色節點，而紅色節點又不能挨着，所以只能是1為紅色節點，2為黑色節點，7為紅色節點。那麼9，1，0，NIIL這條路徑，0就要為黑色節點。調整完畢。

19節點作為12節點的右孩子，與左孩子保持一樣的紅色即可。

4節點應該作為7節點的左子樹，無論着什麼顏色，以1節點為根節點的子樹，都要破壞紅黑性質。所以應該進行旋轉。先以7為根節點進行一次右旋，再以2為根節點進行一次左旋。嘗試着色即可。

類似插入節點的分析、總結，刪除節點也可以針對每種場景找到固定的着色方法，就像玩一個遊戲，有自己的推理跟玩法。我先做個PPT，這塊稍後補充。

所有的插入、刪除都是有限個情況，基於插入、刪除的情況分析，即可編寫算法生成紅黑樹，使其在固定的業務場景中發揮紅黑樹穩定操作效率的特色了。

在 計算機科學 中， AVL樹 是最先發明的 自平衡二叉查找樹 。在AVL樹中任何節點的兩個 子樹 的高度最大差別為一，所以它也被稱為 高度平衡樹 。查找、插入和刪除在平均和最壞情況下都是 O （log n ）。增加和刪除可能需要通過一次或多次 樹旋轉 來重新平衡這個樹。

節點的 平衡因子 是它的左子樹的高度減去它的右子樹的高度（有時相反）。帶有平衡因子1、0或 -1的節點被認為是平衡的。帶有平衡因子 -2或2的節點被認為是不平衡的，並需要重新平衡這個樹。平衡因子可以直接存儲在每個節點中，或從可能存儲在節點中的子樹高度計算出來。

不提問題的碼農不是好程序員。自己寫完了紅黑樹的簡單剖析，感覺還是只懂皮毛，沒有從觸碰到算法的核心內容。所以，不妨留幾個小問題，擔心自己腦子生鏽或者沒事想玩手機的時候，再提筆研究下紅黑樹。

教你初步了解紅黑樹

算法的時間複雜度和空間複雜度-總結

紅黑樹從頭至尾插入和刪除

AVL樹

紅黑樹C源碼實現與剖析

Echo

8 Nov，2016

紅黑樹詳解

首先，我們來了解一下二叉查找樹,二叉查找樹具備以下幾個特點：

1、左子樹上所有節點的值均小於或等於它的根節點的值；

2、右子樹上所有節點的值均大於或等於它的根節點的值；

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

下面我們以一棵典型的二叉查找樹來查找值為10的節點：

以上圖例正是典型的二分查找的思想，查找所需的最大次數等同於二叉查找樹的高度。在往樹中插入新節點的時候也要用類似的方法，通過一層一層地比較大小從而找到新節點適合插入的位置。但是即便如此，二叉查找樹依舊存在它的缺陷，並且此缺陷恰恰體現在插入新節點的時候。請看下面圖例展示：

這樣的瘸腿形態雖然也符合二叉查找樹的特性，但是查找的性能卻大打折扣，幾乎變成了線性數據結構。為了解決二叉查找樹多次插入新節點而導致的不平衡問題，紅黑樹便應運而生了。

紅黑樹是一種自平衡的二叉查找樹，除了符合二叉查找樹的特性外，還具有下列性質：

1、根節點是黑色，節點是紅色或黑色；

2、每個葉子節點都是黑的空節點；（nil節點）

3、每個紅色節點的兩個子節點都是黑色；（也就是說從每個葉子到根的所有路徑上不能有兩個連續的紅色節點）

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

這些規則的限制，保證了紅黑樹的平衡，紅黑樹從根到葉子的最長路徑不會超過最短路徑的兩倍。當紅黑樹插入或者刪除節點的時候，紅黑樹的規則可能被打破，這時候就需要做出調整來維持它的平衡了。請看下面的例子（注意：新插入的節點必須是紅色，否則就沒有意義了）：

由於父節點22是也是紅色節點，因此打破了紅黑樹的規則（每個紅黑樹的兩個子節點都是黑色），所以必須進行調整，使之重新符合規則。那麼我們需要作出怎樣的調整才能保證一棵紅黑樹始終是符合規則的標準紅黑樹呢？調整有兩種方法：“變色”和“旋轉”，其中，旋轉又分為兩種形式：“左旋轉”和“右旋轉”。

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

下圖是摘自上面紅黑樹的一部分，節點25並非根節點。正如上面所說因為新節點21和節點22連續出現了紅色，不符合規則，所以把節點22從紅色變成黑色。

但這樣並不算完，節點22變成黑色後，憑空多出的黑色節點又打破了規則，發生連鎖反應，需要繼續把節點25從黑色變為紅色。

此時仍未結束，節點25變為紅色後，又和節點27形成了兩個連續的紅色，規則又被打破，需要繼續把節點27從紅色變為黑色。

如此一路走下來，完成變色調整。

逆時針旋轉紅黑樹的兩個節點，使得父節點被自己的右孩子取代，而自己成為左孩子。

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

這幾種方法究竟怎麼使用呢？紅黑樹的插入和刪除包含很多種情況，每種情況都有不同的處理方式，下面舉一個典型的例子，可以體會一下這個過程。

還以剛才插入節點21為例：

首先我們變色處理，把節點25及其下方的節點變色：

此時節點17和節點25是連續的兩個紅色節點，那麼此時再把節點17變成黑色節點可以嗎？顯然是不可以的，這樣依然不符合規則，更不可以把根節點13變成紅色。

既然變色已經無法解決問題，我們此時就要使用旋轉了，我們把節點13看作X，把節點17看作Y，進行左旋轉：

旋轉完成後，由於根節點必須是黑色，所以還需要進行變色：

至此並沒有結束，因為其中兩條路徑（17-8-6-NIL）的黑色節點數是4，其他路徑的黑色節點數是3，依舊不符合規則。這時我們需要把節點13看成X，節點8看成Y，做右旋轉：

然後再進行變色：

經過上面一系列的調整，我們的紅黑樹終於變得重新符合規則，整個過程有點複雜，經歷了：變色–左旋轉–變色–右旋轉–變色這樣的一系列步驟。

經過上面細緻的步驟演示，想必大家對二叉查找樹和紅黑樹有所了解了吧，對紅黑樹結構插入新節點所觸發的一系列的變化流程也有了大概印象。實際中紅黑樹的應用是很多的，比如JDK（Java開發工具包）的集合類TreeMap和TreeSet底層就是紅黑樹實現的，在Java8中，HashMap也用到了紅黑樹。其實關於紅黑樹自平衡的調整，插入和刪除節點時涉及到的情形一一展開講解還是很多很多的，但是萬變不離其中，紅黑樹自平衡調整的主體思想都是上面所敘述的，大家有興趣可以再進行深入的探究。

紅黑樹——一個自平衡的二叉搜索樹

普通的二叉搜索樹在最壞的情況下，可能退化成一個鏈表。而又因為二叉搜索樹的所有操作的性能（添加，刪除，查找等），與二叉搜索樹的高度有關。在最壞的情況下，二叉搜索樹的高度和元素個數相同，此時二叉搜索樹的效率降為了O(n)級別。

所以為了防止我們的二叉搜索樹退化成一個鏈表，就產生了 平衡二叉樹 。 平衡二叉樹 可以保證它的左右兩個子樹的高度差不會超過1。平衡二叉樹有很多實現，一個經典實現就是 紅黑樹 。

在紅黑樹中將樹中的節點劃分為兩種狀態，分別用黑色和紅色來表示。

紅黑樹為了保證自己能夠平衡子樹，所以制訂以下五個規則：

1、每個節點必須有顏色，要麼黑色，要麼紅色，沒有別的顏色。

2、根節點必須是黑色

3、所有的空節點(nil節點)都認為是黑色節點。

4、紅色的節點不能連續，即一個紅色的節點，它的父節點和子節點不能也是紅色的，

5、無論從哪一個節點起始，到它每個葉子節點的路徑中，黑色節點數量必須相同。

在對紅黑樹進行添加、刪除等操作之後，必須使紅黑樹符合這5個規則。

那麼問題來了，在添加刪除操作之後，樹中節點的數量都變了，是怎麼保證整個樹滿足上述這些規則呢？

這裡涉及到3種操作， 變色 、 左旋 和 右旋 。通過這個三種操作，在增刪節點之後調整樹的形狀結構，使它滿足上述5個規則。這也是紅黑樹能保持平衡的原因。

變色操作 我們在下文的添加、刪除節點的實際操作中，再進行在描述。

先來說一下左右旋。

文字描述一下就是，2的右孩子節點4，變為了2的父節點，2由父節點變為4的左孩子。同時，4原來的左孩子變為2的右孩子。

右旋與左旋相反，即以某節點為支點進行順時針旋轉。同樣，我們看下圖，是以5為支點進行的右旋:

文字描述同樣反過來，5的左孩子節點3，變為5的父節點，5由父節點變為3的右孩子。3原來的右孩子變為5的左孩子。

首先是在樹中找到新節點正確的位置，尋找位置的過程與普通的二叉搜索樹相同，只是將新插入的節點默認為 紅色節點 。為什麼默認為紅色？因為如果你將新節點默認為黑色，則插入後肯定會打破原本符合規則的紅黑樹（上述第5條規則）。但是，如果你將新節點定為紅色，則有可能不用任何操作就符合紅黑樹規則，如下圖，當新插入的紅色節點，它的父親節點為黑色時候，此時已經滿足紅黑樹規則了。所以用紅色比黑色好。

如果很不巧，新插入的節點的父親節點也為紅色，因為紅色節點不能連續，所以我們需要調整紅黑樹的結構使其滿足規則。在調整的過程中我們會遇到3種需要處理的情況，我們來一一進行說明。

情況1：

插入新節點40， 此時它的父節點為紅色，並且它的叔叔節點（即51）也為紅色 。此時我們需要進行 變色 操作。 將該節點的父親節點、叔叔節點都變為黑色，祖父節點變為紅色 。

此時上圖已經滿足紅黑樹的規則。但有的時候我們經過了變色操作後，仍不滿足紅黑樹的規則，會遇到下面的情況。

情況2：

如圖，我們插入新的節點53，在按情況1的操作變色後，變成了這樣:

最後我們說一下情況3的情景，如下圖：

我們向樹中插入新節點37，在按情況1的操作變色後，變成了這樣：

情況3：

3種情況我們說明完了，但是你可能還會有這樣的疑問，什麼時候進行左旋，什麼時候進行右旋；什麼時候以父節點為支點旋轉，什麼時候又以祖父節點為支點旋轉？

那麼我們可以總結一下，當遇到連續的紅色節點應該怎麼辦： 當前節點我們叫它X，如果X相對於父節點的左右位置和父節點相對於祖父節點的左右位置相同，此時，就以祖父節點為支點，進行反向旋轉。例如：X為父節點的左孩子，X的父節點同樣也是其祖父節點的左孩子，此時以祖父節點為支點進行右旋；

如果X相對於父節點的左右位置和父節點相對於祖父節點的左右位置不同，則以X的父節點為支點，進行旋轉，旋轉方向與X相對於父節點左右位置相反。例如：X為其父節點的左孩子，X的父節點為祖父節點的右孩子，此時以X的父節點為支點進行一次右旋。

在紅黑樹中刪除節點，肯定要涉及到要刪的這個節點是紅色的還是黑色的。刪除紅色比較簡單，我們先說一下刪除紅色節點。

刪除節點要考慮這個節點所處的位置，所以我們羅列一下紅色的節點所有可能的位置情況。

你可能會發現為什麼少了一種情況？它不能只有左子樹或者只有右子樹嗎?我們可以看下圖:

很明顯，這四種情況都不符合紅黑樹的規則，所以根本不會出現這種情況。

而對於既有左子樹也有右子樹的情況。 我們可以先和普通的二叉搜索樹的刪除操作一樣，將它與前驅或者後繼交換一下 。它就又變成第一種情況——成為了一個葉子節點。所以我們只需考慮當它是葉子節點的情況。

接下來我們看一下當要刪除的節點是黑色的時候應該怎麼辦。

同樣我們列一下節點位置可能的情況：

第三種情況和刪除紅色節點時的處理方法一樣，可以轉換成第一種或第二種情況，所以我們只關心前兩種情況。

當要刪除的黑色節點只有一個子樹時：

最後我們看一下最難處理的一種情況。

要刪除的黑色節點是葉子節點時：

情況1：待刪除黑色節點20，它的兄弟節點為紅色。

操作方法為：將遠侄子節點變黑，兄弟節點與父親節點互換顏色，最後以父節點為支點進行 左旋 。(為什麼是左旋？因為待刪除的20是左孩子，我們要將左子樹長度拉長，將它沉下來，使它變成多餘的節點好刪除它，如果它是右孩子，則進行右旋)

操作後如下圖就完成了。

情況3：待刪除黑色節點20，它的兄弟節點為黑色，但它沒有紅色的遠侄子節點(即nil點，記住，nil點算黑色)，只有紅色的近侄子節點。

操作後如下圖:

此時有了紅色的遠侄子，就滿足了情況2，再按情況2進行一次操作就完成了。

情況4：待刪除黑色節點20，它的兄弟節點為黑色，遠侄子、近侄子節點都沒有。(即兩個nil節點，nil節點算黑色)

我們將上圖紅黑樹按流程演示一下:

第一步按情況4操作，將55變紅。並將父節點50看做當前節點，繼續操作。

此時有關紅黑樹的知識就說完了。

以上所有內容都為自己查閱資料學習理解之後手敲的。盡量得採用通俗易懂的描述和解釋讓讀者更明白。27張圖都是自己親自畫的，花費了四天才寫完，如果覺得寫的還可以，麻煩點亮喜歡支持一下，如果還是不懂，可以下方留言QQ等聯繫方式，我親自告訴你。