樹結構#
樹是一種非線性資料結構，廣泛應用於資料庫索引、檔案系統、編譯器等場景。
本章內容#
- 二元樹基礎：樹的定義、二元樹與二元搜尋樹
- 二元樹走訪：前序、中序、後序與層序走訪
- BST 經典問題：驗證 BST、最近公共祖先、樹的深度
- 紅黑樹：平衡二元搜尋樹的實現原理
- 堆與堆排序：堆的定義、操作與應用
核心概念#
| 結構 | 特點 | 時間複雜度 |
|---|---|---|
| 二元搜尋樹 | 左 < 根 < 右 | 平均 O(log n)，最差 O(n) |
| 紅黑樹 | 近似平衡 | O(log n) |
| 堆 | 完全二元樹 + 堆性質 | 插入/刪除 O(log n) |
學習建議：先掌握二元樹的遞迴走訪，再理解 BST 的性質，最後學習平衡樹和堆的應用。