紅黑樹上的問題

Question

如果我有一棵二叉樹，並且想要將黑/紅屬性添加到其所有節點以形成一棵紅黑樹，是否有辦法做到這一點，如果我們知道二叉樹是平衡的？

Answer 1

可能紅黑樹上最嚴格的條件是任何根空路徑必須具有相同數量的黑節點的事實。因此，一個選項是從根開始運行DFS以確定最短的root-NULL路徑的長度。該路徑長度給出樹的「黑色高度」的上限，這是任何根空路徑上的黑色節點的數量。

一旦我們有了這個值，我們可以嘗試給節點分配黑色高度，讓我們確定哪些節點是紅色或黑色。一個有用的觀察結果如下：任何一個節點的子樹的黑色高度必須相同，否則會有兩個具有不同黑色高度的root-NULL路徑。因此，對於每個節點，如果其當前黑色高度爲h並且希望的黑色高度爲H，則我們可以：

• 將它着色爲紅色，在這種情況下，高度H.我們也迫使下面那些子樹的根部變黑。
• 將它染成黑色，在這種情況下，我們遞歸着色左側和右側子樹，使它們具有黑色高度H - 1。這些樹根上的節點可以是任何顏色。

我想你可以通過使用動態編程來做到這一點。假設所需的目標黑色高度爲H，我們可以製作一個由節點/黑色深度/顏色三元組索引的表格（這裏，黑色高度是以該節點爲根的子樹的黑色高度），該表格存儲是否可以爲節點以正確的方式。我們稱之爲T [v，h，c]。我們可以如下填寫：

• 將NULL視爲黑色的節點。 T [null，0，red] = false，T [null，0，black] = true。
• 對於每個節點，在使得如果它的子樹的L和R被處理V是隻處理中，執行以下的順序進行處理：
  • T [V，H，紅色] = T [L，H，黑]和T [r，h，黑]
  • 任何顏色的T [v，h，黑] = T [l，h - 1，c]和T [r，h - 1，c] c

一旦你評估這個，你可以檢查T [root，h，c]對於任何高度爲h或者顏色c是否爲真。這應該只需要多項式時間。

希望這會有所幫助！

Answer 2

Templatetypedef已經以非常好的方式回答了您的問題的主要部分。我只是想爲你的第二個問題添加一個答案。

由於紅黑色標記用於防止不平衡的樹木出現，所以當然不可能爲每一個搜索樹着色 - 如果它沒有達到任何效果！一個反例是這棵樹：

1 
\ 
    2 
    \ 
    3 

所有留下的孩子都是空的。