プログラミング
 Computer >> コンピューター >  >> プログラミング >> プログラミング

データ構造へのBツリーの挿入

ここでは、Bツリーへの挿入を実行する方法を説明します。以下のようなBツリーがあるとします-

Bツリーの例 −

データ構造へのBツリーの挿入

要素を挿入するための考え方はBSTと非常に似ていますが、いくつかのルールに従う必要があります。各ノードにはm個の子と、m-1個の要素があります。 1つのノードに要素を挿入する場合、2つの状況があります。ノードの要素がm-1未満の場合、新しい要素がノードに直接挿入されます。 m-1個の要素がある場合は、すべての要素と挿入される要素を取得し、それらの中央値を取得します。同じ基準を実行して中央値をそのノードのルートに送信し、2つ作成します。ノードの左半分と右半分からリストを分離する

79をツリーに挿入するとします。最初はルートでチェックされますが、これは56より大きいです。次に、右端のサブツリーに移動します。現在は81未満なので、左側のサブツリーに移動します。その後、ルートに挿入されます。現在、3つの要素があります[66、78、79]。中央値は78なので、78が上がり、ルートノードが[79、81]になり、ノードの要素が2つのノードに分割されます。 1つは66を保持し、もう1つは79を保持します。

79を挿入した後のBツリー。

データ構造へのBツリーの挿入

アルゴリズム

BTreeInsert（root、key）−

入力 −ツリーのルートと挿入するキーキーがリストに存在しないと仮定します

x := Read root
if x is full, then
   y := new node
   z := new node
   Locate the middle object oi, stored in x, move the objects to the left of oi in to node y
   Move the object to the right of oi into node z.
   If x is an index node, then move the child pointers accordingly
   x->child[1] := address of y
   x->child[2] := address of z
end if

  1. データ構造における圧縮された四分木と八分木

    圧縮された四分木 細分化されたセルに対応するすべてのノードを格納するときに、多くの空のノードを格納してしまう可能性があります。このようなまばらなツリーのサイズを縮小するには、葉に興味深いデータがあるサブツリー（つまり、「重要なサブツリー」）のみを保存します。ここでも、実際にサイズをさらに縮小することができます。重要なサブツリーのみを考慮する場合、プルーニングプロセスは、中間ノードの次数が2（1つの親と1つの子へのリンク）であるツリー内の長いパスを回避する場合があります。このパスの先頭にノードUを格納し（そして削除されたノードを表すためにいくつかのメタデータをそれに関連付けて）、その最後にルー

  2. ハーフエッジデータ構造

    はじめに テンプレートパラメータまたはハーフエッジデータ構造（HalfedgeDSと略記）のHDSは、平面マップ、多面体、またはその他の方向付け可能な2次元など、頂点、エッジ、および面の入射情報を維持できるエッジ中心のデータ構造として定義されます。ランダムな次元に埋め込まれたサーフェス。各エッジは、反対方向の2つのハーフエッジに分割されます。各ハーフエッジには、1つの入射面と1つの入射頂点が格納されます。各面と各頂点に1つの入射ハーフエッジが格納されます。ハーフエッジデータ構造のバリエーションを減らすと、面のハーフエッジポインタや面の保存など、この情報の一部を削除できます。 ハーフエッジデ