0

二分探索木の高さを最小化しようとしている場合、これらは正しい手順ですか？：

1）ツリーからソートされた配列を生成します2）ソートされた要素を順番にツリーに追加してツリーを再構築します

4

4 に答える 4

2

すでに並べ替えられたリストを単純な非平衡二分探索木に追加すると、二分探索木の理論上の最悪のケースが構築されます。最も低い値のノードがルートであり、すべてのノードがリスト内でその直前のノードの「右側」に追加され、O（lg n）ではなくO（n）時間で検索して最大深度のツリーを作成します。 ）。事実上、過度に複雑なリンクリストを作成しているだけです。

于 2012-12-03T17:20:27.847 に答える
2

要素を並べ替えた後、中央の要素をルートノードとして定義してツリーを再構築し、中央の前後の要素からそれぞれ左と右のサブツリーを再帰的に構築します。

于 2012-12-03T17:46:34.437 に答える
0

でソートされた要素を挿入する前にツリー構造を再構築するとinorder、提供するソリューションが正しくなると思います。

  1. ツリーを再構築します。ヒープのように。
  2. 並べ替えられた要素を順番に挿入

たとえば、元のツリーが次のような場合：

                 (5)
           (3)         (6)
      (2)      (4)
  (1)

  1. 次のようにツリーを再構築します。

               ()
    ()            ()
()      ()   ()

  2. ソートされた要素をinorder次のように挿入します： 1、2、3、4、5、6

                (4)
     (2)             (6)
(1)      (3)    (5)
于 2012-12-03T17:24:32.267 に答える
0

ツリーにアクセスでき、「手動で」変更できると思います。バランスの問題は次のように解決できると思います（擬似コード）：

depth(node)
{
    if node is null, return 0;
    l = depth(left child);
    r = depth(right child);
    diff = (r - l);
    if (diff < -1) rotate right (as often as you need);
    else if (diff > 1) rotate left (as often as you need);
    return the new maximum depth of both subtrees +1;
}

告白する必要があります。これについてはよくわかりませんが、ツリーをトラバースして正しい回転を適用する必要があるため、一時配列は必要ないという考えです。

于 2012-12-03T17:32:54.707 に答える