2-3-4木

2-3-4木とは

2-3-4木（2-3-4 tree）は、計算機科学におけるデータ構造の一つで、4次のB木とも呼ばれます。これは、辞書のように使用できる平衡木であり、データの探索、挿入、削除といった操作を効率的に行うことができます。これらの操作は、木の要素数をnとしたとき、O(log n)の時間計算量で実行可能です。要素数が増加しても、処理時間が大幅に増大することがないため、安定したパフォーマンスを維持できます。

構造

2-3-4木は、要素と呼ばれる単一のデータを格納します。これらの要素はノードにまとめられ、ノードは以下の3種類に分類されます。

2-ノード: 1つの要素と2つの子ノードを持ちます。
3-ノード: 2つの要素と3つの子ノードを持ちます。
4-ノード: 3つの要素と4つの子ノードを持ちます。

各ノードの子は、それぞれ部分的な2-3-4木となります（空の場合もあり）。根ノードは親を持たない特別なノードで、すべてのノードに到達するための出発点となります。葉ノードは子を持たないノードです。

2-3-4木は、B木と同様に順序付けられています。各要素は、左側の要素や左部分木よりも大きく（または等しく）なければなりません。これにより、各子ノードは、左右の要素によって定義される区間を表現します。

内部ノードと外部ノード

2-3-4木を解析する際には、内部ノードと外部ノードを区別することが重要です。

内部ノード: 木構造の中に存在するノード（上記の例のa,b,cなど）。
外部ノード: 木構造の中には存在しないノードで、次のノードの位置を示している（上記の例のp,q,r,sなど）。

2-3-4木は以下の2つの重要な性質を持ちます。

1. 各内部ノードは4つより多くの子ノードを持たない。
2. すべての外部ノードは同じ深さを持つ（根ノードから任意の外部ノードへ到達するまでのノード数が同じ）。

赤黒木との関連性

2-3-4木は、赤黒木と等価なデータ構造です。つまり、任意の2-3-4木に対して、同じ順序でデータ要素を持つ赤黒木が少なくとも一つ存在します。2-3-4木における挿入や削除の操作は、赤黒木における色の変更（color-flipping）や回転（rotation）操作に対応します。赤黒木が平衡を保つためのメカニズムは複雑ですが、2-3-4木との関連性を理解することで、赤黒木の動作原理をより深く理解することができます。

赤黒木への変換

2-3-4木は、特定の規則に従うことで、赤黒木に変換できます。具体的には、以下のようになります。

3つの要素を持つノード: 中央の要素を黒ノードとし、残りの要素を赤ノードとしてその子ノードにします。
2つの要素を持つノード: どちらかの要素を黒ノードとし、もう片方の要素を赤ノードとしてその子ノードにします。
すべての子ノードが2つ持つように黒の葉を追加します。

この変換により、赤黒木の定義が自動的に満たされるようになります。

まとめ

2-3-4木は、効率的なデータ操作を可能にする平衡木です。実装はやや難しいですが、赤黒木との関連性を理解することで、より複雑なデータ構造の理解を深めるための基礎となります。

関連項目

2-3木

外部リンク

Animation of a 2-3-4 Tree
Java Applet showing an 2-3-4 Tree
B-Tree animation (Java Applet)

もう一度検索