1

私の問題は次のとおりです。

キーを持つバイナリ検索ツリーがあります: a1<a2<...<an、問題は、O の再帰アルゴリズムを使用して、ツリー (i={1,2,3,...}) 内のすべての (a_i, a_i+1) ペアを出力することです。 (n) グローバル変数なしで O(1) 余分なスペースを使用する時間。例: キーを次のようにします: 1,2, ..., 5 印刷されるペア: (1,2) (2,3) (3, 4) (4, 5)

そのため、ツリー内で順不同のトラバーサルを実行して、各ノードの後続/先行を見つけることはできません。それには O(nh) 時間がかかり、ツリーのバランスが取れている場合、ツリー全体で O(nlgn) になるためです。

4

2 に答える 2

3

順序どおりの後継者または前任者を見つけるのに O(h) 時間がかかる可能性があることは正しいですが、BST の最小値から始めてその後継者を繰り返し見つけると、完了した作業の総量が最終的に増加することがわかります。ツリーの形状に関係なく、O(n) に出力されます。

直観的には、後続のルックアップを繰り返し行うときに、ツリーの各エッジを何回トラバースするかを考えてみてください。具体的には、ツリー内のすべてのエッジを正確に 2 回訪問します。1 回はサブツリーに降りるとき、もう 1 回はそのサブツリー内のすべてのノードを訪問してサブツリーから出るときです。n ノード ツリーには O(n) 個のエッジがあるため、完了するまでに O(n) の時間がかかります。

これについて懐疑的である場合は、簡単なプログラムを作成して検証してみてください。この結果を最初に聞いたとき、それを確認するプログラムを書くまで信じられなかったのを覚えています。:-)

擬似コードでは、ロジックは次のようになります。

  1. ルートから開始し、そのようなポインターが存在しなくなるまで、左側の子ポインターを繰り返したどって、ツリー内の最小値を見つけます。
  2. すべてのノードにアクセスするまで、現在のノードを思い出して、次のように後続ノードを見つけます。
    1. 現在のノードに正しい子がある場合:
      1. 右へ曲がって。
      2. 左の子がなくなるまで左に移動します。
      3. 開始したノードを出力し、次にこのノードを出力します。2: それ以外の場合:
      4. 開始したノードがその親の左側の子であることがわかるまで、親ノードまで歩いていきます。
      5. ルートにヒットし、左の子から上にトラバースしたことが見つからない場合は、完了です。
      6. それ以外の場合は、覚えているノードを出力し、次に現在のノードを出力します。

お役に立てれば！

于 2013-01-06T17:14:40.850 に答える
1

Oli は、順序通りのトラバーサルが O(n) であることは正しいですが、一般的な後続/先行ルーチンを使用するとアルゴリズムの複雑さが増すことは正しいです。そう：

簡単な解決策は、順序通りのトラバーサルを使用してツリーをたどり、最後に右向きのエッジを取得したとき (たとえば、last_right_ancestor_seenという変数を使用してその親ノードを指す) と最後のリーフ ノードを追跡することです。 (たとえば、last_leaf_seen (実際には、適切な子を持たないノード) で見たことがあります)。葉ノードを処理するたびに、その前身はlast_right_ancestorであり、非葉ノードにヒットするたびに、その前身はlast_leaf_seen です。 O(n) 時間、O(1) スペースの 2 つを出力するだけです。

十分に明確であることを願っています。そうでない場合は、図を描くことができます。

編集：これはテストされていませんが、おそらく正しいです：

walk(node* current, node* last_right_ancestor_seen, node* last_leaf_seen) {

    if(current->left != null) {
        walk(current->left, last_right_ancestor_seen, last_leaf_seen);
    }

    if(current->is_leaf()) {
            if(last_right_ancestor_seen != null)
                print(last_right_ancestor_seen->value, current->value);
    }
    else {
        print(last_leaf_seen->value, current->value);
    }

    if(current->right != null) {
        *last_right_ancestor_seen = *current;
        walk(current->right, last_right_ancestor_seen, last_leaf_seen);
    }
    else {
        *last_leaf_seen = *current;
    }

}
于 2013-01-06T15:13:01.597 に答える