binary-tree - 二分探索木の順序付け

Question

一連の数値をバイナリ検索ツリーに並べ替えようとするとき、ツリーの高さが最も短くなる、つまり最も効率的になるように並べ替える方法は常に 1 つだけですか?

score 2 · Accepted Answer

一連の数値は、1 つの要素をツリーのルートとして取り、その周りに他のすべての数値を配置することにより、BST に変換できます。この理論と矛盾する次の状況を見ることができました。

1 つのルートを選択すると、高さのツリーが生成さhれ、左側のサブツリーが右側のサブツリーよりも「高く」なります。別のルートを選択すると、同じ高さの異なるツリーにつながりh、右側のサブツリーが左側のサブツリーよりも「高く」なります。

もう 1 つの簡単な例では、直接関連していない 2 つの連続する要素の挿入順序を交換することで、ツリー内の互いの位置に影響を与えません。

反例による反証。

セットしましょうS = {0, 1, 2, 3}。次の順序で要素を二分探索木に挿入します。1, 0, 2, 3

次の順序で要素を二分探索木に挿入します。1, 2, 0, 3

これら 2 つのツリーの挿入順序は異なりますが、どちらも最小の高さであるため、最小の高さの二分探索ツリーを提供する挿入順序は 1 つだけであるという記述は誤りです。

ツリー上の要素の実際の順序に関心がある場合は、セットの要素を次の順序で挿入します。2, 1, 0, 3

繰り返しますが、このツリーは前のツリーと同じ高さです。したがって、ツリー内の項目の順序が異なると、最小の高さのツリーも生成される可能性があることがわかります。

（余談）

最初にセットの要素を並べ替え、次に並べ替えられたセットを継続的に細分割してバランスを確保し、各行を完全に埋めることにより、常に最小の高さのツリーを構築できます。

これにより、常に最小の高さになる完全なバイナリツリーが得られるはずです。