|
2-3-4木（2-3-4き、）または2-4木は計算機科学の用語であり、4次のB木（）と同じである。 一般に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木である (空もありうる)。根ノードは親を持たないノードであり、全ての他のノードはそこから到達できるので、探索の開始点になる。葉は子を持たないノードである。 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)と等価である。このことは、赤黒木が平衡する原理が複雑であるため、赤黒木の背後にあるロジックを理解する上で重要である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「2-3-4木」の詳細全文を読む スポンサード リンク
|