平衡ツリーを構築する

Question

次のソートされた整数が与えられます。1 2 3 4 5 6 7 8.バランス検索ツリーをどのように構築しますか？

誰かがコード例を与えずにを説明することができれば、私は本当にいただければ幸いです。

宿題ではありません。私は試験の改訂をしています。

上記の値をバランスの取れたツリーに入れると、ツリーは次のようになりますか？

 5 
     4 6 
    3  7 
    2  8 
1 

Answer 1

あなたは下から上へのビルディングを考えることができます。

ルートがあります。ツリーに要素が1つしかない場合、これがルートです。ルートの各要素は、ツリー内の別の2つのノード（バイナリツリー）への参照を持ちます。 1つはそれ自身より大きな要素のためのものであり、もう1つはそれ自身より小さな要素のためのものです。あなたのツリーだけナンバーワンを持っており、あなたは数トウを挿入しようとしているのであれば、これは葉として挿入されます

、および参照ルートに指します「より大きな」ノードに2

値3を挿入すると、ノード2の「より大きい」参照に挿入する必要があります。しかし、これでツリーがアンバランスになるので、これを修正する必要があります。ノード2をルートとして設定し、ノード1を「より小さい」に、第3を「より大きい」参照を指し示す必要があります。

これはあなたが少し良く理解してくれることを願っています。

最終的な結果は、要素を挿入する順序によって異なります。その後、

2 
1 3 

3 
    2 4 
1 

と

3 
    2 4 
1  5 

ので、後：あなたは5、4、3、2、1のように挿入した場合でも...木のようなものでなければなりませんに。このようなノードを挿入するときの例はあまり良くありませんが、4,2,6,1,3,5の順で考えると、結果は次のようになります。

 4 
    2  6 
1 3 5 

Answer 2

最も簡単な方法は、おそらく次のようである：

• リストの平均値を検索します。
• 平均値の周りの整数を分割します。ここでは、左側に小さい数値が含まれ、右側には大きな数値が含まれます。
• 各パーティションからツリーを再帰的に構築することによって続行します。

あなたの整数のリストは既にソートされているので、平均値を見つけるために中央の値を選択するだけで済みます（パーティションを作成するときに平均値を移動する必要はありません）。リストを2つに分割するだけでサブツリーを取得できます。

最終的なツリーは、どのノードを中間として選択するかによって異なります。これは1つの例です：

4 
2  6 
1 3 5 7 
      8