キネティックトーナメント
キネティックトーナメントは、優先度が時間の連続関数として変化する要素のための優先キューとして機能するキネティックデータ構造です。これは、要素間の「トーナメント」に類似した実装で、「勝者」（最大値または最小値の要素）を決定します。証明書は、トーナメントの各「試合」の勝者を強制します。キネティックトーナメントは、通常の優先キュー操作（insert、delete、find-max ）をサポートします。これらの操作は、キネティッククローズドペア（ kinetic closer pair ）などの他のキネティックデータ構造のコンポーネントとしてよく使用されます。
実装
キネティック トーナメントはバイナリ ツリーのような構造で構成され、リーフには要素が含まれ、各内部ノードにはその子ノードの要素のうち大きい方 (または小さい方) が含まれます。したがって、ツリーのルートには、特定の時点での最大 (または最小) の要素が含まれます。構造の有効性は、各ノードで証明書を作成することによって強化されます。証明書は、ノードの要素が 2 つの子のうち大きい方であることを主張します。この証明書が失敗すると、ノードの要素は変更され (もう一方の子の要素になります)、新しい不変条件を表す新しい証明書が作成されます。このノードの要素が親ノードで勝者だった場合、親の要素と証明書も再帰的に更新する必要があります。
分析
これは、O( n ) 空間、応答性が高く、ローカルで、コンパクトかつ効率的なデータ構造です。
- 応答性:証明書の失敗により、古い証明書を置き換える新しい証明書が作成され、イベント キューに入れられる必要があります。また、親ノードの O(log n ) 個の証明書の変更がトリガーされることもあります。証明書の変更ごとに、イベントの優先キューでの削除と挿入の操作が必要です。これらの操作にはそれぞれ O(log n ) 時間がかかるため、応答性、つまり証明書の失敗を処理するために必要な合計時間は です。これは一般に応答性が高いと考えられていますが、証明書の失敗に O(1) の証明書変更で対応するキネティック ヒープなどの他のキネティック優先キューよりも応答性が低くなります。
- 局所性：各要素はO(log n )個の証明書に関係します（例えば、最大要素はルートノードに至るまで、各親ノードの証明書に関係します）。繰り返しますが、これは局所的であると考えられていますが、キネティックヒープはより局所的です。
- コンパクト性:これは非常にコンパクトな構造で、O( n ) 個の証明書 (ツリー内のエッジごとに 1 つ) が含まれます。
- 効率：キネティックヒープは非常に効率的で、内部イベント（証明書の変更）の数は外部イベントの数よりわずかO(log n )倍多くなります。具体的には、各ペアが最大s回交差する時空間軌跡のコレクションの場合、キネティックトーナメントはO(λ s+2 log n )のイベントをO(λ s+2 log 2 n )の時間で処理します。ここで、 λ s+2はDavenport-Schinzelシーケンスです。さらに、挿入と削除はそれぞれO(log n )の証明書の変更を引き起こします。各証明書の変更にはO(log n )の時間がかかり、これはイベントキューの更新を実行するために必要な時間によって決まります。
参考文献
- Basch, J. 1999. キネティックデータ構造. 博士論文, スタンフォード大学コンピュータサイエンス学科. [1]
