樹

樹是從線性結構邁出的第一大步。陣列或鏈結串列把資料排成一條直線，而樹則會分叉：每個元素（稱為節點）可以指向它下方的多個節點。這自然地刻劃了層次關係——檔案系統、組織結構圖、棋局中的著法——一切從單一起點向外發散的事物。

這套術語值得一次學會、終身受用。最頂端唯一的節點稱為根。指向其他節點的節點是父節點，被它指向的是子節點。沒有子節點的節點叫葉子。樹的高度是從根到某個葉子最長路徑上的邊數，而某個節點的深度是它到根的距離。關鍵在於：樹中沒有環——你順著子節點一直走，永遠不會回到出發點；除根以外的每個節點都恰好有一個父節點。

樹之所以重要，是因為它的分叉形狀能讓操作變快。如果一棵樹保持枝繁葉茂、又矮又寬，而不是又細又長，那麼你只需大約 O(log n) 步就能到達任意節點，而不是 O(n)——這正是讓二分搜尋變快的同一個對數級好處。本節中的大多數結構（搜尋樹、堆積、字典樹）都是為保持這種形狀、保證這種速度而專門設計的特殊樹。