演算法圖鑑
資料結構 · 7 個細項

Tree樹

樹是「一個節點底下有更多節點」的結構，天生對應遞迴。從二元樹的走訪開始，二元搜尋樹把「有序」和「動態插入」結合，字典樹處理字串，線段樹與樹狀陣列則處理區間查詢。

為什麼要學 Tree

現實中的應用
檔案系統與網頁 DOM

資料夾裡有資料夾、HTML 標籤裡有標籤。計算資料夾大小、渲染網頁、序列化 JSON，都是樹的走訪。

→ 對應課程：Traversal
資料庫索引與有序集合

MySQL 的索引是 B-tree，Redis 的 sorted set、Java 的 TreeMap 是平衡搜尋樹。要「快速找到、還要保持有序」就靠 BST 家族。

→ 對應課程：BST
搜尋列的自動補全

打「alg」就跳出「algorithm」，字典樹沿著字母一路走下去，每一層就是下一個字元。

→ 對應課程：Trie
即時排行與區間統計

十萬筆資料不斷更新，還要隨時問「第 1000 到 2000 筆的總和」。線段樹與樹狀陣列讓查詢與更新都是對數時間。

→ 對應課程：Segment Tree

細項

7 篇
#演算法難度
01Binary Tree Basics 二元樹基礎高度、深度、完全二元樹、陣列表示用在：堆積、表達式樹、決策樹的共同基礎02Traversal 前中後序與層序走訪遞迴與迭代兩種寫法，層序用佇列用在：算資料夾大小、序列化樹、運算式求值03BST 二元搜尋樹插入、刪除、驗證、中序即有序用在：有序集合、範圍查詢、資料庫索引的原型04Balanced BST 平衡樹概念AVL 與紅黑樹為什麼能保證 O(log n)，講概念不實作用在：TreeMap、std::map、資料庫索引05Trie 字典樹每層一個字元，共用前綴用在：自動補全、拼字檢查、IP 路由表06Segment Tree 線段樹區間查詢與單點更新，懶標記做區間更新用在：區間和／區間最大值的動態查詢07Fenwick Tree (BIT) 樹狀陣列用位元技巧做前綴和的動態版本用在：線段樹的輕量替代、逆序對計數