紅黑樹〜1子刪除

Question

紅父節點有可能只有一個黑子節點嗎？我一直在玩紅/黑樹模擬器在線，我無法設法得到這種情況發生。

背後問這個的原因是我相信我有一個不必要的，如果在我的代碼...

if (temp_node->color == BLACK && node->color == RED) 
{ 
    node->color = BLACK; 
    global_violation = false; 
} 

感謝您的反饋！

Answer 1

不，這是不可能的。請記住，在紅/黑樹中，從樹根開始的所有路徑必須通過相同數量的黑節點（即紅/黑樹不變量之一）。

如果你有一個紅色節點x與一個黑人孩子y，它不能有另一個紅孩子（因爲這打破了紅/黑不變紅色節點不能有紅孩子）。

這意味着通過x到丟失孩子的路徑將通過比路徑至少少了一個黑色節點通過x，然後y，然後過樹從那裏，打破了紅/黑樹不變量。