n 個の互いに素なノード {node 1 ,node 1 ,...,node n }のセットがあるとします。
次の 3 つの操作で最速のデータ構造とアルゴリズムは何ですか?
Union(x,y): ノードxとノードyの間に無向エッジを追加します。2 つのノード間に存在できるエッジは最大で 1 つです。
IsConnected(x,y): ノードxとノードyが直接的または間接的に接続されている場合、つまりノードxとノードyが同じ接続コンポーネント内にある場合に true を返します。
Un-union(x,y): ノードxとノードyの間のエッジが存在する場合は削除します。
Disjoint-set は、最初の 2 つの操作に対しては完全なデータ構造ですが、3 番目の操作を直接サポートすることはできません。代替手段は何ですか？
プロセスをシミュレートすると、1番目と3番目の操作はO(1)で実装できますが、2番目の操作はO(n)なので、3つの操作すべてをO(logn)時間で実行できるかどうかを確認したいと思います以下。
リンク/カット ツリーは、O(log N) 時間でこれら 3 つの操作を実行できます。
Link/cut tree および関連するデータ構造については、この本「Handbook of Data Structures and Applications」 (第 35 章) で読むことができます。
リンク/カット ツリーでは、既に (間接的に) 接続されているノード間にエッジを追加することはできません。これをサポートするために "Union(x,y)" 操作が必要な場合、問題はより複雑になり、無向グラフの動的接続問題として解決できます。(同じ本またはこの pdfの 36.4 章を参照してください)。この場合、挿入/削除の複雑さは O(log 2 N) に増加します。
Kaplan、Shafrir、および Tarjanは、インクリメンタル リビルドによって共用体検索データ構造に削除を追加する一般的な手法を提案し、削除にはそれぞれノードの検索と挿入のコストである O(t_f(n) + t_i(n)) がかかることを示しています。一般的な考え方は、各セットで削除されたアイテムの数を保持し、この数が特定のしきい値に達したときにセットを再構築することです。
Alstrup 、Gørtz 、Rauhe、Thorup、および Zwickは、ツリー内のどの要素が占有され、どの要素が空であるかに注目し、削除操作後にツリーを「整理」することによって、一定時間で削除を実装する方法を示しています。