木走査の計算量 — DFS、BFS、平衡木
木走査アルゴリズムの時間と空間計算量を理解します：通りがけ順、前順、後順、BFS、平衡BST、ヒープ、トライの操作。
Data Structures
詳細な説明
木走査の時間と空間計算量
基本的な走査計算量
nノード、高さhの木に対して：
| 走査 | 時間 | 空間 |
|---|---|---|
| 通りがけ順 (DFS) | O(n) | O(h) |
| 前順 (DFS) | O(n) | O(h) |
| 後順 (DFS) | O(n) | O(h) |
| レベル順 (BFS) | O(n) | O(w) |
平衡BSTの操作
| 操作 | 時間 |
|---|---|
| 検索 | O(log n) |
| 挿入 | O(log n) |
| 削除 | O(log n) |
ヒープの操作
| 操作 | 時間 |
|---|---|
| 挿入 | O(log n) |
| 最小/最大抽出 | O(log n) |
| ヒープ構築 | O(n) |
トライの操作
長さmの文字列を格納するトライの場合：検索、挿入、削除はすべてO(m)。
ユースケース
木の計算量分析は、データベース設計（B-tree、B+tree）、オートコンプリートシステム（トライ）、タスクスケジューリング（ヒープ）、階層データ処理に不可欠です。