Bツリー挿入プロセスの概要

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

挿入プロセスとツリー構築プロセスは本質的に同じです。つまり、どちらも挿入操作を実行し、挿入後に B ツリーを調整します。

B ツリーの次数を 5 に設定します。キーシーケンス {1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15} を使用して B ツリーを構築します。

ツリーの次数は 5 なので、各ノードには最大 5 つの子ノードがあり、各ノードのキーワードの数は 3 ～ 4 です。

したがって、最初のステップは、1、2、6、7 をノードとして挿入することです。

次に 11 を挿入すると、1、2、6、7、11 が得られます。ノード数が 4 を超えるため、ノードを分割する必要があります。中間のノード 6 を選択し、それを親ノードに昇格すると、次のようになります。

新しく挿入されたノードは常にリーフノードに現れるというルールがあります。次に4、8、13を直接挿入すると、次のようになります。

次に10を挿入します。

右下のノードには 5 つの要素があり、最大数の 4 を超えているため、分割する必要があり、中央のノード 10 は 6 と一緒に昇格されて次の構造を形成します。

次に5、17、9、16を挿入すると次のようになります。

次に20を挿入します。20を挿入した後、右下のノードの要素数は5になり、最大数の4を超えます。したがって、次の構造を形成するには16を増やす必要があります。

次に、3、12、14、18、19 を挿入して次の構造を形成します。

次に 15 を挿入すると、13 がルート ノードに昇格されます。この時点で、ルート ノードには 5 つのノードがあります。次に、ルート ノードの 10 が再び昇格され、次の構造が形成されます。

仕上げる。

要約する

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