data-structures - 2-3 ツリーに挿入する正しい方法はどれですか?

Question

クラスの先生から、2-3 ツリーに挿入するようにという質問がありました。

私が行ったのは上の方法です。そして、彼が欲しかったのは以下の方法です。どちらが正しい方法であるか教えてください。ウェブを調べたところ、両方の方法が表示されています。しかし、なぜ10点を失ったのかはまだわかりません! 助けてくれてありがとう。

Answer 1

まず、2 ～ 3 ツリーにはさまざまなバージョンがあり、混乱を招く可能性があると言うことから始めましょう。実際には、ストアの値が異なるだけです。値をリーフにのみ保存するものもあれば、すべてのノードに値を保存するものもあります。

先生は後者の 2 ～ 3 本の木の定義を使用していると思います。したがって、ツリーの問題は、「ルート」ノードがその子と同じ値を持ち、ノードがその子と同じ値を共有することは決してないことです。ただし、先生が提供したものも真の 2-3 ツリーではないと思います。ノードに 3 つの値が含まれている場合、2-3 ツリーは分割されます。以下が適切な出力になると思います：

ツリーに 4 を追加します。

(4)

ツリーに 7 を追加します。

(4,7)

ツリーに 6 を追加します。

(4,6,7)
*splits*
  (6)
(4) (7)

ルート ノードが 3 つの値を取得すると、1-2 ツリーに分割されます。

8 を挿入する場合:

  (6)
(4) (7,8)

9 を挿入する場合:

   (6)
 (4) (7,8,9)
 *push-up*
   (6,8)
(4) (7) (9)

非ルート ノードが 3 つの値を取得する場合。中間の値を親に押し上げます。値を押し上げると、親が 3 つの値を持つようになり、親が分割されます。