二分探索木の挿入順序と高さの求め方を徹底解説｜具体例で理解するBSTの作り方

二分探索木（Binary Search Tree）は、データ構造やアルゴリズムの学習で頻出する重要なテーマです。特に、同じデータを登録しても挿入する順番によって木の形や高さが変化する点、また新しい要素を追加するときの比較経路を理解することが試験問題でも重要になります。

この記事では、二分探索木への要素挿入の仕組み、高さ2や高さ4になる挿入順序の考え方、新しい要素を挿入するときにあり得ない比較順序を判断する方法について、具体例を使って解説します。

二分探索木とは何か

二分探索木とは、各節点（ノード）が最大2つの子を持つ木構造で、左部分木には親の値より小さい値、右部分木には親の値より大きい値が配置されるという特徴があります。

例えば、ある節点の値が10の場合、左側には10より小さい値だけが入り、右側には10より大きい値だけが入ります。この規則によって、探索時には不要な部分を除外できるため、高速な検索が可能になります。

二分探索木では、同じ値の集合を登録しても、登録する順番によって完成する木の形が変化します。そのため、高さも変わります。

新しい要素を挿入するときは、まず根（ルート）の値と比較します。

例えば、根が10で新しい値が5の場合、5は10より小さいため左側へ進みます。左の子が空いていれば、そこに5を配置します。

この処理を繰り返すことで、入力された順番に応じた二分探索木が完成します。

高さ2の木を作るには、できるだけ根の近くに多くの節点が配置されるような順番で挿入します。

例えば、以下の順番で挿入します。

7 → 5 → 13 → 3 → 11 → 14 → 25

この場合、完成する二分探索木は次のようになります。

　　　　7
　　　/　　\
　　 5　　 13
　　/　　 /　 \r>　 3　　11　 14
　　　　　　　　\
　　　　　　　　25

根を7にすることで、左側に小さい値、右側に大きい値がバランスよく配置され、高さは2になります。

高さを大きくするには、値が片側に偏るような順番で挿入します。

例えば、以下の順番があります。

3 → 5 → 7 → 11 → 13 → 14 → 25

この場合、最初に小さい値から順番に入れるため、右側だけに伸びる木になります。

3
　\
　 5
　　\
　　 7
　　　\
　　　 11
　　　　 \r>　　　　　13
　　　　　　\
　　　　　　 14
　　　　　　　 \r>　　　　　　　　25

このように、同じ7個のデータでも挿入順序によって高さが大きく変化します。

二分探索木に55を追加する場合、根から順番に比較しながら進む必要があります。

重要なのは、比較結果によって次に進む方向が決まるため、比較値の並びには必ず条件があります。

つまり、途中で右へ進んだ後、その範囲内で矛盾する大きな値や小さな値が出る順番は成立しません。

比較順序を確認するときは、最初の比較を根と考え、その後の範囲を絞っていきます。

例えば、最初に18と比較して55が大きい場合、次は18より右側にある値になります。この時点で、18より小さい値はその後の比較候補にはなりません。

また、途中で51と比較して55が大きい場合、次は51より右側の範囲になります。このように、比較するたびに探索範囲を更新します。

二分探索木の問題では、単純に数字を並べるだけではなく、「その順番で本当に木構造が成立するか」を確認することが重要です。

挿入順序を求める問題では、まず完成形の木を想像し、根から順番に配置される値を考えると解きやすくなります。

また、高さを小さくしたい場合はバランスよく中央の値から入れ、高さを大きくしたい場合は小さい順や大きい順に入れると偏った木になります。

二分探索木では、同じデータ集合でも挿入する順番によって完成する木の形や高さが変化します。

高さ2の木を作るには中央付近の値から登録し、高さ4のような深い木を作るには昇順や降順に近い順番で登録すると実現できます。

また、新しい要素を追加するときの比較順序を判断する問題では、各比較によって探索範囲がどのように変化するかを意識することが解答のポイントになります。