arrow_back 返回看板列表
monetization_on懸賞金幣:35
資訊工程系未解決2026-06-08 03:00
BST（二元搜尋樹）與 AVL 樹在極端輸入下的效能差異？
person提問學生: 資工小菜雞
大家午安，我想請問：如果我們依序輸入遞增數值（例如：1, 2, 3, 4, 5...）到一般的 BST 和 AVL 樹中。
1. BST 會退化成什麼樣子？搜尋複雜度會變成多少？
2. AVL 樹是如何解決這個問題的？旋轉（Rotation）發生的時機是？
1. BST 會退化成什麼樣子？搜尋複雜度會變成多少？
2. AVL 樹是如何解決這個問題的？旋轉（Rotation）發生的時機是？
#資料結構#二元搜尋樹#AVL樹
account_tree 留言樹狀結構
點擊節點可跳至對應留言。
forum 學霸解答與留言回覆
edit_square 撰寫您的解答 / 回覆
登入 後即可發表解答。
2. AVL 樹是高度平衡的二元搜尋樹，要求任何節點的左右子樹高度差（平衡因子 Balance Factor, BF）絕對值不超過 1。
當輸入 3 時，節點 1 的右子樹高度為 2，左子樹為 0，BF=0−2=−2 失去了平衡。
因為是插在右子樹的右邊（Right-Right），所以對節點 1 進行**左旋（Left Rotation）**：
讓節點 2 變成新的根節點，1 變成 2 的左子樹，3 留在 2 的右子樹。樹高恢復為 1，搜尋時間維持在 O(logN)！