46

参考： @MS SDE 面接第3回でこんな質問をされました。そしてそれは宿題の問題ではありません。私もそれを考え、以下の私のアプローチに言及しました.

質問: BST を変更して、可能な限りバランスがとれるようにします。言うまでもなく、できるだけ効率的に行う必要があります。

ヒント: インタビュアーは、これは論理的な質問だと言いました。別の考え方をすれば、答えが得られます。難しいコーディングは必要ありません。
--> そうは言っても、私が AVL/RB Trees を指し示すことを彼が期待していたとは思いません。

私の解決策： 私は、ツリーを順番にトラバーサルし、中間要素を新しいツリーのルートとして使用することを提案しました（新しいルートと呼びましょう）。次に、中間要素の左部分に移動し、その中間要素をツリー ルートの新しいルートの左サブツリーのルートとして取得します。右側も同様。これを再帰的に行うと、最適なバランスの取れた BST が得られます。

ここに投稿する理由: しかし、彼は答えに満足していませんでした :( それで、ウェイト/RBカラーリング戦略を使用せずにこれを行う方法は本当にありますか、それとも彼はただ私をだましていたのでしょうか?あなたの専門家の考え。

複製？いいえ！この質問が あることは知っていますが、リクエスタによって提案された解決策は複雑すぎて、他の人は AVL ツリーについて話しています。

4

4 に答える 4

43

任意の二分探索木を完全な二分木に再形成するための O(n) 時間、O(1) 空間アルゴリズムであるDay-Stout-Warrenアルゴリズムを調べることをお勧めします。直感的に、アルゴリズムは次のように機能します。

  1. ツリーの回転を使用して、ツリーを縮退リンク リストに変換します。
  2. リンクされたリストに選択的なローテーションを適用することにより、リストを完全にバランスの取れたツリーに変換します。

このアルゴリズムの優れた点は、線形時間で実行され、一定のメモリ オーバーヘッドしか必要としないことです。実際、新しいツリーを作成して古いデータをコピーするのではなく、基になるツリーを再形成するだけです。コーディングも比較的簡単です。

お役に立てれば！

于 2012-12-25T05:07:50.683 に答える
17

「可能な限りバランスを取る」 =完全な (または完全な) 二分木1 . それ以上のバランスを取ることはできません。

解決策は簡単です。「空の」完全なバイナリ ツリーを構築し、新しいツリーと入力ツリーを (同時に) 順番に走査して完全なツリーを埋めます。

完了すると、取得できる最もバランスの取れたツリーが得られます。このアプローチの時間計算量は ですO(n)。

編集:
これは、次の手順に従って行う必要があります。

  1. ノードを持つダミーの完全なツリーを構築しnます。各ノードのすべての値は、ガベージ値に初期化されます。
  2. originalIter(1)元のツリー用、(2)newIter新しい (ガベージで初期化された) ツリー用の2 つの反復子を作成します。両方の反復子は、要素を順番に走査して返します。

  3. 次の手順を実行して、ツリーに元の値を入力します。

     while (originalIter.hasNext()):
      newIter.next().value = originalIter.next().value

(1) (ウィキペディアより): 完全二分木とは、最後のレベルを除くすべてのレベルが完全に埋められ、すべてのノードが可能な限り左にある二分木です。

于 2012-12-22T09:46:50.173 に答える