2-3-4木

出典: フリー百科事典『ウィキペディア（Wikipedia）』

2-3-4木(2-3-4き英 en:2-3-4 tree)は、4次のB木(en:B-tree)と同じである。

一般に2,3,4木はB木のように辞書として使うことができる平衡木の一種である。探索,挿入,削除をO(n)で行うことができる。ここでnは木の要素数である。

2-3-4木は木の操作において多くの特別なケースが存在するので大半のプログラミング言語において比較的実装が難しい。赤黒木(en:Red-black tree)の方が実装が簡単で代わりに用いられる傾向がある。

[編集] 背景

2-3-4木の要素はまとまるとノードになる。ノードは以下のうちどれかである。

2-nodeの場合は、1つの要素と2つの子をもつ。
3-nodeの場合は、2つの要素と3つの子をもつ。
4-nodeの場合は、3つの要素と4つの子をもつ。

a 2-node

a 3-node

a 4-node

それぞれの子も2-3-4木になっている。根ノードは親を持たないノードであり、全ての他のノードはそこから到達できるので、探索の開始点になる。葉は子を持たないノードである。

B木同様、2-3-4木も順序つきであり、それぞれの要素は左の要素と左の部分木と等しいかより大きくなければならない。従ってそれぞれの子は左と右の要素で示される閉区間となる。

2-3-4木は赤黒木のisometryで、これは等価なデータ構造であることを意味している。言い換えると、任意の2-3-4木には少なくとも1つ以上の同じ並びにデータが配置された赤黒木が存在するということである。2-3-4木に対する挿入と削除は赤黒木における色替え(color-flipping)と回転(rotation)と等価である。このことは赤黒木の背後にあるロジックを理解する上で重要である。