前回の記事 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 をご愛顧いただき、誠にありがとうございます。これについてもっと知りたい場合は、次のリンクをご覧ください。 以下もご興味があるかもしれません:
|
<<: KVM 仮想マシンのオンライン ホット マイグレーションを実装する方法 (画像とテキスト)
>>: Vue のレスポンシブ原則と双方向データの詳細な分析
MySQL 8.0.18 では、インデックスが作成されていないフィールドに適用でき、等価値の関連付け...
ミニプログラムデータキャッシュ関連知識データ キャッシュ: データをキャッシュして、アプレットを終了...
目次MySQL の基本的な共通コマンド1. SQL文2. テーブルを作成する3. フィールドのプロパ...
目次1. オブジェクトのプロパティ1.1 属性表記2. プロパティ名を計算する3.オブジェクトメソッ...
MySQL 開発チームは、2019 年 10 月 14 日に MySQL 8.0.18 GA バージ...
目次1. はじめにII. 監視対象2.1 なぜオブジェクトを監視する必要があるのですか? 2.2 デ...
ルート ルーティング コンポーネント (アプリの下のルート ルーティング コンポーネント。子コンポー...
コードをコピーコードは次のとおりです。 1. 新浪微博<a href="http:/...
今日の Web デザインでは、非常に大きなフォントが表示される傾向があります。これらのオープンソース...
最近友人からDockerを触ったことがあるかと聞かれました。あまり自信がなかったので答えられませんで...
1. はじめにレスポンシブ Web デザインにより、Web サイトは複数のデバイスと複数の画面に同時...
目次前の1. セットアップ構文シュガーとは何か2. セットアップコンポーネントを使用して自動的に登録...
ブラウザの互換性とは、スタイルの互換性 (CSS)、インタラクションの互換性 (JavaScript...
1.v-bind(略称:)コンポーネント プロパティのデータで定義されたデータ変数を使用するか、コン...
MySQL Workbench - モデリングおよび設計ツール1. モデルは、最も効果的で高性能なデ...