11

2つのツリーノードが関連しているかどうかを確認します（つまり、祖先-子孫）

  • O（N）空間（N =ノード数）を使用して、O（1）時間で解きます
  • 前処理が許可されています

それでおしまい。以下の私の解決策（アプローチ）に行きます。最初に自分のことを考えたいのなら、やめてください。

前処理のために、私は事前注文を行い（最初にルートを再帰的に通過し、次に子を通過する）、各ノードにラベルを付けることにしました。

ラベルについて詳しく説明します。各ラベルは、「1,2,1,4,5」のようなコンマ区切りの自然数で構成されます。このシーケンスの長さは、（ノードの深さ+ 1）に等しくなります。たとえば、ルートのラベルが「1」の場合、ルートの子には「1,1」、「1,2」、「1,3」などのラベルが付けられます。次のレベルのノードには「1,1,1」のようなラベルが付けられます。 "、" 1,1,2 "、...、" 1,2,1 "、" 1,2,2 "、..。

ノードの「注文番号」は、その親の子リストの「このノードの1から始まるインデックス」であると想定します。

一般的なルール：ノードのラベルは、親ラベルの後にコンマとノードの「注文番号」が続くもので構成されます。

したがって、O（1）で2つのノードが関連しているかどうか（つまり、祖先-子孫）に答えるために、一方のラベルが他方のラベルの「プレフィックス」であるかどうかを確認します。そのようなラベルがO（N）スペースを占めると見なすことができるかどうかはわかりませんが。

修正または代替アプローチを使用する批評家が予想されます。

4

3 に答える 3

19

各頂点の事前注文番号と事後注文番号を保存し、次の事実を使用すると、O（n）前処理時間とO（n）空間で、O（1）クエリ時間でそれを行うことができます。

ツリーTの2つの与えられたノードxおよびyについて、xがTのプレオーダートラバーサルでyの前に発生し、ポストオーダートラバーサルでyの後に発生する場合にのみ、xはyの祖先です。

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

最悪の場合に行ったことはTheta（d）です。ここで、dは上位ノードの深さであり、O（1）ではありません。スペースもO（n）ではありません。

于 2012-04-25T07:21:58.273 に答える
1

ツリー内のノードにn/2の子があるツリーを考えると（たとえば）、ラベルを設定する実行時間はO（n * n）と同じくらい長くなります。したがって、このラベル付けスキームは機能しません...。

于 2013-09-26T14:33:11.277 に答える
0

線形時間の最も低い共通祖先アルゴリズムがあります（少なくともオフライン）。たとえば、ここを見てください。タージャンのオフラインLCAアルゴリズムもご覧ください。これらの記事では、LCAを実行するペアを事前に知っている必要があることに注意してください。オンラインの線形時間事前計算時間アルゴリズムもあると思いますが、それらは非常に複雑です。たとえば、範囲最小クエリ問題には線形事前計算時間アルゴリズムがあります。私が覚えている限り、このソリューションはLCA問題を2回通過しました。アルゴリズムの問​​題は、定数が非常に大きいため、O（n * log（n））アルゴリズムよりも実際に高速であるために膨大な入力が必要になることです。

O（n * log（n））の追加メモリを必要とし、一定時間で応答する、はるかに単純なアプローチがあります。

お役に立てれば。

于 2012-04-25T07:23:38.897 に答える