爲什麼我們不在紅黑樹插入中添加黑節點而不是紅節點？

Question

在紅黑樹插入，我們總是選擇添加一個新的節點爲紅色，以便我們能夠避免改變樹的黑色高度。爲什麼這比添加黑節點更可取？

Answer 1

我認爲這是由於紅黑樹的規則...

1. A node is either red or black. 
2. The root is black. 
3. All leaves (NIL) are black. 
4. Both children of every red node are black. 
5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes. 

的插入是在樹的底部加入其中，用一個節點替換葉（黑色無）節點價值和2黑黑兒童。規則5規定每條路徑上黑色節點的數量必須相同。如果您添加了黑色節點，則會違反此規則。我會盡力說明。

     B(10) 
      R(5)     B(15) 
    B(1)    B(6)  B(NIL) B(NIL) 
B(NIL) B(NIL) B(NIL) B(NIL) 

您會注意到在每條路徑上都有3個黑色節點。如果您試圖在15之下插入一個新節點16作爲黑節點（請記住，您要在添加的節點下添加2個黑節點），那麼該路徑將變得更長（4）。這是不正確的是這樣的：

     B(10) 
      R(5)      B(15) 
    B(1)    B(6)  B(NIL)  B(16) 
B(NIL) B(NIL) B(NIL) B(NIL)   B(NIL) B(NIL) 

爲了保持滿足所有規則，你需要插入一個紅色節點，每個路徑上的黑色結點的數量將保持相等。

     B(10) 
      R(5)      B(15) 
    B(1)    B(6)  B(NIL)  R(16) 
B(NIL) B(NIL) B(NIL) B(NIL)   B(NIL) B(NIL)