令和6年度 秋期 午前 問5
アルゴリズム
2分探索木に関する問題
次の 2 分探索木から要素 12 を削除したとき，その位置に別の要素を移動するだけで 2 分探索木を再構成するには，削除された要素の位置にどの要素を移動すればよいか。
〔図〕2 分探索木（丸と線の木の図。12 は太い丸）
6
├── 左 4
│ ├── 左 2
│ │ ├── 左 1
│ │ └── 右 3
│ └── 右 5
└── 右 8
├── 左 7
└── 右 12（太い丸）
├── 左 10
│ ├── 左 9
│ └── 右 11
└── 右 14
├── 左 13
└── 右 15- ア9
- イ10
- ウ13
- エ14
答えと解説を見る
✓ これが正解ウ13
解説
右の枝の最小値なら並びを保てます。
設問は、図の 2 分探索木から要素 12 を削除したとき、その位置に別の要素を移動するだけで木を組み直さずに済ませるには、どの要素を移せばよいかを選ばせています。図では根が 6 で、その右に 8 があり、8 の下に 12 が付いています。12 の左には 10 があってその下に 9 と 11 が並び、12 の右には 14 があってその下に 13 と 15 が並びます。2 分探索木では、どの位置でも左の枝にある値がその位置の値より小さく、右の枝にある値がその位置の値より大きいという関係が成り立ちます。したがって 12 を取り除いた穴に置けるのは、12 の左の枝にある値のすべてより大きく、右の枝にある値のすべてより小さい値だけです。この条件を満たすのは、左の枝の中で最も大きい値か、右の枝の中で最も小さい値の二つに限られます。左の枝の最大は 11、右の枝の最小は 13 で、選択肢にあるのは 13 のほうです。13 を穴に入れると、上にある 8 より大きく、左に来る 10 より大きく、右に残る 14 より小さいので、関係がすべて保たれます。
ほかの選択肢はなぜ違うのか
- ア9：9 を移す場合です。9 は左の枝の中で最も小さい値なので、穴に置くと 9 より大きい 10 と 11 が左の枝に残ってしまい、左は小さい値だけという関係が崩れます。
- イ10：10 を移す場合です。10 を抜くと、その下にあった 11 が左の枝に残ります。11 は 10 より大きいので、左の枝は小さい値だけという関係を満たせなくなります。
- エ14：14 を移す場合です。14 を抜くと、その下にあった 13 が右の枝に残ります。13 は 14 より小さいので、右の枝は大きい値だけという関係を満たせなくなります。
出典：令和6年度 秋期 応用情報技術者試験 午前 問5
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）