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

データ構造の最大HBLTからの任意の要素の削除

最大または最小HBLTから任意のノードを削除することは標準的な操作ではありません。優先キューまたはHBLTの場合。 HBLTからKなどのノードを削除する場合は、次のルールに従う必要があります。

  • Kをルートとするサブツリーをツリーから切り離し、ノードKのサブツリーの融合に置き換えます。

  • Kからルートへのパスからsの値を更新し、必要に応じてこのパスのサブツリーを交換して、HBLTのプロパティを維持します。

sの値をKからrootに更新するには、各ノードの親ポインターが必要です。 s値が変更されていないことがわかると、s値を上位ノードに更新するためのこの操作は停止します。変更されたs値は、昇順を形成する必要があります。各ノードは前のノードより1つ多い必要があるためです。最大s値はO（log n）であり、すべてのs値が正であるため、更新パスで最大O（log n）ノードが検出されます。各ノードは、値を更新するためにO（1）を取ります。したがって、任意のノードを削除する全体的な複雑さはO（log n）

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

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

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

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