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

データ構造における最大WBLT操作

ここでは、さまざまなMax-WBLT操作について説明します。 HBLTには、挿入、削除、初期化などのさまざまな操作があります。それらもWBLTと非常によく似ています。ただし、融合操作は1回の上から下へのパスで実行できます。

WBLTではシングルパスメルド操作が可能です。 w値を見つけることができるので、途中で。必要に応じて、w値を更新し、サブツリーを交換できます。 HBLTの場合、ツリーに到達する途中でsの値を見つけることができません。

融合は1回の上から下へのパスで実行できるため、挿入と削除も効率的に実行できます。したがって、挿入と削除は一定の係数で高速になります。ここでは、任意に配置されたノードKの要素をO（log n）時間で削除することはできません。その背後にある理由は、ノードKにO（n）個の祖先があり、そのw値が更新される可能性があるためです。したがって、これはマージ可能なダブルエンド優先キューアプリケーションには適していません。


  1. データ構造における2つの最大HBLTの融合

    メルド戦略は、再帰を使用して簡単に実行できます。 AとBが2つのHBLTであり、それらが融合するとします。それらの1つが空の場合は、最終結果として別の1つを作成するだけです。空のHBLTがない場合は、2つのルートの要素を比較する必要があります。より大きな要素を持つルートは、融合したHBLTのルートになります。 Aのルートが大きいとします。そして、それはその左側のサブツリーがLです。Cが最大HBLTであると仮定します。これは、AとHBLT Bの右側のサブツリーをマージした結果です。最終的なHBLTは、ルートとしてAを持ち、サブツリーとしてLとCを持ちます。 Lのs値がCの値よりも小さい場合、C

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

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