キネティックトーナメント

キネティックトーナメントは、時間の連続関数として優先度が変化する要素の優先キューとして機能するキネティック データ構造です。これは、要素間の「トーナメント」に類似して実装され、「勝者」(最大要素または最小要素) を決定し、証明書によってトーナメントの各「試合」の勝者を決定します。これは、通常の優先キュー操作 (挿入、削除、最大検索) をサポートします。これらは、キネティック クローズド ペアなどの他のキネティック データ構造のコンポーネントとしてよく使用されます。

キネティック トーナメントは、二分木のような構造で構成されます。二分木では、葉に要素が含まれ、各内部ノードには、その子ノードの要素のうち大きい方 (または小さい方) が含まれます。したがって、ツリーのルートには、特定の時点での最大 (または最小) の要素が含まれます。構造の有効性は、各ノードで証明書を作成することによって強制されます。証明書は、ノードの要素が 2 つの子のうち大きい方であることを主張します。この証明書が失敗すると、ノードの要素が変更され (他の子の要素に変更)、新しい不変条件を表す新しい証明書が作成されます。このノードの要素が親ノードで勝者だった場合、親の要素と証明書も再帰的に更新する必要があります。

これは、O( n ) スペース、応答性、ローカル性、コンパクト性、効率性に優れたデータ構造です。

• 応答性:証明書の失敗により、古い証明書を置き換える新しい証明書が作成され、イベント キューに入れられる必要があります。また、親ノードの O(log n ) 証明書の変更がトリガーされる場合もあります。証明書の変更ごとに、イベントの優先キューでの削除と挿入の操作が必要です。これらの操作にはそれぞれ O(log n ) 時間がかかるため、応答性、つまり証明書の失敗を処理するために必要な合計時間は です。これは一般に応答性が高いと考えられていますが、証明書の失敗に O(1) の証明書変更で対応するキネティック ヒープなどの他のキネティック優先キューよりも応答性が低くなります。${\displaystyle O(\lg ^{2}n)}$
• 局所性:各要素は O(log n ) 個の証明書に関係します(たとえば、最大要素はルート ノードまでの各親の証明書に関係します)。これも局所的であると考えられますが、キネティック ヒープはより局所的です。
• コンパクト性:これは非常にコンパクトな構造で、O( n ) 個の証明書 (ツリー内のエッジごとに 1 つずつ) が含まれます。
• 効率:キネティック ヒープは非常に効率的で、内部イベント(証明書の変更)の数は外部イベントの数よりO(log n )倍だけ多くなります。具体的には、各ペアが最大s回交差する空間時間軌跡のコレクションの場合、キネティック トーナメントはO(λ _s+2 log n )のイベントをO(λ _s+2 log ² n )時間 で処理します ( λ _s+2はDavenport-Schinzel シーケンス) 。さらに、挿入と削除はそれぞれ O(log n ) の証明書の変更を引き起こします。各証明書の変更には O(log n ) の時間がかかり、これはイベント キューの更新を実行するために必要な時間によって決まります。

• Basch, J. 1999. キネティックデータ構造。博士論文、スタンフォード大学コンピュータサイエンス学部。[1]