跳轉到

第6章 平衡樹#

本章目標#

  • 理解 AVL 樹如何用旋轉維持平衡。
  • 掌握紅黑樹的性質與它在效率上的取捨。
  • 認識為「外存/資料庫」而生的 B 樹。

章前言#

第5章的 BST 有一個致命弱點：插入順序不巧（例如有序插入）就退化成一條鏈，所有操作從 O(log n) 掉到 O(n)。平衡樹（balanced tree） 的使命就是「自動維持形狀」，讓樹高始終保持在 O(log n)，從而保證最壞情況的效能。

維持平衡的手段是旋轉（rotation）——一種局部調整父子指標的手術，能在 O(1) 內改變樹形而不破壞「左小右大」的次序。不同平衡樹的差異在於「何時旋轉、旋轉多少」：

  • AVL 樹：嚴格平衡。每個節點的左右子樹高度差至多 1，一旦失衡立刻旋轉。查詢快（樹更矮），但插入刪除可能引發多次旋轉。
  • 紅黑樹：寬鬆平衡。用「紅/黑著色」保證最長路徑不超過最短路徑的兩倍。旋轉次數少（插入至多 2 次、刪除至多 3 次），修改成本低，因此被 C++ std::map、Java TreeMap、Linux 核心選為標配。
  • B 樹：不為記憶體、而為磁碟設計。每個節點有很多鍵、樹非常矮，一次磁碟讀取就能搬一整頁資料，是資料庫與檔案系統索引的基石。

三者的共同哲學：用少量額外資訊（高度、顏色、鍵數）換取可證明的樹高上界。本章以 AVL 的旋轉為核心訓練指標操作，理解紅黑樹的性質與調整邏輯，最後把視野拉到「每一層都很貴」的磁碟世界，看 B 樹如何把樹高的每一層都變得物超所值。