樹與層級結構：權力的架構

效率的形狀

在一個扁平的世界（陣列）裡，找東西是件苦差事。妳必須檢查街上的每一棟房子 ($O(N)$)。 在一個層級的世界（樹）裡，找東西很容易。妳先問國家，再問州，然後問城市，最後問街道。只需幾個問題 ($O(\log N)$)，妳就能精準地找到所需。

樹是 「分而治之」 的物理體現。她們透過將問題分解為子問題來解決問題，透過嚴格的父級控制來管理巨大的複雜性。

分支的策略

在本章中，我們將探索不同的樹結構如何解決不同的工程問題：

樹的三大法則

1. 高度即成本： 找到任何東西所需的時間與樹的高度成正比。一棵矮胖的樹（B 樹）比一棵瘦高的樹要快。
2. 平衡是關鍵： 一棵向右傾斜太嚴重的樹本質上就變成了鏈表 ($O(N)$)。AVL 和紅黑樹等演算法的存在純粹是為了保持樹的「平衡」。
3. 從根到葉： 所有邏輯自上而下流動。要解決一個節點的問題，妳通常依賴於她的孩子提供的答案（遞迴）。

小結

在本章中，我們將看到資料庫、檔案系統和記憶體分配器如何使用層級結構來管理世界的資訊。我們將明白，有時候，處理自由的最好方法是施加一點點結構。

讓我們從萬樹之祖開始：二叉搜尋樹。