Bツリーの削除プロセスの紹介

前回の記事 https://www.jb51.net/article/154157.htm では、B ツリーの挿入プロセスを紹介しました。この記事では、B ツリーの削除プロセスを紹介します。

B ツリー内のノードを削除すると、兄弟ノードから要素を借用したり、子ノードと要素を交換したり、ノードをマージしたりすることがあります。

削除の基準として次のツリーを使用します。

まず、このツリーの定義を明確にしましょう。 5次の木です。したがって、各ノードの要素数は 2 ～ 4 になります。

4 つの要素 8、16、15、4 を順番に削除します。

まず 8 を削除します。8 を削除してもツリーのプロパティは破壊されないので、直接削除できます。以下を入手

次に 16 が削除され、13 ノードが 1 つだけ残りますが、ノード内の要素数が 2 ～ 4 であるという要件を満たしません。したがって調整が必要です。ここで、子からノードを借りて 17 を上げると、次の図が得られます。ここでは兄弟ノードからノードを借りることはできません。ノード 3 と 6 から 6 を借りた後、残りの 3 では要件を満たさないためです。さらに、15 人の子供を昇進させることはできません。そうすると、残りの 14 人が要件を満たさなくなるからです。

次に 15 を削除します。15 を削除した後、同じ調整が必要です。調整方法は、18 を増やして 17 を減らして元の 15 の位置に戻すと、次の図のようになります。

次に要素 4 を削除します。4 を削除すると、ノードに残るのは 5 のみとなり、これを調整する必要があります。ただし、兄弟ノードには借りられる余分なノードがないため、ノードのマージが必要です。ノードをマージする方法は多数あり、そのうちの 1 つを選択できます。ここでは、次の図に示すように、シンクする親ノードの 3 を選択し、それを 1、2、5 とマージします。

しかし、この調整により、6 は要件を満たさなくなりました。さらに、ルート以外のノードが 6 つあるが、子ノードが 2 つしかない場合も、要件を満たしません。引き続き調整する必要があります。調整方法は、次の図に示すように、10 をシンクし、6、13、18 とマージしてルート ノードにします。

仕上げる。

要約する

以上がこの記事の全内容です。この記事の内容が皆様の勉強や仕事に何らかの参考学習価値をもたらすことを願います。123WORDPRESS.COM をご愛顧いただき、誠にありがとうございます。これについてもっと知りたい場合は、次のリンクをご覧ください。