algorithm - 二分探索木の作成

Question

次の値を順番に追加してバイナリ検索ツリーを構築する場合：

 10, 7, 16, 12, 5, 11, 2, 20, 1, 14

高さ5のツリーを取得します。高さ4のツリーを作成する整数の順序を決定するために使用できる方法（試行錯誤以外）はありますか？

score 5 · Accepted Answer

これについては完全には考えていませんが、特定の深さのツリーを取得する1つの方法は、要素を挿入する前に並べ替えることです。つまり、要素を並べ替えてからN二分探索木に挿入すると、深さのツリーが生成されNます。

次のことができる場合があります。

（もちろん、どのK要素から始めるか、残りの要素を挿入するための戦略を選択するのは難しい部分ですが、おそらくこれが始まりになるでしょうか？）

編集K：十分に大きいと仮定すると、一般的な解決策は可能だと思います。これはどう：

たとえば、最後の4を並べ替えて挿入した後：

...最後の3を挿入した後：

...最後の2の後：

    12
   /  \
  7    14
 / \     \
2   10    16
 \    \     \
  5    11    20

...そして最後に、最後の要素を挿入した後：

      12
     /  \
    7    14
   / \     \
  2   10    16
 / \    \     \
1   5    11    20

...高さK=4のBSTが残ります。

このアプローチは、Kが十分に大きい場合、特に。の場合にのみ機能することに注意してくださいK(K+1)/2 >= N。

score 5 · Accepted Answer

はい、最初に完全にバランスの取れたツリーを構築してから、親ノードが子の前に出力されるようにノードを出力できます。

完全にバランスの取れたツリーを作成するには、数値を並べ替えてから、再帰的な 2 分割を使用してツリーを構築します。

たとえば、あなたの場合、数字を並べ替えます

 1 2 5 7 10 11 12 14 16 20

そして、それらからバランスの取れたツリーを構築します（真ん中の数字をルートとして、このプロセスを再帰的に繰り返します）

            11
     5            14
 1     7       12    16
   2     10             20

preorder traversal または width-first traversal を使用して、必要な順序でノードを出力できるようになりました (子ノードの前に親ノードを出力する限りは問題ありません)。

11 5 14 1 7 12 16 2 10 20

3 に答える 3