題組內容

四、(一)在一棵高度為 h(h=0,1,2,…)的 AVL tree 中：

⑵假設此樹共有45個 nodes。請問此 AVL tree 可能最高之高度及最矮之高度各為何？

詳解提供者：111郵專一，地特四資訊正取

F_h+2-1<=n<=2^h+1-1

h>=log₂⁽ⁿ⁺¹⁾-1 (取上限，所以log₂⁽⁴⁵⁺¹⁾=5.多取6)

h最低5

對照費氏數列

0 1 2 3 4 5 6 7 8 9 10

0 1 1 2 3 5 8 13 21 34 55

h最高9