データ構造におけるブレント法
このセクションでは、オープンアドレスハッシュに関連するブレント法とは何かを説明します。この方法はヒューリスティックです。これにより、ハッシュテーブルでの検索が成功するまでの平均時間が最小限に抑えられます。
この方法は元々ダブルハッシュ手法に適用されていましたが、線形および二次プロービングなどのオープンアドレッシング手法に使用できます。要素xの経過時間は、オープンアドレス法のハッシュテーブルに格納され、最小値iであり、xはA [x iに配置されます。 ]
ブレント法は、すべての要素の合計年齢を最小化しようとします。要素xを挿入すると、いくつかの手順が実行されます-A [x iのようなiの最小値が見つかります ]は空です。これは、標準のオープンアドレス法でxが挿入される場所です。ここで、A [x i-2に格納されている1つの要素yについて考えます。 ]。 yj =x i-2 であるため、この要素はそこに格納されます 、j≥0の値の場合。配列の位置A [y j + 1かどうかを確認します。 ]が空の場合、yを場所A [y j + 1に移動します ]、xを場所A [x i-2に格納します ]。
通常のオープンアドレス法と比較して、これにより合計年齢が1減少します。一般に、ブレント法は2≤k≤iごとに、配列エントリA [x i-kをチェックします。 ]を確認するには、要素yが格納されている場合、そこにA [y j + 1のいずれかに移動できます。 ]、A [y j + 2 ]、。 。 。、A [y j + k-1 ]、x用のスペースを確保します。
-
データ構造のB+ツリー
ここでは、B+ツリーとは何かを確認します。 B +ツリーは、Bツリーの拡張バージョンです。このツリーは、Bツリーのより良い挿入、削除、および検索をサポートします。 Bツリー、キー、およびレコード値は、内部ノードとリーフノードに格納されます。 B +ツリーレコードでは、リーフノードに保存できます。内部ノードはキー値のみを保存します。 B+ツリーのリーフノードもリンクリストのようにリンクされています B+ツリーの例 − これは、検索、挿入、削除などの基本的な操作をサポートします。各ノードで、アイテムが並べ替えられます。位置iの要素には、その前後に子があります。したがって、以前に痛んだ
-
ハーフエッジデータ構造
はじめに テンプレートパラメータまたはハーフエッジデータ構造（HalfedgeDSと略記）のHDSは、平面マップ、多面体、またはその他の方向付け可能な2次元など、頂点、エッジ、および面の入射情報を維持できるエッジ中心のデータ構造として定義されます。ランダムな次元に埋め込まれたサーフェス。各エッジは、反対方向の2つのハーフエッジに分割されます。各ハーフエッジには、1つの入射面と1つの入射頂点が格納されます。各面と各頂点に1つの入射ハーフエッジが格納されます。ハーフエッジデータ構造のバリエーションを減らすと、面のハーフエッジポインタや面の保存など、この情報の一部を削除できます。 ハーフエッジデ