木構造
親子関係を持つノードで構成される階層的なデータ構造
データ構造アルゴリズム
木構造とは
木構造 (Tree) は、親子関係を持つノードで構成される階層的なデータ構造である。ファイルシステム、DOM、AST、データベースのインデックス (B-Tree) など、あらゆる場面で使われている。
用語
root (根)
/ \
A B ← 子ノード (children)
/ \ |
C D E ← 葉ノード (leaf)
| 用語 | 説明 |
|---|---|
| ルート (root) | 最上位のノード |
| 葉 (leaf) | 子を持たないノード |
| 深さ (depth) | ルートからの距離 |
| 高さ (height) | 葉までの最大距離 |
| 部分木 (subtree) | あるノードを根とする木 |
木構造の種類
| 種類 | 特徴 | 用途 |
|---|---|---|
| 二分木 | 各ノードが最大 2 つの子 | 基本的な木構造 |
| 二分探索木 (BST) | 左 < 親 < 右 | 検索、ソート |
| B-Tree | 多分岐、バランス保証 | データベースインデックス |
| Trie | 文字列の接頭辞で分岐 | オートコンプリート |
| ヒープ | 親 ≤ 子 (最小ヒープ) | 優先度キュー |
TypeScript での実装
interface TreeNode<T> {
value: T;
children: TreeNode<T>[];
}
// 深さ優先探索 (DFS)
function dfs<T>(node: TreeNode<T>, visit: (v: T) => void) {
visit(node.value);
for (const child of node.children) dfs(child, visit);
}
// 幅優先探索 (BFS)
function bfs<T>(root: TreeNode<T>, visit: (v: T) => void) {
const queue = [root];
while (queue.length > 0) {
const node = queue.shift()!;
visit(node.value);
queue.push(...node.children);
}
}
実際の利用例
DOM ツリー
<html> ← ルート
<body> ← 子ノード
<div> ← 子ノード
<p>Hello</p> ← 葉ノード
</div>
</body>
</html>
ファイルシステム
/
├── home/
│ └── user/
│ ├── documents/
│ └── pictures/
└── etc/
└── nginx/
DynamoDB のシングルテーブル設計
PK | SK | data
ORG#1 | ORG#1 | { name: "Acme" }
ORG#1 | TEAM#eng | { name: "Engineering" }
ORG#1 | TEAM#eng#USER#1 | { name: "Alice" }
階層構造を SK のプレフィックスで表現し、begins_with で部分木を取得する。
計算量
| 操作 | BST (平均) | BST (最悪) | B-Tree |
|---|---|---|---|
| 検索 | O(log n) | O(n) | O(log n) |
| 挿入 | O(log n) | O(n) | O(log n) |
| 削除 | O(log n) | O(n) | O(log n) |
さらに掘り下げるなら関連書籍が参考になる。