データ構造入門：K分木（K-aryツリー）の基本概念と具体例をわかりやすく解説
K分木（K-aryツリー）とは
この記事では、データ構造のひとつであるK分木（K-aryツリー）について解説します。
K分木とは、根付き木（rooted tree）の一種で、各ノードが持つことのできる子ノードの数が最大でk個に制限された木構造です。この「k」の値によって、木の形状や性質が大きく変わります。
二分木・三分木との関係
k = 2 の場合、この木は二分木（バイナリツリー）として知られています。同様に、k = 3 の場合は三分木（ターナリーツリー）と呼ばれます。
つまり、二分木や三分木はK分木の特殊なケースであり、K分木はこれらを一般化した概念だと言えます。この一般化により、データベースのB木やファイルシステムなど、さまざまな用途に応じた柔軟な木構造を設計することが可能になります。
K分木の例
上図の例を見てみましょう。
- 最上部には根（ルート）ノードがあり、このルートには4つの子ノードが接続されています。
- さらに、ルートの各子ノードもそれぞれ子を持っています。
具体的には、以下のような構造になっています。
- 1番目の子：3つの子ノードを持つ
- 2番目の子：子ノードなし（葉ノード）
- 3番目の子：2つの子ノードを持つ
- 4番目の子：4つの子ノードを持つ
このように、K分木では「各ノードが最大k個までの子を持てる」というルールの範囲内で、実際に持つ子の数はノードごとに異なっていても問題ありません。上の例では k = 4 となっているため、どのノードも最大4個までの子を持つことができます。
-
データ構造の範囲ツリー(レンジツリー)とは?仕組み・kd-treeとの違い・構築方法を解説
範囲ツリー(range tree)は、点の集合を格納するための順序付き木構造として定義されるデータ構造です。最大の特徴は、指定された範囲内に存在するすべての点を効率的に取得できる点にあり、実務では主に2次元以上の空間で実装されます。範囲ツリーはkd-tree(kd木)とよく似た構造を持っていますが、両者には明確なトレードオフがあります。範囲ツリーはクエリ時間が O(logd n + k) とkd-treeより高速である一方、必要な記憶領域は O(n logd-1 n) と大きくなります。ここで、d は空間の次元数、n は木に格納されている点の総数、k は1回のクエリで取得される点の数を表します
-
データ構造：仮想木におけるスプレー操作のアルゴリズム
仮想木（Virtual Tree）では、一部の辺は実線（solid）として扱われ、その他の辺は破線（dashed）として扱われます。通常のスプレー操作は、実線で構成される木（solid tree）の内部でのみ実行されます。仮想木内のノード y でスプレーを行うには、以下に示す手法が用いられます。 このアルゴリズムは、木を3回走査し（各パスで1回ずつ）、その都度木を書き換えていきます。第1パスでは、ノード y から開始して実線の木内でのみスプレーを行うことで、y から木全体の根までの経路が破線に変わります。続いて、スプライシング（splicing）によってこの経路を実線に変換します。最後にノード