指定された仕様のバイナリツリー内のノードの最適な位置は何でしょうか？

Question

ノードが0,1または2の子を持つことができるバイナリツリーがあるとします。コスト値は各ノードに関連付けられ、{5,10,20,40}とすることができる。新しいノードの最も最適な配置は、同じまたはより低いコスト値を有するノードの下にある。例えば、コスト値20の新しいノードは、コスト値20のノードの下に配置するのが最も良いが、コスト値5および10のノードの下に配置することもできる。

このアルゴリズムの第1の要件は、コスト値10を有するノードがコスト値10を有する左の子を有する場合、コスト値10を有する新しいノードは、前記ノードの右の子にされる。二次的な要件は、ツリーの全体の深さを最大にすることです。

ツリーはいつでも再配置できません。着信ノードの価値が低い場合、ペナルティは発生しません。 上記の要件を前提として、ツリー内に着信する新しいノードの最適な位置を決定するにはどうすればよいですか？私たちは一般的なアルゴリズムを書くことができますか？

最初は、ツリーの各レベルを最初に完成すると思っていましたが、最適ではないと私は考えています。

Answer 1

二次要件はであり、ツリー全体の深さはです。

これは少し異例です。

最短の道：

1. ソートあなたの入力は
2. 値の両方の左右のノードが前に満たされなければならない場合には最初の要件（まだ不明との点で、すべての最小限の値ノード（5の）を埋めますがでなければならない場合、最大深度はlog2（N ）になります。右側に塗りつぶさずに「左に入る」ことが許可されていれば、最大深度ツリーはすべて右のリストで縮退しますノードをヌルにする）。
   コールこのマスターツリー
3. は、次の値（例えば10値ノード）からツリーを作成し、マスターツリー
4. ステップ3を繰り返し、必要に応じて

注の最も深い分岐このツリーを取り付けますこれは最も簡単な概念です。実装では、マスターツリーが常にソートされ、最初のソートで処理されるという事実を利用できます。