← All notes
LeetCode Cycle 09：平衡 BST、Heap、Trie 三種結構優化
樹進階的命題只有一條——「為了避開最壞情況，要在結構上付什麼代價」。平衡 BST 為了防退化付旋轉成本；heap 放棄全序換 O(log n) 插入；trie 為了字串前綴付 O(M×S) 空間。Cycle 09 後半把這三個取捨講清。內部使用。
Tree basics 把三種 traversal 拆完，但有個東西沒講透：BST 在最壞情況退化成 linked list（單鏈），O(log n) 變回 O(n)[^1]。Cycle 09 的後半要回答的命題是：
為了避開「退化成單鏈」這條最壞路徑，要在結構上付什麼代價？
三個答案：
- 平衡 BST（AVL / Red-Black）：付旋轉成本，保 O(log n)
- Heap：放棄全序、只保 root，付完全樹約束換 O(log n) 插入 / 取極值
- Trie：付 O(M×S) 空間，換 O(M) 字串前綴查詢（與 n 無關）
面試官追問樹題的時候，這三個取捨是「資深可問」與「junior 只會背題」的分水嶺。