Bツリー：非葉ノードを削除しますか？

Question

イムBツリーを勉強したり、本の中で彼らがいることを言った：

1. キーkがノードXおよびXである場合には、xから鍵Kを削除し、葉です。

2. 鍵kがノードxにあり、xが内部ノードである場合は、次のようにします。

a。ノードx内のkに先行する子yが少なくともt個のキーを有する場合、yを根源とするサブツリー内のkの先行キーk 'を見つける。 k 'を再帰的に削除し、xをk'で置き換える。 （k 'を見つけること、それを削除することは、単一の下向きパスで実行することができる）。

b。対称的に、ノードxのkに続く子zが少なくともt個の鍵を有する場合、zを根源とするサブツリーにおいてkの後続k 'を見つける。 k 'を再帰的に削除し、xをk'で置き換える。 （k 'を見つけてそれを削除することは、単一の下向きパスで実行することができる）

c。それ以外の場合、yとzの両方にt-1個のキーしかない場合は、kとzのすべてをyにマージして、xとzの両方のポインタを失い、yには2t-1のキーが含まれます。そして、zを解放し、yからkを再帰的に削除する。

私の質問は次のとおりです。ケース2.a。 誰かが私に説明することができますか？再帰的にkを削除し、xをkで置き換えます。

よろしくお願いいたします。

Answer 1

あなたは= 4度のトンでB木があるとします。

26,  49,  60 
27,31,34,36  51,55,56,58 

と仮定y = [27,31,34,36]、x = [51,55,56,58]はリーフノードではありません、あなたはキーk = 51を削除したいです。 K = 49を親ノードの鍵とし、xとyを分割します。

サブツリーyの右端のキーk'あるkの前身を探す（この例では37と48の間の整数が含まれている可能性があり、k' = 40を言います）。 k = K = 49と​​を設定し、k'を再帰的に削除します（実際にノードがリーフの場合の削除手順の最初のケースです）。結果のbツリーは次のようになります

26,  40,  60 
27,31,34,36  49,55,56,58