多方向ツリー（多分木）とは？定義とm-way探索木の条件をわかりやすく解説

多方向ツリー（多分木）の定義

多方向ツリー（multiway tree、多分木）とは、各ノードが2つ以上の子ノードを持つことができる木構造のことです。通常の二分木では子ノードは最大2つに制限されていますが、多方向ツリーではこの制限が緩和され、より柔軟なデータ構造を実現できます。

もし多方向ツリーの子ノード数の最大値が m 個である場合、その木は「次数 m の多方向ツリー（m-way tree、m分木）」と呼ばれます。

ノードの構造

これまで学習してきた他の木構造と同様に、m-way ツリーの各ノードは以下の要素で構成されます。

• キー（鍵）フィールド： 最大 m-1 個
• 子ノードへのポインタ： 最大 m 個

つまり、キーの数よりも常にポインタが1つ多くなる構造になっています。これは、n 個のキーで n+1 個の区間（部分木）を表現できるためです。

次数5の多方向ツリーの例

下図は、次数5（5-way）の多方向ツリーのイメージです。各ノードは最大4つのキーと最大5つの子へのポインタを持つことができます。

m-way 探索木（多方向探索木）とは

m-way ツリーの処理を効率化するために、各ノード内のキーに対して何らかの制約（順序のルール）を課したものを「次数 m の多方向探索木（m-way search tree）」と呼びます。

定義上、m-way 探索木は次の条件をすべて満たす必要があります。

m-way 探索木が満たすべき4つの条件

1. 子ノードとキーフィールドの関係： 各ノードは最大 m 個の子ノードと、最大 m-1 個のキーフィールドを持つ。
2. キーの整列： 各ノード内のキーは昇順に並べられている。
3. 左側の部分木： 先頭から j 番目の子ノードに属するキーは、j 番目のキーよりも小さい。
4. 右側の部分木： 最後の m-j 個の子ノードに属するキーは、j 番目のキーよりも大きい。

まとめ

多方向ツリーは、二分木を一般化したデータ構造であり、特に B木 や B+木 などの平衡多分木の基礎となる重要な概念です。これらの構造はデータベースやファイルシステムのインデックス実装に広く活用されており、大量のデータを効率的に検索・挿入・削除することを可能にしています。m-way 探索木の条件を理解することは、こうした高度なデータ構造を学ぶ第一歩となります。