AVL樹

Question

分析我對韋斯

閱讀中的數據結構和分析AVL特雷斯

一個平衡狀態還是堅持認爲每個節點必須具有相同高度的 左，右子樹。如果將空子樹的高度定義爲-1（如通常情況下那樣），那麼只有完美的（（2到k）-1）個節點的平衡樹將滿足這個標準。因此，雖然這保證了較小深度的樹木，但平衡條件過於僵硬而不實用，需要放鬆。在瞭解上述文本提供一個示例 1.如作者是怎麼來用

請求幫助（（2〜k的功率） - 1）節點將會滿足這些條件？ 2.什麼聲明「雖然這保證了小深度的樹木，但平衡條件過於僵化，無用且需要放鬆」 是什麼意思？

謝謝！

Answer 1

如此處所述，一個完美平衡的樹在任何節點的任一側具有相同數量的節點。能夠滿足這具有的總節點數樹木：

1: * 

3: * 
/\ 
* * 

7: * 
/\ 
    * * 
/\/\ 
* * * * 

等

在數學上，這意味着在樹中的節點的數目是2 ^ķ -1，其中k是整數。

「小深度」意味着這種形式的樹具有給定深度的最大可能節點數量：增加一個節點必須增加深度。