問題タブ [least-common-ancestor]

そこで、 RMQ (Range Minimum Query) に関するこのTopCoder チュートリアルを読んだところ、大きな疑問が生じました。

彼がアプローチを紹介したセクションで、私が今までに理解できることは次のとおりです。

(全体のアプローチは、実際にはスパース テーブル (ST) アルゴリズム、 LCA から RMQ への削減、およびRMQからLCA への削減で導入された方法論を使用します)

配列 A[N] が与えられた場合、それをデカルト ツリーに変換する必要があります。したがって、RMQ 問題を LCA (Lowest Common Ancestor) 問題にします。後で、配列 A の単純化されたバージョンを取得して、制限付き RMQ 問題にすることができます。

つまり、基本的には 2 つの変換です。したがって、RMQ から LCA への最初の部分は単純です。スタックを使用することで、O(n) 時間で変換を行うことができ、配列 T[N] が得られます。ここで、T[i] は要素 i の親です。そしてツリーが完成。

しかし、ここで私が理解できないことがあります。O(n) アプローチには配列 where が必要であり、その配列はチュートリアルのLCA から RMQ への削減|A[i] - A[i-1]| = 1セクションで紹介されています。これには、このツリーのオイラー ツアーが含まれます。しかし、変換の最終結果でこれをどのように達成できますか? それに対する私のアプローチは線形ではないため、このアプローチでは悪いと見なす必要があります。これに対する線形アプローチは何でしょうか?

更新：私を混乱させるポイント

ツリーの写真:

オイラー ツアーでは、DFS (深さ優先検索) と同様に、各ノードの子を知る必要がありますが、T[n] には各要素のルートのみがあり、子はありません。

ツリー内の 2 つのノードの最も一般的でない祖先を取得しようとしています。試してみましたが、問題はif one node is the descendant node for otherLCAを取得できなかったことです。
私はそれを解決しようとしましたが、それは子孫ノードに対してのみ機能していました。これを進める方法がわかりませんでした。

これは私のバイナリ ツリーの実装です (これは Lca のコードではなく、バイナリ ツリーをどのように構築したかを理解するためのバイナリ ツリーの通常の実装です)

今私の質問は、たとえば、2 つのノードが右のサブツリーと左のサブツリーの両方で同じである場合、2 つのノードの最も低い共通の祖先を見つける方法です。

では、これの最下位共通祖先は何であるべきか

私は以下の質問でニック・ジョンソンの答えを理解しましたが、上記のタイプのツリーを行う方法を理解していません

二分木で2つのノードの最も低い共通の祖先を見つける方法は?

二分木でLCAを求める方法についてのインタビューで質問されました。私は自分の考えに答えます。結局、インタビュアーはscala fold関数でできると言っていました...しかし、方法がわからない、何かアイデアはありますか?

least common Ancestorで 2 つnodesのを見つけるためのこのコードがありますbinary tree。時間計算量は だと思いますO(log n)。しかし、専門家の意見が必要です。このコードは私の入力ではかなりうまく機能しますが、徹底的にテストしたかどうかはわかりません。

ここにコードがあります

私はLCAアルゴリズムについて話している記事に入りました.コードは簡単です http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

しかし、アルゴリズムの時間の複雑さをどのように計算するのか疑問に思っていましたが、誰か助けてもらえますか?

ルートのないツリーに LCA を実装しようとしています。ツリー (循環のない接続された無向グラフ) と、いくつかのルートと 2 つの頂点に対する LCA に関する一連のクエリを指定しました。特定のクエリごとにルートが異なる可能性があるため、最初に任意のルートのツリーを前処理するアルゴリズムを使用することはできません。

これまでのところ、DFS を使用して両方の頂点からルートへのパスを見つけようとしましたが、分岐する場所を確認しましたが、やや遅い (O(nq)、q はクエリの数)。

クエリの準線形複雑性を持たせるためにツリーを前処理する方法について何か提案はありますか?