民國109年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第38題
欲將數值資料1、2、3、4 建立二元搜尋樹,則最多可構成多少種高度平衡二元樹(AVL 樹)?
題目
欲將數值資料1、2、3、4 建立二元搜尋樹,則最多可構成多少種高度平衡二元樹(AVL 樹)?
- (1) 14
- (2) 10
- (3) 6
- (4) 4
官方答案
(4) 4
解析
AVL 樹要求每個節點左右子樹的高度差絕對值不超過 1。四個鍵值中，根若取 1 或 4，另一側會有 3 個節點形成高度 2 的子樹，而空側沒有節點，高度差超過 1，因此根只能是 2 或 3。根為 2 時，左子樹固定為 1，右子樹 {3,4} 有「3 的右子為 4」及「4 的左子為 3」兩種；根為 3 時左右對稱，也有兩種。合計 2+2=4 種。14 是未加平衡限制的全部二元搜尋樹數，即 Catalan 數 C4。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。