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 のレスポンシブ原則と双方向データの詳細な分析

推薦する

MySQL 8.0.18 ハッシュ結合は左/右結合をサポートしていません 左と右の結合の問題

MySQL 8.0.18 では、インデックスが作成されていないフィールドに適用でき、等価値の関連付け...

小規模プログラムへのデータキャッシュ機構の応用と実装

ミニプログラムデータキャッシュ関連知識データ キャッシュ: データをキャッシュして、アプレットを終了...

MySQLの基本的な共通コマンドの概要

目次MySQL の基本的な共通コマンド1. SQL文2. テーブルを作成する3. フィールドのプロパ...

新しい ECMAscript オブジェクト機能の紹介

目次1. オブジェクトのプロパティ1.1 属性表記2. プロパティ名を計算する3.オブジェクトメソッ...

MySQL 8.0 の新機能: ハッシュ結合

MySQL 開発チームは、2019 年 10 月 14 日に MySQL 8.0.18 GA バージ...

Vueデータ監視の原理の詳細な説明

目次1. はじめにII. 監視対象2.1 なぜオブジェクトを監視する必要があるのですか? 2.2 デ...

Vue マウスホイールスクロール切り替えルーティング効果を実装する方法

ルート ルーティング コンポーネント (アプリの下のルート ルーティング コンポーネント。子コンポー...

ウェブページでよく使用される共有コードの完全なリスト(フロントエンドに必須)

コードをコピーコードは次のとおりです。 1. 新浪微博<a href="http:/...

超大型フォントを使用した 40 の Web ページ デザイン

今日の Web デザインでは、非常に大きなフォントが表示される傾向があります。これらのオープンソース...

SpringBoot のパッケージ化と Docker へのアップロード、およびマルチインスタンス デプロイメントの実装に関する簡単な分析 (IDEA バージョン)

最近友人からDockerを触ったことがあるかと聞かれました。あまり自信がなかったので答えられませんで...

レスポンシブレイアウトについて知っておくべきこと

1. はじめにレスポンシブ Web デザインにより、Web サイトは複数のデバイスと複数の画面に同時...

強くお勧めします! Vue 3.2 でシンタックスシュガーを設定する

目次前の1. セットアップ構文シュガーとは何か2. セットアップコンポーネントを使用して自動的に登録...

一般的なブラウザ互換性の問題(概要)

ブラウザの互換性とは、スタイルの互換性 (CSS)、インタラクションの互換性 (JavaScript...

VUE ユニアプリテンプレート構文についての簡単な説明

1.v-bind(略称:)コンポーネント プロパティのデータで定義されたデータ変数を使用するか、コン...

MySQLのワークベンチ例の詳細な説明

MySQL Workbench - モデリングおよび設計ツール1. モデルは、最も効果的で高性能なデ...