基本情報技術者 2016年 春期 午前（科目A） 問05

二分探索木の節の値配置【午前解説】

正解の理由

解法ステップ

1. 木全体の節数が10個で、値は$1$〜$10$を一意に割り当てることを確認。
2. 中間順（in-order）走査が二分探索木では昇順になることを利用する。
3. 左部分木の節数を数える（図では4個）ので、左部分木が$1\sim 4$を占め、根が$5$と確定する。
4. 右部分木は残り$6\sim 10$を占める。a の子の構造を見て、a の左部分木の節数が0である（＝中間ノードはaの右子である）と判断する。
5. したがって a は右部分木の最小（6）で、a の右子の中間ノードの左子である b はその次（7）となる。

選択肢別の誤答解説

• ア: a=6, b=7 — 正しい。中間順の順位付けと部分木の節数から一意に決まる。
• イ: a=6, b=8 — b が8 だとすると a の直下で b が a より大きいが中間ノードの左子が8となり、残りの順位調整が合わなくなる。実際は b は a の直後の順位（7）になる。
• ウ: a=7, b=8 — a=7 とすると右部分木内で a の左に置かれるべき節が無くなるか、ノード数配分と矛盾して root=5 の右側の最小が6であるはずという条件に反する。
• エ: a=7, b=9 — a を7 とするには右部分木に6が存在するはずだが図の配置（a より上位の右側先頭）がそれを許さないため矛盾する。

よくある誤解

• 中間ノードの位置（a の子が左子か右子か）を図の見た目だけで誤判断し、a の順位を間違える。
• 「ラベル4だから値は4とは限らない」と混乱するが、木全体のノード数と中間順の順位から値4であることが確定する。
• 中間順（in-order）と前順・後順を混同して配置を決めてしまうミス。

補足コラム

• 左部分木: 1,2,3,4（4は図の4に対応）
• 根: 5
• 右部分木（中間順）: 6(a), 7(b), 8(中間), 9, 10

FAQ