データ構造のBツリークエリ
ここでは、Bツリーで検索を実行する方法を説明します。 Bツリー検索は、Bツリークエリとも呼ばれます。以下のようなBツリーがあるとします-
Bツリーの例 −
検索手法は、二分探索木と非常によく似ています。上記のツリーから66を検索するとします。したがって、ルートから開始します。66はルート要素46よりも大きくなります。したがって、ルートの右の子に移動します。次に、適切な子には複数の要素があります。要素はソートされており、[56、81]です。ターゲットキーは56より大きく、81より小さいので、56から81の間にあるサブツリーに入ります。次に、リーフレベルに移動しました。その時点で、要素66があります。
Bツリー内の要素を検索するアルゴリズムを見てみましょう。
BTreeSearch（root、key） −
入力 −木の根、そして見つけるための鍵
出力 −キーを持つノードの値（存在しない場合はnullを返す
）x := Read root if x is an index node, then if there is an object o in x, such that o->key = ‘key’, then return o->val Find the child of x, as x->child[i], whose key range is containing ‘key’ return BTreeSearch(x->child[i], key) else if there is an object o in x, such that o->key = ‘key’, then return o->val, else return null end if end if
-
データ構造へのBツリーの挿入
ここでは、Bツリーへの挿入を実行する方法を説明します。以下のようなBツリーがあるとします- Bツリーの例 − 要素を挿入するための考え方はBSTと非常に似ていますが、いくつかのルールに従う必要があります。各ノードにはm個の子と、m-1個の要素があります。 1つのノードに要素を挿入する場合、2つの状況があります。ノードの要素がm-1未満の場合、新しい要素がノードに直接挿入されます。 m-1個の要素がある場合は、すべての要素と挿入される要素を取得し、それらの中央値を取得します。同じ基準を実行して中央値をそのノードのルートに送信し、2つ作成します。ノードの左半分と右半分からリストを分離する
-
ハーフエッジデータ構造
はじめに テンプレートパラメータまたはハーフエッジデータ構造（HalfedgeDSと略記）のHDSは、平面マップ、多面体、またはその他の方向付け可能な2次元など、頂点、エッジ、および面の入射情報を維持できるエッジ中心のデータ構造として定義されます。ランダムな次元に埋め込まれたサーフェス。各エッジは、反対方向の2つのハーフエッジに分割されます。各ハーフエッジには、1つの入射面と1つの入射頂点が格納されます。各面と各頂点に1つの入射ハーフエッジが格納されます。ハーフエッジデータ構造のバリエーションを減らすと、面のハーフエッジポインタや面の保存など、この情報の一部を削除できます。 ハーフエッジデ