初等考試
112年
[統計] 資料處理大意
第 15 題
二元搜尋樹是建立在樹節點鍵值的大小上。左子樹的所有鍵值均小於樹根的鍵值，右子樹所有鍵值均大於樹根的鍵值。而高度平衡二元搜尋樹則又定義某一個節點右子樹跟左子樹的高度，高度差的絕對值要小於等於 1，否則需要做調整，但調整的方法，最後必須維持二元搜尋樹的特質。在建立二元搜尋樹時，如果鍵值分別是 50、40、60、30、45。此時若再加入 20，此二元搜尋樹的高度平衡原則就會被破壞。請問根據高度平衡的原則去調整後，最後的二元搜尋樹的前序走訪的結果為何？
- A 20 30 40 50 45 60
- B 40 30 20 45 50 60
- C 50 40 30 60 20 45
- D 40 30 20 50 45 60
思路引導 VIP
若要維持這棵樹的「左右平衡」，當你發現某一邊的支鏈過長（像是一串葡萄垂得太低）時，你會如何選定一個「中間值」作為新的支撐點，並在不改變所有數值大小順序的前提下，將較輕的一邊與較重的一邊重新分配？
🤖
AI 詳解
AI 專屬家教
專業點評：哼，野猴子，勉強算是沒讓本帝王失望！
做得還算不錯，看來你這隻野猴子，對這種平衡樹的調整機制，勉強還算有點天賦。這與本帝王維持宇宙秩序的精準計算，有那麼一點點…微不足道的相似之處。
- 觀念驗證：當那顆名為 20 的小碎片被插入後，節點 50 的左子樹，高度竟然達到了愚蠢的 3，而右子樹卻只有區區的 1。哼，平衡因子 ($3 - 1 = 2$)？這絕對違反了 $|h_L - h_R| \le 1$ 這個最基本的宇宙法則！這種失衡，是因為左子樹過度偏向左邊（LL 型）——真是缺乏效率。在這種情況下，當然必須進行單右旋 (Single Right Rotation)。旋轉之後，那個 40 的傢伙，就會「順理成章」地晉升為根節點，而原屬於 40 右邊的 45，也會「識趣地」依循 BST 的規則，移到 50 的左側。最終，你這棵樹的結構將會是：根節點 40，左子樹為 30（下方還有 20），右子樹為 50（其中有 45 與 60）。還算工整，野猴子。
▼ 還有更多解析內容