2-3-4木
2-3-4木（2-3-4き、テンプレート:Lang-en-short）または2-4木は計算機科学の用語であり、4次のB木（テンプレート:Lang-en-short）と同じである。
一般に2-3-4木はB木のように辞書として使うことができる平衡木の一種である。探索、挿入、削除をO(log n)で行うことができる。ここでnは木の要素数である。
2-3-4木は木の操作において多くの特別なケースが存在するので大半のプログラミング言語において比較的実装が難しい。赤黒木(red-black tree)の方が実装が簡単で代わりに用いられる傾向がある。
背景
2-3-4木は要素と呼ばれる単一の項目としてデータを格納する。 それら要素はノードにまとめられる。ノードは以下のうちどれかである。
- 2-nodeの場合は、1つの要素と2つの子をもつ。
- 3-nodeの場合は、2つの要素と3つの子をもつ。
- 4-nodeの場合は、3つの要素と4つの子をもつ。
ファイル:2-3-4 tree 2-node.png 2-node |
ファイル:2-3-4-tree 3-node.png 3-node |
ファイル:2-3-4 tree 4-node.png 4-node |
それぞれの子は部分2-3-4木である (空もありうる)。根ノードは親を持たないノードであり、全ての他のノードはそこから到達できるので、探索の開始点になる。葉は子を持たないノードである。
B木同様、2-3-4木も順序つきである。そのためそれぞれの要素は、左の要素および左の部分木と比較して等しいかより大きくなければならない。従って、それぞれの子は左と右の要素で示される閉区間となる。
2-3-4木を解析するときは、内部ノードと外部ノードを明確に区別しなければならない。内部ノードとは上記の例において木の中にあり、a、b、そしてcを含んでいるノードである。外部ノードとは木の中にないノードであり、次のノードの位置として示されているものである。それらは上記の例では、p、q、r、そしてsを含む。2-3-4木は次の二つの性質を維持しなければならず、他の平衡木と明確に区別される。
- 各内部ノードは4つより多い子ノードを持たない
- すべての外部ノードは同じ深さを持たなければならない (これは、その木の中の任意の外部ノードへ到達するために、根ノードから同じ個数のノードを探索すればよい事を意味する)
2-3-4木は赤黒木のisometry、すなわち等価なデータ構造である。言い換えると、任意の2-3-4木に対して，それと同じ順序でデータ要素を持つ赤黒木が少なくとも一つ存在する。2-3-4木に対する挿入および削除は、赤黒木における色替え(color-flipping)および回転(rotation)と等価である。このことは、赤黒木が平衡する原理が複雑であるため、赤黒木の背後にあるロジックを理解する上で重要である。
挿入
削除
赤黒木への視覚的な変換
2-3-4木は、少なくとも一種類以上の赤黒木に変換可能である。具体的には3つの要素を持つノードの場合は真ん中の値を要素にもつ黒ノードを作成し、それ以外の要素を作成したノードの子ノードとして生成し色を赤とする。2つの要素を持つノードの場合は、どちらかの要素を持つノードを作成し色を黒とし、もう片方の要素はそのノードの子ノードとし色を赤とする。最後に葉以外の全てのノードが子どもを2つ持つように黒の葉を付与することで赤黒木を作成できる。このとき赤黒木の定義は自動的に満たされていることとなる。
また2-3-4木における挿入および削除の各操作は、赤黒木におけるカラー・フリッピングおよび回転の各操作にあたる。
.svg){kind=link}