紅黑樹筆記

紅黑樹學習

rb1:根結點必須是黑色，空葉子結點視為是黑色

rb2:不能有兩個相鄰的紅色節點（父節點和子節點不能同時為紅色）

rb3:從根結點到任意空葉子結點的路徑的黑色結點數相等。

衍生推論：

1.紅黑樹從根結點起，最長路徑比最短路徑節點數比，不會超過2:1

2.以紅黑樹任意黑色節點為根，都是一顆紅黑樹

3.任意節點到外部節點的所有路徑中，黑色節點數是一緻的。

術語：

外部節點：紅黑樹的空葉子節點

紅黑樹節點的階：一個節點到外部節點的路徑中的黑色節點數，是紅黑樹的階。

rb2不平衡狀态：插入操作中會出現，即違反了相鄰節點不能是紅色節點的規則的狀态，有八種情況

LLr,LLb,LRr,LRb,RLr,RLb,RRr,RRb.

現有節點X

第一個字母表示：L即X的左子節點為紅色，R即X的右子節點為紅色

第二個字母表示：L即第一個字母對應的節點的左葉子節點為紅色，R即第一個字母對應的右葉子節點為紅色。

第三個字母表示：X的另一個子節點顔色。r紅色，b黑色

LLr為例子：代表X節點的左節點及左節點的左節點為紅色，X的右節點為紅色

RLb為例子：代表X節點的右節點及右節點的做節點為紅色，X的左節點為黑色

插入操作：

新插入的節點都是紅色節點，因為插入黑節點會導緻rb2定律不符合，且很難調整。

如果是XYr型(LLr,LRr,RLr,RRr)不平衡狀态，需要進行變色操作，其餘的需要進行旋轉。

變色：XYr型不平衡狀态，左右子節點都是紅色節點，為了保持rb3規則，此時需要将目前節點變紅色，子節點都變為黑色，這樣變色不會影響到rb3規則。

變色之後可能會産生新的不平衡狀态。除了8中不平衡狀态，還有可能出現根結點變紅，如果根結點變紅直接染黑。其餘8種不平衡狀态，依然照常處理，直至平衡。

删除操作：

删除操作和插入操作大同小異，就是分析不同的情況進行染色或者旋轉，删除略微複雜一下，大概思想了解了就行了，不再詳述了。

性能分析：

紅黑樹在删除和插入的時候平均性能比較好，因為有機率隻需要染色不需要旋轉。

紅黑樹是不平衡的，但是因為rb2的緣故，極端情況下，紅黑樹從根結點出發的最長路徑最多比最短路徑長一倍。紅黑樹節點越多，性能差異就越小，在實際查詢中，性能差異基本可以忽略。

紅黑樹實作相對複雜一些。