在前面兩天，粗淺的介紹了 Binary Tree 與 Balanced Tree，今天更粗淺的介紹一下其他樹，因為本系列只是要做一個拋磚引玉的動作，如果讀者對於資料結構有興趣，建議可以買書來研讀。

樹的資料結構他的應用場景非常廣，比如機器學習的決策樹、極限梯度提升樹，或者是資料庫、檔案系統等應用場景，所以樹的資料結構不是僅僅的理論而已，讀者也許會疑惑說，為什麼好像介紹到樹就沒什麼程式碼，向機器學習的決策樹，它是一種機器學習的演算法，它使用的樹的資料結構去設計，所以光這個演算法要講清楚，就會花很久，也不是本系列的範圍，如果要深入的學樹模型，需要讀者自行找資源學習。

各種樹

接下來，淺淺的介紹一下其他樹還有什麼

B-Tree

B-Tree 是一種多路搜尋樹 (multi-way search tree)，與二元搜尋樹不同的是，它的每個節點可以擁有多於兩個子節點。

特點:

• 節點可以存放多個 key。
• 每個節點的子樹數量 = key 數量 + 1。
• 適合用在「磁碟存取」的場景，因為可以減少磁碟 I/O 次數。

B-Tree 是資料庫索引的基礎，例如 MySQL 就使用 B-Tree 來實作索引。

B+ Tree

B+ Tree 是 B-Tree 的延伸，改進點在於:

• 所有資料都存放在葉節點，非葉節點只用來導航。
• 葉節點之間使用 鏈結串列 串接，支援範圍查詢。

這讓 B+ Tree 在查詢時更有效率，特別是需要「區間搜尋」的情境。

紅黑樹 (Red-Black Tree)

紅黑樹是一種自平衡二元搜尋樹 (self-balancing BST)**，常用於準程式庫的實作，例如:

• Java 的 TreeMap、TreeSet

紅黑樹的規則:

• 節點要嘛是紅色，要嘛是黑色。
• 根節點一定是黑色。
• 紅節點的子節點必須是黑色 (不能連續兩個紅色)。
• 從根到每個葉節點的路徑，黑色節點數必須相同。

這些限制保證了樹的高度維持在 $O(\log n)$，因此搜尋、插入、刪除都能保證在 $O(\log n)$ 完成。

Trie 樹 (Prefix Tree)

Trie，又叫字典樹，專門用來處理字串集合的問題。

特點：

• 每個節點代表一個字元。
• 從根到某一節點的路徑，對應到一個字串前綴。
• 適合用來做前綴搜尋 (prefix search)或自動完成 (autocomplete)。

簡單範例：假設要存 cat, car, dog:

• 根節點分出 c 和 d。
• c 節點再分出 a → t 與 a → r。
• d 節點分出 o → g。

這樣就能快速判斷是否存在某個前綴。

Segment Tree (線段樹)

線段樹是一種用於區間查詢 (range query) 的資料結構，例如:

• 查詢一段區間的總和
• 查詢最大值或最小值

時間複雜度:

• 建立: $O(n)$
• 單點更新: $O(\log n)$
• 區間查詢: $O(\log n)$

應用:

• 區間和查詢 (Range Sum Query)
• 區間最值查詢 (Range Minimum/Maximum Query)
• 遊戲伺服器的即時排名、區間統計

Fenwick Tree (Binary Indexed Tree, BIT)

Fenwick Tree 是 Segment Tree 的輕量化版本，主要用於前綴和 (prefix sum) 的計算。

• 記憶體使用比 Segment Tree 更省。
• 適合處理動態更新的累加問題。

常見應用:

• 線上排名系統
• 股票成交量累積統計
• 動態區間加總

Huffman Tree (哈夫曼樹)

Huffman Tree 是一種 最佳前綴編碼樹，用於壓縮演算法 (例如 zip、JPEG、MP3）。

基本原理:

1. 統計字元出現頻率。
2. 頻率最低的兩個節點合併，直到剩下一棵樹。
3. 左邊編碼 0，右邊編碼 1，得到最短編碼。

這樣能讓常見字元使用短編碼，達到壓縮效果。

總語

我們花了幾天介紹了樹的世界。和前面線性資料結構相比，樹的結構更靈活，能夠更高效地處理複雜的資料查詢與更新。

• Binary Tree: 樹的基本型態，每個節點最多兩個子節點。
• Balanced Tree: 解決了二元搜尋樹退化成鏈表的問題，讓操作維持在 $O(\log n)$。
• B-Tree / B+ Tree: 多路搜尋樹，應用於資料庫索引與檔案系統。
• 紅黑樹: 自平衡 BST，標準程式庫常用的底層結構。
• Trie: 專門處理字串前綴的結構，應用於搜尋與自動補全。
• Segment Tree / Fenwick Tree: 處理區間查詢與更新問題。
• Huffman Tree: 應用於壓縮編碼。

這些樹各自有專門的應用場景，但背後的核心思想是相通的: 透過階層結構來提升查詢與操作的效率。

樹結構是資料結構中最具代表性的非線性結構，它們在理論與實務上都佔據了核心地位。從最基本的二元樹到複雜的 B+ Tree 與 Segment Tree，每一種樹都是針對特定問題的解法。