無限數量的最大不平衡的紅黑樹

Question

我必須找到一個最大不平衡的紅黑樹的家庭，並證明該家庭的「各自的屬性」，以證明有一個無限大紅黑樹的家庭有接近2log（n + 1）的高度。

現在我的猜測是，這個家庭基本上包括所有的紅黑樹，其中有一個路徑與s-r-s-r ...節點，其餘的路徑充滿黑節點。但我如何證明這一點？以及我如何正式寫下這樣一個家庭的樣子？

謝謝！

Answer 1

現在我的猜測是，這個家庭基本上包括所有的紅黑樹，其中有一個路徑與s-r-s-r ...節點，其餘的都是黑節點。

這是一個合理的猜測。

但我該如何證明？

描述樹T_0，T_1，T_2，T_3，...的無限序列，使得對於每個整數n，存在具有至少n個節點的序列中的樹。證明存在一個常數C，使得對於每個i，T_i的高度至少爲2log（n_i + 1）-C，其中n_i是T_i中的節點數。 （這是含糊不清的術語「接近」的一種可能解釋）。

我該如何正式寫下這樣一個家庭的樣子？

感應式。我會以全黑樹爲例。樹T_0是空的（基本情況）。對於所有大於0的整數，樹T_i由一個黑色節點組成，左邊和右邊的子樹等於T_ {i-1}（歸納步驟）。然後你可以使用歸納法來證明這些樹的事實。