data-structures - 2-3-4 数字のリストから木を生成する

Question

番号 50、40、60、30、70 のリストがあります。これらを空の 2-3-4 ツリーに挿入するとします。これらの数字のどれがツリーの親ルートで、その理由は? 広告掲載順ですか、数字の大きさですか。数字のリストを与えるときに 234Tree を描画できるようにしたいと考えています。最初に親ルートとして使用するものがわからないため、それができないようです。簡単に言えば、このツリーの親ルートを指定する要因は何ですか。

Answer 1

バランスの取れたツリー データ構造では、通常、ルート要素には、追加されたアイテムの中央値に近い値が含まれます。ただし、通常、ツリーは完全にバランスが取れているわけではないため、ルートに正確な中央値がない場合があります。ツリーの正確な構造は、値が追加された順序に依存する場合があります。

あなたの質問では、2-3-4 ツリーに 5 つの項目を追加することに言及しています。これは常に 2 レベルのツリー構造になりますが、正確な構造は要素が追加される順序によって異なります。質問に記載されている順序でそれらを追加すると、次のようになります。

root -> <50>
       /    \
  <30,40>  <60,70>

しかし、要素を別の順序で追加すると、ルートに 40 または 60、リーフ ノードの 1 つに 50 を持つことができます。