紅黑樹插入：插入時爲什麼使節點變紅？

Question

紅黑樹屬性不包含插入節點顏色的任何規則，我們總是插入紅色節點。

如果我們插入黑色節點沒有違背任何性質（任何排除4）？

Answer 1

是的！假設你在你的樹中的單個節點：

5 (black) 

現在，插入一個新的黑色結點到樹：

5 (black) 
    \ 
     9 (black) 

現在不變，在樹的每根空路徑具有相同數量的黑色節點被破壞，因爲從左邊的路徑有一個黑色節點，而從右邊的路徑有兩個。

希望這會有所幫助！

Answer 2

你似乎在問兩個問題

1）爲什麼要插入時（在標題）節點紅色？

2）是否插入黑違反任何性的判定？

也似乎是錯誤的印象，對於2回答yes）爲1的自動理）下。

不是這樣！將節點插入爲紅色也可能會違反其中一個RB樹屬性。例如，如果您將紅色節點作爲另一個紅色節點的子節點，那麼您剛剛違反了紅色節點只能有黑色子節點的屬性。

使它變成紅色的原因是修復子節點屬性（通過旋轉和重繪父級/祖父母）更容易，而不是試圖修復路徑長度屬性。也許另一個原因是，這是作者提出的。

它可能還可以通過插入黑色節點，而不是重新粉刷紅色修復了樹。也許沒有人考慮過它。