特征

紅黑樹有以下特征:

1. 每個節(jié)點或者是黑色，或者是紅色。
2. 根節(jié)點是黑色。
3. null結(jié)點默認(rèn)是黑色, 因此每個葉子節(jié)點（指空(nil或null)的葉子節(jié)點?。┦呛谏?。 : 個人理解,根據(jù)這個特征,插入節(jié)點時,每個結(jié)點都能找到叔叔結(jié)點
4. 如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。
5. 從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。

另外紅黑樹可以理解為是一個四階的B樹

還可以反推出一些特征

• 紅色結(jié)點要么有兩個黑色的nil結(jié)點,要么有兩個黑色非空子結(jié)點. 要不然就違背了第五個特征

插入

插入的結(jié)點默認(rèn)是紅色的,這樣的話,插入結(jié)束后,只有可能違背第四個原則,之后只要通過一些辦法修正就可以了

• 按照二叉搜索樹的插入方法進行插入
  • 若插入的是根結(jié)點,插入結(jié)點變成黑色,插入結(jié)束
  • 若插入后父結(jié)點是黑色的,沒有違背紅黑樹的特征,插入結(jié)束
  • 若插入后父結(jié)點是紅色的, 此時祖父結(jié)點肯定是黑色的, 叔叔結(jié)點可能是黑色可能是紅色
    • 若叔叔結(jié)點是紅色的
      • 父結(jié)點和叔叔結(jié)點都變成黑色,祖父結(jié)點變成紅色,
      • 祖父結(jié)點的子結(jié)點們,都滿足了紅黑樹的特征,以祖父結(jié)點作為插入結(jié)點,重新走插入結(jié)束的判斷
    • 若叔叔結(jié)點是黑色的,且當(dāng)前結(jié)點是父結(jié)點的右結(jié)點
      • 把父結(jié)點作為當(dāng)前結(jié)點,之后左旋.
      • 重新走插入結(jié)束的判斷
      • 這一步的目的是把當(dāng)前結(jié)點變成父結(jié)點的左結(jié)點
  • 若叔叔結(jié)點是黑色的,且當(dāng)前結(jié)點是父結(jié)點的左結(jié)點
    • 把父結(jié)點變成黑色,祖父結(jié)點變成紅色
    • 以祖父結(jié)點作為當(dāng)前結(jié)點,然后右旋,
    • 到這一步,就修復(fù)了違背紅黑樹第四個特征的問題,插入結(jié)束

刪除

首先按照二叉搜索樹的刪除方法進行刪除
刪除的結(jié)點,要么是黑色結(jié)點,要么是有兩個黑色的nil結(jié)點的紅色結(jié)點.

• 如果刪除的紅色結(jié)點,并不會違背什么原則,直接結(jié)束
• 如果要刪除的是黑色結(jié)點
  1. 要刪除的結(jié)點是兩個黑色的nil結(jié)點
     1.兄弟結(jié)點是紅色且刪除的結(jié)點是左結(jié)點 (父結(jié)點是黑色)
     • 兄弟結(jié)點變成黑色,父結(jié)點變成紅色,然后父結(jié)點左旋,

     • 這樣做的目的是,兄弟結(jié)點變成了黑色,

       
       
       要刪除D結(jié)點
       
       
       要刪除D結(jié)點
     2. 兄弟結(jié)點是紅色且刪除的結(jié)點是右結(jié)點(父結(jié)點是黑色)
     • 兄弟結(jié)點變成黑色,父結(jié)點變成紅色,然后父結(jié)點右旋,
     • 這樣做的目的是,兄弟結(jié)點變成了黑色,
     3. 節(jié)點是左結(jié)點,兄弟結(jié)點是黑色,且兄弟結(jié)點的右節(jié)點是紅色結(jié)點(要么是紅色結(jié)點,要么是黑色的nil結(jié)點,要不然在刪除之前就不平衡了)
     • 此時要刪除結(jié)點若刪除,則經(jīng)過子節(jié)點（nil節(jié)點）的路徑的黑色節(jié)點個數(shù)就會減1，

     • 將兄弟結(jié)點的右結(jié)點變成黑色,父結(jié)點和兄弟結(jié)點換顏色,然后父結(jié)點左旋,

       
       
       要刪除D結(jié)點
       
       
       要刪除D結(jié)點
     4. 節(jié)點是右節(jié)點,兄弟節(jié)點是黑色,且兄弟結(jié)點的左結(jié)點是紅色結(jié)點
        • 將兄弟結(jié)點和左結(jié)點變成黑色,父結(jié)點和兄弟結(jié)點換顏色,父結(jié)點右旋
     5. 結(jié)點是左結(jié)點,兄弟結(jié)點是黑色,兄弟結(jié)點的左結(jié)點是紅色
        • 兄弟結(jié)點變成紅色,兄弟結(jié)點的左結(jié)點變成黑色, 兄弟結(jié)點右旋

        • 此時變成了第3種情況

          
          
          要刪除D結(jié)點
          
          
          要刪除D結(jié)點
     6. 節(jié)點是右節(jié)點,兄弟結(jié)點是黑色,兄弟結(jié)點的右節(jié)點是紅色
        • 兄弟結(jié)點變成紅色,兄弟結(jié)點的右節(jié)點變成黑色,兄弟結(jié)點左旋
        • 此時變成了第四種情況
     7. 不符合上述情況時,兄弟結(jié)點是黑色,兄弟結(jié)點的孩子,都是黑色的nil結(jié)點,父結(jié)點是紅色,

        • 將父親節(jié)點改成黑色，將兄弟節(jié)點改成紅色，

          
          
          要刪除D結(jié)點
     8. 父結(jié)點是黑色,兄弟結(jié)點是黑色,兄弟結(jié)點的孩子都是黑色的nil結(jié)點,父結(jié)點是黑色
        • 兄弟結(jié)點變成紅色,再以父結(jié)點作為刪除結(jié)點,進行平衡操作

  2. 刪除黑色的非葉節(jié)點
     這種情況下,刪除的黑色節(jié)點僅有左子樹或者僅有右子樹。且另一個結(jié)點肯定是有兩個黑色的nil子結(jié)點的紅色結(jié)點
     直接讓另一個子結(jié)點變?yōu)楹谏?然后替換要刪除的結(jié)點就行

     
     
     刪除D結(jié)點
     
     
     刪除D結(jié)點