前処理

Question

チェックとO 2つのツリーのノードが関連しているかどうかを確認し（祖先/子孫）（1）2つのツリーのノードが関連している場合（すなわち、祖先 - 子孫）

• （1）Oでそれを解決します時間とO（N）スペース（ノードN =＃）
• 前処理は、それをだ

が許可されています。私は下の私の解決策（アプローチ）に行くつもりです。あなた自身を最初に考えたければ、やめてください。私は予約注文を行うことを決めた前処理のために

---

（再帰的に子供、その後、最初のルートを通過）し、各ノードにラベルを与えます。

ラベルを詳細に説明します。各ラベルは、 "1,2,1,4,5"のようなコンマで区切られた自然数で構成されます。このシーケンスの長さは（ノードの深さ+1）に等しくなります。例えば。ルートのラベルは "1"、ルートの子はラベル "1,1"、 "1,2"、 "1,3"などを持ちます。次レベルのノードは "1,1,1" ... "1,2,1"、 "1,2,2" ...

ノードの "注文番号"は、親の子リスト内の「このノードの1から始まるインデックス」。

共通ルール：ノードのラベルはノードの親ラベルとコンマで構成され、ノードの「注文番号」で構成されます。

O（1）に2つのノードが関連している場合、そのノードのラベルがもう一方のラベルの「接頭辞」であるかどうかを確認します。そのようなラベルがO（N）スペースを占有すると考えられるかどうかはわかりませんが。

修正を含む批評家または代替のアプローチが必要です。

Answer 1

各頂点のプリオーダー番号と注文番号を保存し、このファクトを使用すると、O（n）前処理時間、O（n）スペース、O（1）クエリー時間で実行できます。

ツリーTの二つの与えられたノードxとyについて

、xはxはTの先行順走査で、ポストオーダートラバースのY 後のYの前に発生した場合にのみならYと の祖先です。

（このページから：http://www.cs.arizona.edu/xiss/numbering.htm）

何が最悪の場合にはやったことはdが高いノードの深さであり、従ってO（1）ではありませんシータ（D）です。スペースもO（n）ではありません。

Answer 2

最低の共通祖先アルゴリズム（少なくともオフライン）があります。たとえば、hereのように見えます。また、tarjan's offline LCA algorithmをご覧ください。これらの記事では、事前にLCAを実施するペアを知っておく必要があります。オンラインの線形時間事前計算アルゴリズムもあると思いますが、それらは非常に複雑です。例えば、範囲の最小問合せ問題に対する線形事前計算時間アルゴリズムがある。私の知る限り、この解決策はLCAの問題を2回通過しました。このアルゴリズムの問​​題は、O（n * log（n））アルゴリズムよりも実際に速くなるためには莫大な入力が必要となるような大きな定数があることです。

O（n * log（n））の追加メモリを必要とし、一定の時間内に再び応答する方法はずっと簡単です。

これが役に立ちます。

Answer 3

ツリー内のノードにn/2個の子があるツリーを考えると、ラベルを設定する実行時間はO（n * n）と同じくらい高くなります。だからこのラベル付けスキームはうまくいきません....