2-3-4木

2-3-4木は要素と呼ばれる単一の項目としてデータを格納する。 それら要素はノードにまとめられる。ノードは以下のうちどれかである。

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

• 
  2-node
• 
  3-node
• 
  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)と等価である。このことは、赤黒木が平衡する原理が複雑であるため、赤黒木の背後にあるロジックを理解する上で重要である。