2

以前、平衡二分探索木で後継者を見つけることについて質問を投稿しました。現在、B ツリー (ノードが 2 つ以上の子を持つことができる) について調べていますが、B ツリーでキーの後継者を見つけるにはどうすればよいのでしょうか? 一般的に、通常の BST と同じでしょうか?

前もって感謝します。

4

1 に答える 1

1

ロジックは似ていますが、複数の子が存在する可能性があるという事実を処理するために少し変更する必要があります。

前と同様に、値のルックアップを行います。次に、ブロック内にその値より大きい値がある場合は、それらの最小値を見つけます。これらの値の間にサブツリーに子がある場合は、そのサブツリーに降りて、そこで最小値を取ります。それ以外の場合は、最初のステップで見つけた値を後継者とします。

後継者がいない場合は、後継者ができるまでツリーをバックアップします。次に、上記の手順を使用してサクセサを取得します。

お役に立てれば！

于 2013-10-31T06:23:57.760 に答える