B ツリーは一般的なデータ構造です。彼と一緒にB+ツリーがあります。 ここで、概念を明確にする必要があります。 B ツリー、B ツリー、B+ ツリーの違いは何ですか?彼らの関係は何ですか? 実際のところ、データ構造には B ツリーと B+ ツリーの 2 種類しかありません。 B ツリーは B ツリーとも呼ばれることがあります。これらは同じものです。 B ツリーの中央にある「-」は「マイナス記号」ではなくハイフンであることに注意してください。英語では B-Tree であり、中国語では B-tree と翻訳されます。翻訳者によってはハイフン「-」を含めることを好むため、B-tree となり、一部の読者は B-tree を B-minus tree と誤読します。 B ツリーを紹介する前に、まず重要な概念である「順序」について見てみましょう。 ツリーの順序は、ツリー内の各ノードの子ノードの最大数です。つまり、一部のノードに 2 つの子ノードがあり、一部のノードに 4 つの子ノードがあり、子ノードの最大数が 5 の場合、ツリーの順序は 5 になります。 この観点から見ると、二分木の次数は 2 です。 次に、B ツリーの主な特性を紹介します。 B ツリーの次数は m であると仮定します。 m 次 B ツリーは、空のツリーか、次のプロパティを持つツリーのいずれかです。 1. 各ノードには最大 m 個の子ノードがあります。少なくとも m/2 (切り上げ) 個のノードがあります。または、次のように表現することもできます: m/2 <= 子ノードの数 <= m。ただし、ルート ノードは例外です。ルート ノードには少なくとも 2 つの子ノードを含めることができます。 2. 各ノードの子ノードの数は、ノードに格納されているキーワードの数より 1 多くなります。つまり、ノードに k 個のキーワードが格納されている場合、ノードには k + 1 個の子ノード (サブツリー) が存在することになります。 3. 各ノード内のk個のキーワードは小さいものから大きいものの順に並べられ、k1、k2、k3、…kkとして記録されます。すると、ノードには p0、p1、p2、... pk と表記される k+1 個のポインターが存在します。さらに、次の図に示すように、p3 が指す子ノード内のすべての要素は k3 より大きく、k4 より小さくなります。これも比較的理解しやすく、覚えやすいです。各ポインタ p は、キーワード k 間のギャップに正確に配置されます。したがって、ギャップのポインタが指す子ノードの要素の値は、当然、ポインタの左側の要素よりも大きく、ポインタの右側の要素よりも小さくなります。 4. B ツリーは厳密にバランスのとれた検索ツリーであり、左と右のサブツリーの高さは等しくなります。リーフ ノードは同じレイヤーにあり、空のノードで表すことができます。 B ツリーの例: 要約する 以上がこの記事の全内容です。この記事の内容が皆様の勉強や仕事に何らかの参考学習価値をもたらすことを願います。123WORDPRESS.COM をご愛顧いただき、誠にありがとうございます。これについてもっと知りたい場合は、次のリンクをご覧ください。 以下もご興味があるかもしれません:
|
<<: ローカルストレージにブール型の値を保存する際の落とし穴を解決する
概要プロトタイプ パターンは、プロトタイプ インスタンスによって作成されるオブジェクトの型を指し、こ...
先ほど MySQL パスワードを設定したのに、外食したり荷物を受け取ったりするときにパスワードを忘れ...
最近、たまたまこの小さな要件に遭遇しました。昔、JS を使用してこれを処理したことを覚えていますが、...
/************************ * Linux メモリ管理 *********...
注: nginxはbrew経由でインストールされますウェブサイトのルートディレクトリ: /opt/h...
Web デザインは科学であると同時に芸術でもあります。 Web デザイン作業は、半分は適切なプログラ...
目次開発環境用のDocker-ceをインストールする開発環境用のDocker-composeをインス...
Linux システムで .sh ファイルを実行する方法は 2 つあります。たとえば、ルート ディレク...
序文add_header は、headers モジュールで定義されたディレクティブです。名前が示すよ...
開発中に以下の状況が発見されました。 (1) ファイルが.jspファイル拡張子で保存されている場合、...
この記事では、主に HTML のサンプル コードを紹介し、次のように交互に色を変更する方法を共有しま...
目次1. 複数ページの違い2. SPAとMPA 3. Vue Cli スキャフォールディング構成1....
トークンの有効期限が切れたら、ページを更新します。ページの読み込み時にバックエンドに複数のリクエスト...
事前に一言:突然、複数のドメイン名のアクセスを https に転送するというタスクを受け取りました。...
最近、同社は、下図に示すように、h5 ページ操作を完了するという要件を提示しました。 ネットで入手で...