2分探索木とヒープ

結論：ルールはそれぞれ1行で言える

• 2分探索木：どの節で見ても 左の部分木の値すべて ＜ その節 ＜ 右の部分木の値すべて
• ヒープ：どの節で見ても 親 ≦ 子（または親 ≧ 子）。左右の子の大小は決まっていない

2分探索木は「左右」に大小があり、ヒープは「上下」に大小があります。この違いさえ押さえれば、図の問題で迷いません。

木の用語を30秒で

木は、1つの出発点から枝分かれしていくデータの形です。いちばん上を根、子を持たない末端を葉、それぞれの丸を節（ノード）と呼びます。各節の子が最大2つの木を2分木といいます。

ある節から下をまとめたかたまりを部分木と呼びます。左の子から下が「左部分木」、右の子から下が「右部分木」です。2分探索木の条件は、直下の子だけでなく部分木の全員に対して成り立つ必要があります。

2分探索木の大小関係（いちばんよく出る）

2分探索木は数当てゲームに似ています。「50より大きい？」「小さい」「なら25より？」と半分ずつ絞り込むように、根から比べて小さければ左、大きければ右へ進めば目的の値にたどり着きます。

見分けるときのコツ：直下の親子だけを見ると失敗します。たとえば根17の左部分木に18が混ざっていたら、親子の関係が正しく見えても違反です。各節について「自分の祖先の誰よりも、左右の向きとして正しい範囲に入っているか」を確かめます。

大小の順に並べるときは中間順（通りがけ順）、つまり「左部分木 → 自分 → 右部分木」の順に読みます。2分探索木を中間順で読むと、必ず小さい順になります。

        a
      /   \
     b     c
    / \   / \
   d   e f   g

中間順：d → b → e → a → f → c → g（これが小さい順）

挿入：入れる順番で木の形が変わる

挿入は検索と同じ道をたどります。根から「小さければ左、大きければ右」へ進み、空いている場所（葉の下）にそのまま置きます。すでにある節の並びは変えません。

同じデータでも入れる順番が違えば形が変わります。たとえば 1, 2, 3, 4… と小さい順に入れると右へ一直線に伸び、探すのに全部をたどることになります。左右の高さがそろった木なら、探す回数は約 log₂n 回で済みます。

15個の値を入れて完全2分木（すべての段が満杯の木）にする場合、置き場所の配置は1通りに決まりますが、その形になる挿入順は何通りもあります（例：根になる真ん中の値を最初に入れ、次に2段目の2つを入れる、など）。

削除：子が2つあるときだけ要注意

子が2つのときに右部分木の最小値を選ぶのは、その値が「左側の全員より大きく、右側の残り全員より小さい」からです。右部分木の最小値は、右の子から左へ左へたどった突き当たりにあります。左部分木の最大値なら、左の子から右へ右へたどります。

ヒープ：上ほど小さい（大きい）木

ヒープは「親は子より小さい（または大きい）」という上下の関係だけを守る木です。根には必ず最小値（または最大値）が来るので、いちばん小さいものをすぐ取り出したいときに使います。左右の子同士の大小は決まっていません。

挿入の手順はトーナメントの勝ち上がりに似ています。新しい要素を最後部（最下段の左詰めの次の位置）に置き、親より小さい間は親と入れ替えて上へ進みます。親以上になったところ、または根に着いたところで止まります。

ヒープソート：ヒープから1つずつ取り出して並べる

ヒープソートは、未整列の部分をヒープ（順序木）にし、根にある最大値（または最小値）を取り出して整列済みの部分へ移す操作を繰り返します。取り出したあとは残りを再びヒープに整えます。

試験では、4種類の整列法の説明文の名前だけを入れ替えた選択肢が出ます。説明文のキーワードで見分けてください。

試験での問われ方

• 図から2分探索木を選ぶ：直下の親子は正しいのに、孫の位置で祖先との大小が崩れている図が混ざります。
• 大小関係を並べる：先行順・後行順・逆順の並びが選択肢に入っています。中間順（左→自分→右）で読みます。
• 挿入後の図を選ぶ：途中の比較を1か所だけ逆にした図が並びます。根から1つずつ比べて道をたどります。
• 削除：直下の子（10や14）をそのまま上げる選択肢が混ざります。正解は右部分木の最小値か左部分木の最大値です。
• ヒープへの挿入：入れ替えが1回で止まると考えると間違えます。親以上になるか根に着くまで続けます。
• 整列法の説明：説明文の名前が入れ替わっています。キーワードで判定します。