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

データ構造における動的フィンガー検索ツリー

  • 動的な指検索データ構造は、指検索に加えて、指で指定された位置で要素の挿入と削除も実行する必要があります。
  • 指検索ツリーは、O（1）の可動指のみが維持されると仮定して、O（log d）時間での指検索とO（1）時間での更新をサポートするBツリーのバリアントとして定義されます。
  • 指のd位置を移動するには、O（log d）時間が必要です。
  • フィンガーサーチツリー（つまり、AVLツリー、赤黒木）構造は、固定された一定数のフィンガーを考慮するか、償却された一定時間の更新のみをサポートします。
  • 任意の数の指をサポートし、最悪の場合の更新を伴う構造が作成されました。
  • 最悪の場合O（1）時間の任意の位置での更新をサポートするが、O（log n）時間の検索のみをサポートする検索ツリー。
  • O（log d）時間の検索とO（log d n）時間の挿入と削除をサポートする構造。
  • 指探索木は、最悪の場合の一定時間の挿入とO（log d n）時間の削除を消費します。
  • レベルリンクされた（2,4）-ツリーのスペース効率の良い代替ソリューションによると、（2,4）-ツリーと同じパフォーマンスコストで進めることができる1本の指が許可されます。このソリューションでは、レベルリンクと親ポインタは必要ありません。代わりに、指を効率的にトラバースできるようにするために、指用に特別なO（log n）スペースデータ構造handが作成されます。
  • スプレーツリーは、償却されたO（log n）時間での検索、挿入、および削除をサポートする自己調整型二分探索ツリーのクラスとして定義されます。そのスプレー木は、効率的な指検索ツリーとして実装できます。
  • O（n）の初期化コストを考えると、スプレーツリー内の以前のアクセスから距離dでのアクセスの償却コストはO（log d）であり、アクセスは検索、挿入、および削除で構成されます。
  • ステートメントは、常に最後にアクセスされた要素を指す1本の指が存在する場合にのみ実装されることに注意してください。
  • 上記のすべての構造は、要素で許可される唯一の操作が2つの要素の比較であるポインターマシンに適用できます。
  • ランダムアクセスマシンの計算モデル（RAM）の場合、一定の更新時間とO（log d）検索時間でフィンガー検索ツリーが作成されます。この結果は、小さなツリー構造を表にすることで達成されますが、要素の比較のみを実行します。

  1. データ構造のBSPツリー

    コンピュータサイエンスでは、超平面をパーティションとして実装することにより、空間を2つの凸集合に再帰的に分割するために、バイナリ空間分割（BSP）と呼ばれる方法が実装されています。この細分化のプロセスにより、BSPツリーと呼ばれるツリーデータ構造の形式で領域内のオブジェクトが表現されます。 バイナリ空間分割は、1969年に3Dコンピュータグラフィックスのコンテキストで発明されました。BSPツリーの構造により、レンダリングに役立つシーン内のオブジェクトに関する空間情報が可能になります。たとえば、オブジェクトは前から後ろに並べられます。すばやくアクセスできるように、特定の場所にいる視聴者を尊重し

  2. データ構造の範囲ツリー

    範囲ツリーは、ポイントのリストを保持するための順序付けられたツリーデータ構造として定義されます。これにより、特定の範囲内のすべてのポイントを効率的に取得でき、通常は2次元以上で実装されます。 O（log d のクエリ時間が速いことを除いて、kdツリーと同じです。 n + k）が、O（n log d-1 のストレージが悪い n）、dはスペースの次元を示し、nはツリー内のポイントの数を示し、kは特定のクエリで取得されたポイントの数を示します。範囲ツリーは、間隔ツリーで区別できます。ポイントを格納して特定の範囲内のポイントを効率的に取得できるようにする代わりに、間隔ツリーは間隔を保存し、特定のポ