半年前在研究HashMap的時候已經學習過紅黑樹的規則原理了. 不過現在又遇到就忘記是怎麼實現的了.(只知道這玩意是用來平衡樹的) 這次就把這個數據結構做一個了斷.

性質

  • 性質1：每個節點要麼是黑色，要麼是紅色。
  • 性質2：根節點是黑色。
  • 性質3：每個葉子節點（NIL）是黑色。
  • 性質4：每個紅色結點的兩個子結點一定都是黑色。
  • 性質5：任意一結點到每個葉子結點的路徑都包含數量相同的黑結點。

滿足這5個性質就能保證紅黑樹是平衡的.

Insert

插入的節點默認是紅色的.因為這樣可以最大限度滿足紅黑樹的5個性質.

請試想一下.如果插入的節點是紅色:

  • 性質1可以滿足.
  • 性質2可以滿足.
  • 性質3可以滿足(插入紅色節點後自動衍生出2個黑色的NIL節點).
  • 性質4可能沒法滿足(新插入的節點的父節點也是紅色).
  • 性質5可能沒法滿足(父節點是黑色時就不行).

然後是紅黑樹節點的左右旋.

看懂沒? 節點的旋轉大概就是這樣。

然後就是要分插入的情況了.

  • 第一種：根節點為空。這種情況，將node的顏色改為黑色即可.

  • 第二種: node的父節點為黑色。這種情況不需要做修改.

  • 第三種: node的父節點為紅色 (根據性質3，N的祖父節點必為黑色). 這種情況和變換規則都比較多.下面細說…

    • node的叔父節點為紅色。這種情況，將N的父節點和叔父節點的顏色都改為黑色，若祖父節點是跟節點就將其改為黑色，否則將其顏色改為紅色，並以祖父節點為插入的目標節點開始重新遞歸修復紅黑樹.

    • node的叔父節點為黑色，且node和node的父節點在同一邊 (即父節點為祖父的左兒子時，N也是父節點的左兒子。父節點為祖父節點的右兒子時。N也是父節點的右兒子)。以父節點為祖父節的左兒子為例，將父節點改為黑色，祖父節點改為紅色，然後以祖父節點為基準右旋。(N為父節點右兒子時做相應的左旋)

    • node的叔父節點為黑色，且node和node的父節點不在同一邊 (即父節點為祖父的左兒子時，N是父節點的右兒子。父節點為祖父節點的右兒子時。N也是父節點左右兒子)。以父節點為祖父節點的左兒子為例。以父節點為基準，進行左旋，然後以父節點為目標插入節點進入情況3的b情況進行操作。

Delete

這個以後再說.

紅黑樹算是搜索二叉樹的一個子集，Search方法是相同的。