二元搜尋樹照順序插入會歪成一條鏈。自平衡樹靠「旋轉」把樹壓回矮胖,保證永遠 O(log n)。
O(log n),但有個致命傷:如果資料剛好照順序插入(1, 2, 3, 4…),它會退化成一條往右歪的鏈,高度變成 n,查找掉回 O(n) —— 跟沒排序的陣列一樣慢。自平衡樹(AVL、紅黑樹)靠旋轉,在每次插入 / 刪除後自動把樹「轉正」壓矮,保證高度永遠是 O(log n)。旋轉的關鍵是:不破壞 BST 的排序性質(左 < 根 < 右),轉完中序還是排好的。
BST 的致命傷 —— 照順序插入 1,2,3,4,5,每個都往右掛,變成一條鏈(高度 = n),查找退化成 O(n)。
旋轉(rotation)是解藥 —— 在不改變中序(左<根<右)的前提下,把某個節點「轉下去」、讓它的孩子「轉上來」,把樹壓矮。左旋、右旋是最小操作,都是 O(1) 改幾個指標。
轉完排序不變 —— 旋轉前後,中序遍歷(由小到大)一模一樣,只是形狀變矮了。所以查找結果不受影響,只是變快。
平衡因子 bf = 左子樹高 − 右子樹高 —— AVL 規定每個節點的 bf 只能是 −1、0、+1。
插入後沿路檢查 —— 插入新節點後,從它往上更新每個祖先的高度;一旦某節點 |bf| > 1 就旋轉修正。
四種失衡情況 —— LL(左孩子的左邊太重 → 右旋)、RR(右右太重 → 左旋)、LR(左右 → 先左旋再右旋)、RL(右左 → 先右旋再左旋)。
嚴格 → 最矮 → 查最快 —— AVL 把樹壓得很矮,查找最快;代價是插入 / 刪除時旋轉比較頻繁。
用「顏色」維持大致平衡 —— 每個節點染紅或黑,靠 5 條規則讓「最長路徑 ≤ 2 × 最短路徑」,高度仍是 O(log n),但比 AVL 鬆。
5 條規則 —— ①節點非紅即黑 ②根是黑 ③葉子(NIL)當黑 ④紅節點的孩子都黑(不能紅紅相連)⑤任一節點到底下每個葉子,經過的黑節點數相同。
比 AVL 鬆 → 旋轉少 → 改得快 —— 插入 / 刪除用「變色 + 少量旋轉」修復,平均動作比 AVL 少。所以 C++ std::map、Java TreeMap、Linux 核心都用紅黑樹。
log n,不會退化。樹長歪了、一邊太重,就旋轉修剪一下,維持勻稱,不會整棵往一邊倒。
平衡因子就是左右高度差。差超過 1 就旋轉,把重心調回中間。
隨時讓每層書量平均,不管怎麼加書,找一本永遠只翻幾層就到。
兩個情境都依序插入 1, 2, 3, 4, 5。普通 BST 會一路往右歪成鏈(高度 5、查找 O(n));AVL 每次 |bf|>1 失衡(紅色)就旋轉,保持矮胖(高度 3)。節點上方數字是平衡因子 bf(左高−右高),綠色是剛插入的。按「下一步」。
從普通 BST 退化、左右旋、AVL 完整插入、四種失衡情況,到紅黑樹規則、驗證平衡、旋轉不改中序、實務替代方案、AVL vs 紅黑對照,最後小結。
❌ 以為 BST 一定 O(log n) —— 照順序(或近乎排序)插入會退化成 O(n) 的鏈。要保證 log 就得用自平衡樹。
❌ 旋轉搞錯方向 / 破壞排序性質 —— 旋轉後的中序必須還是排好的(左<根<右)。轉完拿中序驗一下最保險。
❌ 手刻紅黑樹的邊界 —— NIL 葉、雙紅、刪除時的「雙黑」修復…情況超多、超容易錯。實務直接用標準庫。
❌ 為了有序硬刻平衡樹 —— Python 用 bisect 維持有序串列、或第三方 sortedcontainers 就很夠,不用自己刻一棵。
map / set 選紅黑樹?把答案打到對話裡,我幫你對。