data-structures - Bツリー挿入の方法

Question

この B ツリーに 3 つの値、60、61、および 62 を挿入しようとしています。ノードがいっぱいで、親が空の場合に値を挿入する方法は理解していますが、親がいっぱいの場合はどうでしょうか。

たとえば、60 と 61 を挿入すると、そのノードがいっぱいになります。親、または親の親を拡張できません (いっぱいであるため)。親の値を変更できますか？挿入前と挿入後の B ツリーのイメージを提供しました。

60、61、62 を挿入しようとしました: ルートの 66 を 62 に変更し、62 を <72 ノードに追加したことに注意してください。これはこれを行う正しい方法ですか？

Answer 1

行った挿入により、通常 B* ツリーと呼ばれるものが得られます。「純粋な」B ツリーでは、ルートがいっぱいになったときに挿入するには、現在のルートを 2 つのノードに分割し、それらの上に新しいルート ノードを作成する必要があります (B ツリーの実装では、ルート ノードが同じ規則に従う必要はありません)。最小数の子孫の他のノードと同じであるため、2 つのみが許可されます)。