data-structures - 2-3-4 ツリーへの挿入

Question

各データ項目が文字である次の 2-3-4 ツリー (つまり、最小次数が 2 の B ツリー) を考えてみましょう。ツリーの作成には、通常の文字のアルファベット順が使用されます。

上のツリーに G を挿入するとどうなりますか?

私は答えを得ています

しかし、ソリューションキーの答えは

ソリューション キーによって提供される回答を取得する方法を説明できる人はいますか?

Answer 1

不変条件に違反しない限り、操作は技術的に有効です。CLRS の挿入アルゴリズムは途中で分割されるため、ルートが分割されます。

ただし、別の実装では、2 番目の子が空で、最初の子がいっぱいであることを確認する場合があります。つまり、「ローテーション」を実行でき、ルート ノード数は影響を受けません。ローテーションには、L を 2 番目の子に押し下げる (先頭に追加する) ことと、ルート内の L の前の場所に I を引き上げることが含まれます。これで、最初の子には 2 つのエントリしかなく、挿入できます。

使用した CLRS メソッドを使用したアニメーション挿入