18

1から始まるインデックスが付けられた2m -1の異なる比較可能な要素の配列が与えられます。

配列を完全な二分木として見ることができます。

Node is placed at index i.
Left child is placed at 2i.
Right child is placed at 2i+1.

たとえば、アレイ

[7 6 4 5 2 3 1]

木です

       7
    /    \
   6       4
  /  \    / \
 5    2   3  1

バイナリツリーとして表示すると、これらの要素はヒーププロパティを満たし、ノードはその両方の子よりも大きくなります。

A[i] > A[2i] and A[i] > A[2i+1]

結果のバイナリツリー（上記のとおり）がバイナリ検索ツリーになるように、配列の要素をシャッフルするための適度に高速なインプレースアルゴリズムはありますか？

二分探索木では、ノードはすべての左の子孫よりも大きく、すべての右の子孫よりも小さいことを思い出してください。

たとえば、上記の配列の再シャッフルは次のようになります。

[4 2 6 1 3 5 7]

これは二分探索木に対応します

       4
    /    \
   2       6
  /  \    / \
 1    3   5  7
4

3 に答える 3

9

2^m-1まず、一般性を失うことなく、バイナリツリーに要素1、2、3、...があると仮定できることに注意してください。したがって、これからは、これらの番号があると想定します。

1 2 3 4 5次に、私の試みは、ソートされた配列（つまり）をソートされた二分木を表す配列に変換する関数です。

要素を持つソートされた二分木で(2^m)-1は、ツリーの「下部」がすべての不均一な数で構成されていることが常にありますm=3。

     4
  2     6
 1 3   5 7

これは、対応する配列で、最後の数がすべて不均等な数であることを意味します。

4 2 6 1 3 5 7
      -------
         ^
         uneven numbers!

2^(m-1)したがって、対応する配列の最後の数がすべて不均等な数であることを確認することにより、二分木の最後の「行」を構築できます。したがって、最後の行に対して行う必要があるのは、インデックスが不均一な位置にあるすべての要素を最後の行に移動する関数を作成することだけです。

それで、今のところ、入力としてソートされた配列が与えられた場合に、最後の行を正しく確立するルーチンがあると仮定しましょう。

次に、配列全体のルーチンを呼び出して、他のすべての要素を並べ替えたまま、最後の行を作成できます。このルーチンを配列に適用する1 2 3 4 5 6 7と、次のような状況になります。

2 4 6 1 3 5 7
      -------
         ^
         correct!

最初のラウンドの後、2 4 6残りの要素を変更せずに、バイナリツリーの最後から2番目の「行」を構成する残りのサブ配列（つまり）にルーチンを適用すると、次のようになります。

 now correct as well!
   v
  ---
4 2 6 1 3 5 7
      -------
         ^
         correct from run before

したがって、私たちがしなければならないのは、最後の行（つまり配列の後半）を正しくインストールする関数を作成することだけです！

これは、が配列の入力サイズであるO(n log n)場合に実行できます。nしたがって、配列を最後から最初までトラバースし、最後の行（つまり配列の後半）が正しくなるように不均一な位置を交換します。これはインプレースで行うことができます。その後、配列の前半をソートします（ヒープソートなどを使用）。したがって、このサブルーチンの実行時間全体はO(n log n)です。

nしたがって、合計サイズの配列の実行時間は次のようになります。

O(n log n) + O(n/2 log n/2) + O(n/4 log n/4) + ...これはと同じO(n log n)です。このすべてが完全にインプレースで機能するように、ヒープソートなどのインプレースソートアルゴリズムを使用する必要があることに注意してください。

これ以上詳しく説明できず申し訳ありませんが、ご理解いただけると思います。

于 2011-02-11T14:22:09.697 に答える
2

n = 2 m -1とします。線形時間では、最大ヒープを作成し、並べ替えられた順序で二分探索木の要素を抽出できるため、（比較ベースのアルゴリズムを想定して）期待できる最善の方法はO（ n log n）時間とO（1）スペース。これがそのようなアルゴリズムです。

  1. j = nを1まで下げる場合、j要素の最大ヒープから最大要素をポップし、（新しく空になった）場所jに格納します。これにより、配列がソートされます。

  2. 分割統治法を使用して、並べ替えられた配列を二分探索木に変換します。（単純にこれはOmega（log n）スペースですが、スタックをO（1）log（n）ビットワードに圧縮できると思います。）

    a。ルートよりも小さい要素をツリー化します。

    b。ルートより大きい要素をツリー化します。

    c。半分のサイズ（O（n））のサブ問題を残すように、ルートよりも小さい葉を所定の位置に回転させて（= 3回反転）、ツリーをマージします。

    (08 04 12 02 06 10 14 01 03 05 07 09 11 13 15)16(24 20 28 18 22 26 30 17 19 21 23 25 27 29 31)

    (08 04 12 02 06 10 14)16(24 20 28 18 22 26 30)01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

    (08 04 12)16(24 20 28)02 06 10 14 18 22 26 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

    (08)16(24)04 12 20 28 02 06 10 14 18 22 26 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

    16 08 24 04 12 20 28 02 06 10 14 18 22 26 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31

于 2011-02-11T13:41:35.223 に答える
0

いくつかの基本的なアイデア：

  1. 二分探索木は二分木です。
  2. ルートの両方の子はnilであるか、それ自体が二分探索木です
  3. 値は次の条件を満たす：左の子<ルート<右の子

条件1は問題ありません。ヒープも二分木です。条件2には問題がありますが、ボトムアップアプローチを提案しています。条件3も満たされていません。

ボトムアップとは、次のことを意味します。-すべての葉から始めます-これは問題ありません。二分探索木です。-次に、ルートまでの親の各レベルを再帰的にウォークします。-左の子が右の子よりも大きい場合は、サブツリーを交換します。-ルートを2つの子の大きい方の値と交換します（これは正しい子です）-これでは不十分な場合があります-再びバイナリ検索ツリーになるまで、正しいサブツリーを修正し続ける必要がある場合があります。

これは機能するはずです。しかし、それでも-最上位の要素を削除して自己平衡ツリーに挿入することは、より高速で優れたアプローチであり、実装がはるかに簡単です（たとえば、c++のstd:: mapなどの標準コンポーネントを使用します）。

別のアイデア：二分探索の場合、ツリーは、ツリーを左から右、右に歩くと、ソートされた値を取得するという特性を保持します。これは逆に行うことができます。ヒープから値をソートすることも簡単です。これを組み合わせてみてください-ヒープから読み取り、ソートされた値から直接ツリーに書き込みます。これはO（n）で実行できると思いますが、適切に実行できるかどうかはわかりませんが、そうではないと思います。

于 2011-02-11T13:03:32.200 に答える