前回の記事 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 のレスポンシブ原則と双方向データの詳細な分析
目次序文vue-i18nをインストールするロケールの設定getLangs.js の実装i18nインス...
最近、画像、ビデオ、CSS/JS などの静的リソースを配置するために nginx を使用する方法を学...
目次1. テーブルを作成する1.1 テストテーブルt_userを作成する1.2 一時テーブルの作成2...
目次1. MySQL msiバージョンをダウンロードする2. インストール3. 環境変数を設定する1...
理由は簡単です。 HTML ドキュメントでは、複数の空白文字は 1 つの空白文字と同等です。つまり、...
Linux に VMWare をインストールするには、公式 Web サイト https://www....
需要背景チームには統合テストが必要であり、そのためには、mysql や rabbitmq などのミド...
この記事では、vue+echart を使って二重列チャートを実現するための具体的なコードを参考までに...
導入: springboot プロジェクトを実行する Docker の構成は実は非常にシンプルで、L...
純粋なCSS3で蝶が羽ばたく様子を再現。まずはその効果をご覧ください どうですか?効果はかなりいいで...
前書き: 最近、私はパートナーとチームを組んで .NET Core プロジェクトに取り組む予定です。...
目次1. 原則の概要クエリキャッシュシステム変数1. クエリキャッシュを持つ2. クエリキャッシュ制...
目次序文グローバルロック完全なデータベース論理バックアップFTWRL と set global re...
コンピュータ ルームのサーバー上の mysql がしばらく実行されていたのですが、突然、再起動しても...
Python 3.4でMySQLデータベースを使用する詳細なプロセスは次のとおりです。 Window...