推奨されます, 2019

エディターズチョイス

Bツリーとバイナリツリーの違い

Bツリーとバイナリツリーは、非線形データ構造のタイプです。 用語は似ているように見えますが、すべての面で異なります。 RAMのアクセス速度はディスクよりはるかに高いため、レコードまたはデータがディスクではなくRAMに格納される場合は、バイナリツリーが使用されます。 一方、Bツリーは、データがディスクに格納されるときに使用され、ツリーの高さを減らし、ノード内の分岐を増やすことによってアクセス時間を短縮します。

Bツリーとバイナリツリーのもう1つの違いは、Bツリーはその子ノードをすべて同じレベルに持つ必要があるのに対し、バイナリツリーにはそのような制約がないことです。 二分木は最大2つの部分木またはノードを持つことができるのに対し、B木ではM個の部分木またはノードを持つことはできず、MはB木の次数である。

比較表

比較基準
Bツリー
二分木
本質的な制約ノードは最大M個の子ノードを持つことができます(Mはツリーの次数です)。1つのノードは最大2つのサブツリーを持つことができます。
中古
データがディスクに保存されるときに使用されます。レコードやデータがRAMに保存されるときに使用されます。
木の高さlog M N(mはM-wayツリーの位数)log 2 N
応用多くのDBMSにおけるコード索引付けデータ構造。コード最適化、ハフマンコーディングなど

Bツリーの定義

Bツリーはバランスの取れたMウェイツリーで、バランスソートツリーとも呼ばれます。 これは、ノードがinorder traversalに基づいて編成されている二分探索木に似ています。 Bツリーの空間複雑度はO(n)です。 挿入と削除の時間の複雑さはO(log n)です。

Bツリーに当てはまる必要がある特定の条件があります。

  • 木の高さはできるだけ最小になるようにしてください。
  • 木の葉の上には、空のサブツリーがあってはいけません。
  • 木の葉は同じ高さになければなりません。
  • すべてのノードは、離脱ノードを除いて、最小数の子を持つべきです。

M次のB木の性質

  • 各ノードは、最大M個の子と最小M / 2個の子、または2から最大の任意の数の子を持つことができます。
  • 各ノードは、最大M-1個のキーを持つ子より1つ少ないキーを持ちます。
  • キーの配置はノード内で特定の順序になっています。 キーの左側に存在するサブツリー内のすべてのキーはキーの先行操作であり、キーの右側に存在するものは後続操作と呼ばれます。
  • フルノードの挿入時に、ツリーは2つの部分に分割され、中央値を持つキーが親ノードに挿入されます。
  • ノードが削除されると、マージ操作が行われます。

二分木の定義

二分木は、その子ノードに対して最大2つのポインタを持つことができる木構造です。 つまり、ノードが持つことができる最高度は2で、ゼロ度または1度のノードもあり得るということです。

厳密な二分木、完全二分木、拡張二分木など、二分木の特定の変形がある。

  • 厳密に二分木とは、各非終端ノードが左部分木と右部分木を持っていなければならない木です。
  • ツリーが各レベルに2 i個のノードを持つという条件を満たす場合、そのツリーはComplete Binaryツリーと呼ばれます。ここで、iはレベルです。
  • スレッド化されたバイナリは、0のノード数または2の数のノードからなるバイナリツリーです。

トラバーサルテクニック

ツリー走査は、各ノードが系統的に1回だけ訪れたツリーデータ構造に対して実行される最も頻繁な操作の1つです。

  • 順序付け - このツリートラバーサルでは、左のサブツリーが再帰的に訪問され、次にルートノードが訪問され、最後の右でサブツリーが訪問されます。
  • Preorer - このツリーのトラバースでは、ルートノードが最初に訪問され、次に左側のサブツリーと最後の右側のサブツリーに移動します。
  • ポストオーダー - この技法は、左のサブツリーを訪問し、次に右のサブツリーを訪問し、最後のルートノードを訪問します。

Bツリーとバイナリツリーの主な違い

  1. Bツリーでは、非終端ノードが持つことができる子ノードの最大数はMです。ここでMはBツリーの次数です。 一方、バイナリツリーは、最大2つのサブツリーまたは子ノードを持つことができます。
  2. Bツリーはデータがディスクに格納されるときに使用され、バイナリツリーはデータがRAMのような高速メモリに格納されるときに使用されます。
  3. Bツリーの他の適用分野は、DBMSにおけるコード索引付けデータ構造であり、対照的に、バイナリツリーは、コード最適化、ハフマン符号化などにおいて使用される。
  4. Bツリーの最大の高さはlog M Nです(Mはツリーの次数です)。 それとは対照的に、二分木の最大の高さはlog 2 Nです(Nはノードの数で、baseは2のため2です)。

結論

Bツリーはバイナリおよびバイナリサーチツリーで使用されています。この主な理由は、CPUが高帯域幅チャネルでキャッシュに接続され、CPUが低帯域幅チャネルでディスクに接続されているメモリ階層です。 レコードがRAMに格納されている(小さいものと速い)場合はバイナリツリーが使用され、レコードがディスクに格納される場合(大きいものと遅い)はBツリーが使用されます。 そのため、バイナリツリーの代わりにBツリーを使用すると、分岐係数が高くなり、ツリーの高さが減少するため、アクセス時間が大幅に短縮されます。

Top