申論題 - 阿摩線上測驗

申論題資訊

試卷：109年 - 109 地方政府特種考試_三等_資訊處理：資料結構#94833
科目：公職◆資料結構
年份：109年
排序：0

四、(一)在一棵高度為 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