平成28年度 春期 午前 問5
データ構造
2分探索木に関する問題
10 個の節（ノード）から成る次の 2 分木の各節に，1 から 10 までの値を一意に対応するように割り振ったとき，節 a，b の値の組合せはどれになるか。ここで，各節に割り振る値は，左の子及びその子孫に割り振る値よりも大きく，右の子及びその子孫に割り振る値よりも小さくするものとする。
図（書き起こし）: 2分木。値の書かれている節だけが「5」「4」「a」「b」で，残り6個の節は空の丸です。
(5)
/ \
(4) (a)
/ \
( ) ( )
/ \ / \
( ) ( ) (b) ( )
\
( )
読み取りの注意（原典の線を追った結果）:
・根は 5。左の子が 4，右の子が a。
・4 は子を1つだけもち（左下へ1本），その子が左右2つの子をもつ。
・a も子を1つだけもち（右下へ1本），その子は左の子が b・右の子がもう1つの節で，
その右の子がさらに右下に子を1つもつ。
・節の総数は 5, 4, a, b と空の丸6個で 10個（原典の「10 個の節から成る」と一致）。
- アa＝6，b＝7
- イa＝6，b＝8
- ウa＝7，b＝8
- エa＝7，b＝9
答えと解説を見る
✓ これが正解アa＝6，b＝7
解説
右部分木の値の並びを絞ると a=6、b=7 に決まります。
設問の木は、根に5、その左に4、右にaが置かれた2分木です。2分探索木の規則によれば、根より右にある節はすべて根より大きい値になります。したがって根5の右部分木には1から10までのうち5より大きい5つの値が入り、その頂点であるaはこの5つの中で最も小さい値に決まります。1から10のうち5より大きいのは6から10までの5つですから、aは6です。次にaの右部分木を見ると、その中でaより大きい4つの値、つまり7から10までが並びます。図の構造では、この右部分木の根にはbの親が来て、その左の子がbとなります。aより大きい4つの値のうち最も小さい値がbになるので、bは7です。判定の軸は、部分木ごとに入る値の集合を範囲で絞り、頂点は集合の中で最小か最大かを図の位置で決めることです。
ほかの選択肢はなぜ違うのか
- イa＝6，b＝8：aが6でbが8だと述べています。aの右部分木にはaより大きい4つの値、つまり7から10までが入ります。その頂点の左の子がbなので、4つの中で最も小さい値がbに来ます。8はこの位置には入りませんでした。
- ウa＝7，b＝8：aが7でbが8だと述べています。aは根5の右部分木の頂点で、その部分木にはaより大きい値だけが並びます。右部分木には5個ぶんの値が入るので、aはその中で最小、つまり6でなければ足りませんでした。
- エa＝7，b＝9：aが7でbが9だと述べています。この組合せもaを最小に置いていないので、aの右部分木に必要な個数の値が残らず並びません。bの位置は右部分木の頂点の左の子で、4つの値の中で最小に決まるはずでした。
出典：平成28年度 春期 基本情報技術者試験 午前 問5（改変：原典の図表をテキストに書き起こした）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）