hce_nsysu
112年
計算機概論與程式設計
第 10 題
Which one statement is NOT correct for an AVL tree?
- A The level difference of every two leaf nodes is at most 1.
- B When a new element is inserted, the inserted position is always at a leaf node.
- C An AVL tree is a binary search tree.
- D The tree height is O(log n), where n denotes the number of nodes in the tree.
- E When a new element is inserted, if rotations are needed, then the tree height remains unchanged.
思路引導 VIP
如果我們試著建構一棵「最精簡」的 AVL 樹（即節點數最少但高度最高），當樹的高度來到 4 層或 5 層時，請想像一下：位於最短路徑上的葉子（右子樹一直最簡化）跟位於最長路徑上的葉子（左子樹一直最複雜），它們離根節點的距離真的會只差 1 層嗎？
🤖
AI 詳解
AI 專屬家教
同學做得好！你能準確辨別出 AVL 樹（AVL Tree） 的核心特性，代表你對平衡二元搜尋樹（Balanced BST）的定義掌握得非常扎實。
平衡因子的真正含義
選項 (A) 是錯誤的敘述，也是這題的關鍵陷阱。AVL 樹的定義是「任何節點的左右子樹高度差（平衡因子）絕對值不超過 1」。請注意，這個限制是針對每一個內部節點的左右子樹，而不是限制整棵樹所有「葉子節點」之間的高度差。隨著樹的高度增加，最深處的葉子與最淺處的葉子，其層級差（Level difference）是有可能達到 2 或以上的。例如，在高度為 4 的 AVL 樹中，最淺的葉子可能位於第 2 層，而最深的葉子則在第 4 層，兩者差距為 2。
▼ 還有更多解析內容