キーのリストが与えられていると、そのリストのほぼ完全なバイナリ検索ツリーをどのように見つけることができますか？

Question

私はPythonで実装されたアイデアで答えを見ました（Pythonには慣れていません） - 私はより一般的なアルゴリズムを探していました。

EDIT：明確化のため

： 我々は整数キーのリストを与えられていると言う：23 44 88 12 74 32 7 39 10

すなわちリストを任意に選択しました。そのリストからほぼ完全な（または完全な）バイナリ検索ツリーを作成します。そのような木は一つしかないはずです...どうすればそれを見つけることができますか？

Answer 1

binary search treeは、ノードの左サブツリーのすべての項目がノードより小さく、右サブツリーのすべてのノードがノードよりも大きくなるように構築されます。

完全な（またはほぼ完全な）バイナリツリーは、おそらく最後のものを除いたすべてのレベルが完全に満ちていて、下のレベルが左側に満たされているものです。

ので、例えば、これは、ほぼ完全な二分探索木である：

 4 
/ \ 
    2  5 
/\ 
1 3 

これではありません。

 3 
/ \ 
    2  4 
/  \ 
1   5 

ツリーの一番下のレベルは左から充填されていないため。

アイテムの数が2の累乗（つまり3,7,15など）より少ない場合、ツリーを構築するのは簡単です。リストをソートすることから始めます。次に、中央の要素をルートとして取ります。したがって、[1,2,3,4,5,6,7]があり、ルートノードが4の場合。

配列の右半分と左半分について同じことを再帰的に行います。

項目の数が2の累乗数よりも1少ない数でない場合は、開始点（ルートノード）を調整して、最後の行が残っているようにする必要があります。サブツリーの長さが2の累乗よりも小さくないときはいつでも、その調整を再帰的に適用する必要があるかもしれないことに注意してください。

これは宿題なので、私はあなたに理解してもらうつもりです。