sorting - 二分探索木 -- 順序付け

Question

値が V= {1,2,3,4,5,6,7} である検索ツリーの V 値がある場合、右から左に挿入されます

そして、可能な限り最大と最小の高さになるように注文する必要があります - どのようにそれを行うでしょうか? 最良と最悪の (lg2 (n+1)) ケースが必要ですか??

そして、順序は一意ですか？

ありがとうございます - なんとなくわかりますが、どのような手順を踏むべきかわかりません。

Answer 1

そのような最も高いツリーは、ソートされたシーケンスから値を挿入することによって作成されます

1 2 3 4 5 6 7

また

7 6 5 4 3 2 1

最短のツリーは、中央値を見つけて左と右のサブツリーを再帰的に処理する再帰アルゴリズムを介して値を順序付けることによって作成されます。

4 2 1 3 6 5 7

これにより、対数の高さの木が生成されます。

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

ここでは中央値が 4 なので、それが最初になります。

4

これで、左 (1、2、3) と右 (5、6、7) のパーティションができました。左を並べ替えるには、その中央値 2 から始めます。これで、サブツリーの 1 と 3 が得られました。これらは 1 つの要素セットなので、それが基本ケースです。

4 2 1 3

次に、6 から始めて、右側のサブツリー (5、6、7) を処理します。

4 2 1 3 6 5 7

Answer 2

最大の高さは簡単です。それらを順番に並べてください：

1
 \
  2
   \
    ...

背の低いものを並べ、真ん中を根とし、両側をどちらかの枝にします。すすいで繰り返します。

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

つまり...最初のものは n 、2番目のものは log_2(n) (切り上げ)。