木構造

木構造とは

木構造 (Tree) は、親子関係を持つノードで構成される階層的なデータ構造である。ファイルシステムのディレクトリ、HTML を解析した DOM、コンパイラーが構文を表現する AST、リレーショナルデータベースの インデックス は、いずれも木構造で表される。共通しているのは、全体を順に見ていくのではなく、ノードごとに進む枝を選んで目的の場所まで降りていける点である。

用語

        root (根)
       /    \
     A        B      ← 子ノード (children)
    / \       |
   C   D      E      ← 葉ノード (leaf)

深さと高さは、辺の数で数えるか通過するノードの数で数えるかが文献によって異なり、同じ木でも値が 1 ずれる。計算量やしきい値を議論するときは、どちらの数え方かを先に決めておかないと話が噛み合わない。

走査の順序

木を全部見るには、子へ降りる深さ優先探索と、同じ深さを先に見る幅優先探索がある。深さ優先はノードを訪問する位置によって 3 通りに分かれる。前順 (pre-order) は降りる前、中順 (in-order) は左の部分木を終えた時点、後順 (post-order) は両方の子を終えた後に訪問する。

        8
      /   \
     3     10
    / \      \
   1   6      14
      / \     /
     4   7   13

この二分探索木を走査すると、訪問順は次のようになる。

前順: 8 3 1 6 4 7 10 14 13
中順: 1 3 4 6 7 8 10 13 14
後順: 1 4 7 6 3 13 14 10 8

中順だけがキーの昇順に並ぶ。これは二分探索木の「左 < 親 < 右」という条件から必ず成り立つので、ソート済みの列挙が必要なら中順を選ぶ。前順は親を先に出すので木の複製やシリアライズに向き、後順は子を先に片付けるので領域の解放やディレクトリのサイズ集計に向く。ヒープは兄弟の間に順序を持たないため、中順に走査してもソート順にはならない。二分探索木の走査規則をヒープに当てはめないよう注意する。

木構造の種類

平均 O(log n) が崩れるとき

二分探索木の検索が O(log n) で済むのは木の高さが log n 程度に収まっている場合だけで、これは挿入順が無作為であることを前提にした期待値である。何も平衡化しない二分探索木に 1 から 1000 までを昇順で挿入すると、新しいキーは常に右端へ付くので木は高さ 1000 の一本道になり、検索は先頭から順にたどる連結リストと変わらなくなる。同じ 1000 件を無作為な順で挿入した場合の高さは 25 前後 (log2(1000) は約 10) に収まる。

実務で扱うキーは連番の ID や時刻順のログなど、すでに整列した状態で届くことが多い。つまり最悪ケースは例外的な入力ではなく既定の入力である。だから素の二分探索木ではなく、挿入と削除のたびに形を整える平衡木を使う。

平衡木と B 木の使い分け

AVL 木は左右の部分木の高さの差を 1 以内に保つため木が低くなり、検索の比較回数が少なくて済む。その代わり、条件が厳しいので挿入と削除で回転が多く発生する。赤黒木は平衡条件が緩く、Linux カーネルのドキュメントは、赤黒木は AVL 木に似ているが挿入では最大 2 回、削除では最大 3 回の回転で平衡を回復できるため最悪ケースの応答時間が読みやすく、探索はわずかに遅いが O(log n) に収まると説明している。更新が頻繁で 1 回の操作にかかる時間の上限を抑えたい場面では赤黒木が選ばれ、カーネル内部でも広く使われている。

B 木は別の軸で考える。1 ノードに多数のキーを持たせて枝を増やすと、対数の底が大きくなり木が浅くなる。メモリ内の比較回数を削るためではなく、ノード 1 つをストレージのブロックに対応させ、目的のキーに到達するまでの読み出し回数を減らすための形である。ディスクや SSD の読み出しは 1 回あたりのコストが比較演算より桁違いに大きいため、比較の回数より読み出しの回数を減らす方が効く。データベースのインデックスがほぼ例外なく B 木系なのはこの理由による。インデックスとしての挙動は B-Tree と データベースインデックス で扱う。

判断の目安は、メモリ内で更新が多いなら赤黒木、メモリ内で検索が支配的なら AVL 木、1 ノードがブロック単位の読み書きに対応するなら B 木となる。

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];
  for (let head = 0; head < queue.length; head++) {
    const node = queue[head];
    visit(node.value);
    for (const child of node.children) queue.push(child);
  }
}

幅優先探索の待ち行列で queue.shift() を使う書き方も広く見かけるが、先頭を取り出すたびに残りの要素を詰め直す実装では要素数に比例したコストがかかる。手元の Node.js v26 で 20 万要素を shift() で取り出し切ると 2.7 秒ほどかかり、添字を進める方式では 1 ミリ秒程度で終わった。ノード数が数万を超える木では、待ち行列を配列で持つなら読み出し位置を添字で管理する。

子を待ち行列へ積むときに queue.push(...node.children) と書くのも避けたい。スプレッド構文は配列を引数の並びへ展開するので、子の数が非常に多いノードでは引数の数が実行環境の限界を超える。同じ環境で 30 万要素を一度に展開すると RangeError: Maximum call stack size exceeded になった。件数が読めない配列は for で 1 件ずつ積む方が安全である。

再帰による深さ優先探索は、木が深いと同じ理由で呼び出しの段数の上限に触れる。段数の上限が何で決まるかと、明示的な待ち行列やスタックへの書き換え方は スタック で扱う。

実際の利用例

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 で部分木を取得する。木そのものを保存しているわけではなく、ルートからの経路を文字列にしてソートキーへ埋め込むことで、前方一致の範囲検索が部分木の取得に相当するようにしている。したがって階層の途中に区切り文字と衝突する値が入ると、意図しない部分木まで拾ってしまう。

計算量

平衡木と B 木の O(log n) は最悪ケースでも保証される。ただし B 木の対数の底は 2 ではなくノードあたりの枝の数なので、同じ件数でも木はずっと浅くなる。この深さがストレージの読み出し回数に対応する一方、ノード内で目的のキーを探す比較は計算量の表に現れない。木の全ノードを見る走査は、どの種類でも O(n) である。

つまずきやすい点

• 深さと高さの数え方が辺の数かノードの数かで 1 ずれる。基準を決めずに他の資料の数式と混ぜない。
• 平均 O(log n) は挿入順が無作為な場合の期待値である。連番の ID を昇順に挿入すると一本道になる。
• 中順でソート順になるのは二分探索木の性質であり、ヒープには当てはまらない。
• 待ち行列を配列で持つとき、先頭の取り出しとスプレッド構文の展開はどちらも件数に依存したコストや上限を持つ。
• 再帰の深さには実行環境由来の上限がある。深い木では明示的なスタックへ書き換える。