爲什麼有N個節點的AVL樹保持C <= N/2？

Question

如果C表示的「獨苗」的節點數量（一個節點被稱爲唯一的孩子時，其父是不是null & &它沒有兄弟姐妹），爲什麼我們的，對於每一個AVL樹與N個節點：C < =（N/2）？

Answer 1

考慮高度1的AVL樹（即僅由根的）：條件清楚地保持（N = 1，C = 0）。

現在考慮高度2的AVL樹有可以是帶2個孩子（N = 3，C = O）或與一個子根（N = 2，C = 1）的根部。因此，條件也適用於高度爲2的樹。

現在假設條件對於高度爲h（h> = 2）和h-1的樹適用，我們表明它也適用於高度爲h的樹+1。我們可以用一個高度爲h的孩子和另一個高度爲h或h-1的孩子取一個新根來構建高度爲h + 1的樹。這些是唯一允許保持AVL屬性完整的配置。兩個子樹的新根和新根都不是「唯一的孩子」節點。因此，我們有N = 1 + N1 + N2和C = C1 + C2。由於C1 < = N1/2和C2 < = N2/2，我們得到c也< = N/2。

現在，誘導條件適用於各種身高的AVL樹。