フォレスト内でどのくらいの速さでルーツを見つけたり切断したりすることができますか?

根っこの木の森を考えてみましょう。問題は2つの操作をサポートすることです。

  1. disconnect(v):vがフォレスト内のいくつかのツリーのルートである場合、vのすべてのエッジを削除します。
  2. findroot(v):ノードvを含むツリーのルートを探します。

そのような操作には最悪の場合の下限がありますか?特に、両方の操作を$
O(1)$最悪ケース時間でサポートすることは可能ですか?

この問題は、マークされた祖先問題の次のバージョンと同等であることに注意してください。

  1. mark(v):直接親が既にマークされている場合、またはvがルートである場合、ルートツリーのノードvをマークする;
  2. firstmarked(v):vの最も近い祖先を返します。

mark(v)に任意のノードをマークすることができる場合、下限のトレードオフとして知られています。

更新時間$ t_u $とクエリ時間$ t_q $、$$ t_q = Omega( frac {
log)との間の単語サイズbのセルプローブモデルのマークされた祖先問題の新しい下限を提示しますn} { log(t_u b
log n)})$$

     

BRICS RS-98-7 Alstrup他:著名な祖先の問題 h3>

合理的な語サイズ$ b $の場合、このトレードオフは、$
O(1)$最悪ケース時間内で両方の操作をサポートすることが不可能であることを意味します。

Alstrup et
al。関連するさまざまな問題に対して同じトレードオフを証明します。しかし私は自分のバージョンに関するアサーションを見つけることができませんでした。彼らの証明技術は、マークされたノード間の任意のギャップに依存しているようです。

ベストアンサー

この問題は、 “祖先問題を念頭に置いた”という名前を持ち、実際には両方の操作に対して$ O( log log
n)$最悪の解を持つため、問題のジェネリックバージョンの下限を克服します。彼らの解は、ユニオンスプリットファインド構造(および無制限度の木に対する高速LCA)を使ったオイラーの木のツアーに基づいています。

同じ論文は、この境界が厳しいかどうかは未解決の問題であると述べている。

[1] D. Breslauer and G. F. Italiano. Near real-time suffix tree
construction via the fringe marked ancestor problem. Selected
papers from the 18th International Symposium on String Processing
and Information Retrieval (SPIRE 2011)
https://www.sciencedirect.com/science/article/pii/S1570866712001062#br0230

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です