「稽古】左偏紅黑樹 I 這就是紅黑樹嗎真的沒有搞錯嗎

簡單介紹完二叉查找樹與平衡樹之後，我們現在來審察平衡樹中一種特殊的平衡方式，那便是紅黑樹。

Intro

紅黑樹¹（Red-Black Tree，簡稱RBT） 之所以叫紅黑樹是因爲其節點具有紅與黑兩種顏色，可以視爲“被染色”和“未染色”兩種狀態。
紅黑樹通過控制紅黑兩種節點的排列來保證其平衡，爲此，一棵紅黑樹滿足以下特徵：

1. 節點為紅色或黑色；
2. 紅色的節點的所有兒子的顏色必須是黑色，即從每個葉子到根的所有路徑上不能有兩個連續的紅色節點；
3. 從任一節點到其子樹中的每個葉子的所有簡單路徑上都包含相同數目的黑色節點（黑高平衡）。

這保證了從根節點到任意葉子的最長路徑（紅黑交替）不會超過最短路徑（全黑）的二倍，從而保證了樹的平衡性。

如圖所示便是一棵紅黑樹，滿足以上各項性質。

References

¹. OI-Wiki 章節 左偏紅黑樹-紅黑樹 ↩

². 13 Red Black Trees Bilibili: av14050857 2017-09-01 ↩

³. 「JDK源碼剖析之紅黑樹TreeMap」子空kosora+七月在線 Bilibili: av23890827 2018-05-25 ↩