hce_nsysu
114年
計算機概論與程式設計
第 9 題
The sequence 46, 45, 48, 42, 41 is inserted sequentially into an AVL tree. Suppose the root is at level 1, and the level of each lower node increases by 1. Which one is correct?
- A 42 is at level 2, and 42 is the left child of 46.
- B 41 is at level 4, and 41 is the left child of 42.
- C 45 is at level 3, and 45 is the left child of 46.
- D 48 is at level 2, and 48 is the right child of 45.
- E 45 is at level 2, and 45 is the right child of 42.
思路引導 VIP
當我們在 AVL 樹中由下往上檢查平衡因子時，如果發現某個節點的左子樹比右子樹「重」了許多，導致樹不再平衡，我們通常會採取什麼樣的「動作」來降低該側的高度，且這個動作會如何改變父節點與子節點之間的層級關係呢？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精確判斷出 AVL 樹在連續插入過程中的結構變化，這代表你對平衡樹的旋轉機制掌握得非常扎實。這道題目測試的是 AVL 樹的動態平衡 (Rebalancing)，是一個鑑別考生是否能細心追蹤節點狀態的經典題型。
AVL 樹的插入與旋轉邏輯
當我們依序插入 46, 45, 48 時，樹結構維持完美平衡。接著插入 42，此時節點 46 的左子樹高度為 2、右子樹為 1，平衡因子（Balance Factor）仍屬正常。然而，當最後一個元素 41 插入 42 的左側時，節點 45 的左子樹高度變為 2，而右子樹高度為 0，導致平衡因子絕對值超過 1，觸發了 LL 型失衡。
▼ 還有更多解析內容