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

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 をご愛顧いただき、誠にありがとうございます。これについてもっと知りたい場合は、次のリンクをご覧ください。

以下もご興味があるかもしれません:
  • Bツリーの特性の紹介
  • MySQL ハッシュインデックスと B ツリーインデックスの違い
  • SQLite における B ツリー実装の詳細の分析
  • ビットマップインデックスとBツリーインデックスのどちらを使用するかを選択する方法
  • Bツリー挿入プロセスの概要
  • BツリーとB+ツリーの使用に基づくデータ検索とデータベースインデックスの詳細な紹介
  • MySQL Bツリーインデックスとインデックス最適化の概要についての簡単な説明
  • 完全なBツリーアルゴリズムのJava実装コード
  • C言語Bツリーの深い理解

<<:  KVM 仮想マシンのオンライン ホット マイグレーションを実装する方法 (画像とテキスト)

>>:  Vue のレスポンシブ原則と双方向データの詳細な分析

推薦する

Vite2とVue3を使用したウェブサイトの国際化を実現するプロセス全体

目次序文vue-i18nをインストールするロケールの設定getLangs.js の実装i18nインス...

リソースアップロード機能を実現するための SpringBoot+nginx の詳細な例

最近、画像、ビデオ、CSS/JS などの静的リソースを配置するために nginx を使用する方法を学...

MySQLは1億のテストデータを素早く挿入します

目次1. テーブルを作成する1.1 テストテーブルt_userを作成する1.2 一時テーブルの作成2...

MySQL msiバージョンのダウンロードとインストールの初心者向けの詳細なグラフィックチュートリアル

目次1. MySQL msiバージョンをダウンロードする2. インストール3. 環境変数を設定する1...

HTMLを圧縮しない理由はいくつかある

理由は簡単です。 HTML ドキュメントでは、複数の空白文字は 1 つの空白文字と同等です。つまり、...

Linux での VMWare15.5 のインストールに関するチュートリアル

Linux に VMWare をインストールするには、公式 Web サイト https://www....

リモートDockerを使用した統合テスト環境の構築手順

需要背景チームには統合テストが必要であり、そのためには、mysql や rabbitmq などのミド...

Vue+echart で 2 列チャートを実現

この記事では、vue+echart を使って二重列チャートを実現するための具体的なコードを参考までに...

Linux DockerでSpringbootプロジェクトを実行するための詳細な手順

導入: springboot プロジェクトを実行する Docker の構成は実は非常にシンプルで、L...

純粋な CSS3 で蝶が羽ばたく様子を再現する例

純粋なCSS3で蝶が羽ばたく様子を再現。まずはその効果をご覧ください どうですか?効果はかなりいいで...

Linux での MySQL 5.7 の導入とリモート アクセス構成

前書き: 最近、私はパートナーとチームを組んで .NET Core プロジェクトに取り組む予定です。...

MySQL クエリ キャッシュのグラフィカルな説明

目次1. 原則の概要クエリキャッシュシステム変数1. クエリキャッシュを持つ2. クエリキャッシュ制...

MySQLのロック機構に関する最も包括的な説明

目次序文グローバルロック完全なデータベース論理バックアップFTWRL と set global re...

MySQL が起動直後にシャットダウンする問題 (ibdata1 ファイルの破損が原因) に対する完璧な解決策

コンピュータ ルームのサーバー上の mysql がしばらく実行されていたのですが、突然、再起動しても...

Windows 7 で Python 3.4 を使って MySQL データベースを使用する

Python 3.4でMySQLデータベースを使用する詳細なプロセスは次のとおりです。 Window...