當轉換爲紅黑樹時，是否有理由選擇一種形式而不是另一種形式？

Question

我有一個鏈接列表/二叉樹方法的庫，當標準容器不適合時使用 - 例如當有不同類型的節點時，或者當我需要從二叉樹轉換爲列表並返回時。它包括紅黑樹處理。

其中一種方法在O(n)時間（假設項目數已知）中從雙鏈錶轉換爲完全平衡的簡單二叉樹。該算法被稱爲「摺疊」 - 這是一次在Dr. Dobbs'中發佈的二叉樹重新平衡算法的後半部分。這些步驟基本上都是......

• 由於樹的大小，決定對左，右子樹

• 遞歸左子樹

• 的尺寸從彈出的節點該列表以root

• 遞歸的右子樹

• 鏈接的使用ubtrees的根

我也有類似的方法，創建一個紅黑樹。原理是一樣的，但遞歸跟蹤節點高度 - 高度爲零的節點被創建爲紅色，其他所有節點都是黑色的。起始高度計算基於樹大小中的最高設置位，並且被弄亂，使得尺寸完美的(2^n)-1大小的樹僅具有黑色節點（遞歸僅下降到高度1）。

這裏的要點是，我只在葉級別有紅色節點，最多隻有一半的節點是紅色的。

事情是，雖然這是生成有效的紅黑樹的簡單方法，但它不是唯一的選擇。避免讓一片完美平衡的樹上的所有葉子變成紅色是一種任意的選擇。我可以有紅色和黑色節點的交替層。或者，在某些情況下，我可以通過發現完美平衡的子樹（如果它需要紅色節點），使子樹根變紅而不是所有樹葉，顯着減少紅色節點的數量。

問題是 - 是否有任何實際的理由選擇一個有效的紅黑樹形式而不是另一個？

這是純粹的好奇心 - 我知道我沒有任何實際的理由 - 但有誰知道這個選擇是重要的專家應用程序？

Answer 1

在使用pysicist方法修改紅黑樹的攤銷成本的標準分析中，具有零個或兩個紅孩子的黑節點被指定爲1的正電位，這意味着它們代表樹中有問題的地方，其中額外的工作可能需要完成。只有一個紅孩子的紅節點和黑節點被賦予零電位。

因此，爲了減少修改成本，給每個黑色節點一個紅色的孩子。

---

的原因爲什麼用一個紅孩子是有福的黑色結點是通過類比最好的解釋冗餘二進制數。我將首先解釋如何將紅黑樹與二進制數聯繫起來，然後我將解釋爲什麼一個紅孩子節點是有用的。

大家可能知道，紅黑樹是表示2-4樹，其中從根到葉的每個簡單的路徑具有相同的長度，但節點具有2，3，或4個孩子的一種方式。用於在2-4樹中添加或移除節點的最簡單算法與從冗餘二進制數中增加或減去一個算法的算法相同。

冗餘二進制數是一個數字，其中第i個數字表示2 ^我，正如在標準的二進制數，而第i個位可以是0,1，或2。他們被稱爲多餘的，因爲有多種方式來編寫給定的數字。 4 _dec可以寫成100或20或12.

要將一個冗餘二進制數加1，可以增加最低有效位;如果它是3，則將其設置爲1並遞增下一個最不重要的數字，依此類推。當它遇到一個0或1

一葉添加到2-4樹，一個孩子添加到其目標父算法停止。如果父母有五個孩子，則將其分爲兩個節點並使其成爲父母的子女。繼續，直到到達不需要拆分的節點。所以，當它遇到有兩個或三個孩子的節點時，朝向根的路徑停止。

要結合遞增冗餘二進制數的攤銷成本，使用物理學家方法和爲1的電勢分配給每個2位。一個xall增量觸及k個數字會釋放k-1個潛在值，給它一個O（1）的攤銷成本。

該分析類似於遞增標準二進制數的攤銷成本，但標準二進制數不能同時支持O（1）攤銷時間的遞增和遞減：考慮2 ^k - 1.它是k 1數字。增量成本Θ（k）。如果後面跟着一個減量，這一對花費爲Θ（k），並使數字回到原來的狀態。

冗餘二進制比較特殊，1位停止都遞增和遞減的級聯操作。 2-4樹是特殊的，因爲3節點會暫停插入和刪除的級聯操作。

在紅黑樹，有一個紅孩子的節點是在2-4樹中的3個節點的只是一種表象。這些節點對於在其子樹中插入或刪除是特殊的和強大的，因此在構建將會看到大量更新的紅黑樹時應該傾向於這些節點。

如果你知道你會看到只有插入，喜歡有兩個黑人孩子的節點。如果你知道你會看到只有刪除，喜歡有兩個紅孩子的節點。

Answer 2

簡短的回答是：它取決於。

基本上，任何有效的樹就足夠了。然而，就amortized analysis而言 - 很可能你會選擇最正確的樹，從長遠來看，它會給你最優化的行爲。

例如如果你總是選擇一個有效的樹，但是一個很容易進行平衡操作，那麼你的性能就會很差。一個明顯的例子是完全黑色的樹，它是完全有效的，但修改後性能很差。

這取決於，因爲這通常是應用程序特定的。