0

インタビューでこんな質問をされました。2 つの BST (Binary Search Tree) が与えられます。マージされたソート済み出力が結果になるように、2 つのツリーをトラバースする必要があります。制約は、配列のような余分なメモリを使用できないことです。私は、両方のツリーを組み合わせた順不同のトラバーサルを提案しました。アプローチは正しかったのですが、再帰に行き詰まり、コードを書くことができませんでした。

注: 2 つのツリーを 1 つにマージすることはできません。

誰かが私をこの方向に導いてください。前もって感謝します。

4

3 に答える 3

0

「最も簡単な」方法は次のとおりです。

  1. ツリー A を双方向リンク リスト (ソート済み) に変換します。
  2. ツリー B を双方向リンク リスト (ソート済み) に変換します。
  3. 並べ替えられたリストの印刷を最小限にトラバースする (簡単)
  4. リスト A をツリー A に変換する
  5. リスト B をツリー B に変換する

この手順のアルゴリズムはオンラインで見つけることができます。
ツリーを並行して走査することは不可能だと思います。訪問済みの左サブツリーを排除するための訪問済みフラグなどの追加情報が必要であり、それでも他の問題に遭遇します。
並列トラバーサルでこれがどのように可能になるかを誰かが知っていれば、喜んで教えてくれます。

于 2013-02-23T20:57:14.760 に答える
0

ツリーに親ノードまたは次のノードへのリンクがないと仮定しています。そうでない場合は非常に簡単です。これらのリンクをたどってツリーを反復し、リンク リストの場合と同様にマージ アルゴリズムを記述します。

次のリンクまたは親のリンクがない場合、単純な再帰は記述できません。2 つの「再帰」スタックが必要になります。次の構造を実装すると、各ツリーを個別に繰り返すことができます。

class Iterator
{
    stack<Node> st;
    int item(){
       return st.top().item();
    }
    void advance(){
        if (st.top().right != null)
            st.push(st.top().right);
            // Go as far left as possible
            while (st.top().left != null) st.push(st.top().left);
        else {
            int x = st.top().item();
            // we pop until we see a node with a higher value
            while(st.top().item()<=x) st.pop(); 

        }
    }
};

次に、これらの反復子の 2 つを使用してマージ アルゴリズムを記述します。

O(log n) スペースが必要になりますが、漸近的には、これは再帰的な反復以上のものではありません。

于 2013-02-23T21:25:43.670 に答える
0 
print $ merge (inorder treeA) (inorder treeB)

どうしたの？

(注意してください、上記は実際にタスクを実行して実行する実際の Haskell コードです)。inorder再帰で実装するのは簡単です。 mergeほぼ標準的な機能で、2 つの引数の順序付き (非減少) リストをマージし、順序付き出力リストを生成し、重複を保持します。

遅延評価とガベージ コレクションのため、リストは実際には作成されません。生成された要素はツリーごとに最大 1 つ保持され、次の要素が生成されると破棄されます。つまり、トラバーサルのイテレータが作成されます (それぞれが独自の内部状態を持つ)。 ）。

これが解決策yieldです（言語が上記、または同等のメカニズム、または制御スタックの奥深くにある2つのコンテキストをそれぞれ切り替えることができるSchemeの明示的な継続をサポートしていない場合（したがって、「2つの再帰」を並行して行うことができます。上記のように)):

彼らは時間の複雑さについて何も言わないので、最初のツリーの各ノードに対して、最初のツリーを再帰的previousにトラバースし、2 番目のツリーを新たにトラバースすることができます。したがって、最初のツリーに 2 つの連続する値があり、それらの間に 2 番目のツリーのすべての値を出力します。最初のツリーからの値の新しいペアごとに、2 番目のツリーの上部から再開して、再帰的なトラバーサルを新たに行います。

于 2013-02-23T22:52:56.687 に答える