申論題 - 阿摩線上測驗

申論題資訊

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

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

⑴高度為6之 AVL tree 最多可能有幾個 nodes？最少可能有幾個 nodes？（假設 root 之 h=0）

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

AVL為高度平衡樹，左右子樹高度相差不超過1

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

最少為費氏，最多為完滿二元樹

0 1 2 3 4 5 6 7 8 9 10

0 1 1 2 3 5 8 13 21 34 55

20<=n<=127