応用情報技術者 試験情報＆徹底解説

令和6年秋期問5です。
解答イ（誤答）の図に疑問を持ちました。
要素10を移動させたとき、なぜ左部分に要素9がくるのでしょうか？というか、要素11が要素10の左にきて、更に要素11の左に要素9がこない訳は何でしょう。

  10
 11
9
↑となってもいいはずです。
どっちにしろ2分探索木のルールから逸脱しているので誤答であることに変わりはないのですが、なんとなく疑問に思いました。
「A要素の左部分はA要素より小さくなければならない」というルールをギリギリまで遵守しているためでしょうか？

ご回答のほどよろしくお願いいたします。

https://www.ap-siken.com/kakomon/06_aki/q5.html

要素10を移動させたとき、要素9と要素11のどちらを併せて移動させるかという話かと思います。

勝手な推測ですが、「どちらでもよく、あくまで一例として要素9も併せて移動した図にした」だけかなと思います。

もしかしたら、理由があることを知ってる方がいらっしゃるかもしれませんが、僕は深い意味はないのかなと考えます。

私も No.2 と同意見です。

ちなみに別件ですが、リンク先の次の解説文を読んで
---
設問の2分探索木から要素12が削除された際、2分探索木の性質（要素同士の大小関係）を保つためには、12に最も近い値である要素11または要素13を新たな節点とします。この方法により他の要素の移動することなく2分探索木が再構成されます。
---
「12に最も近い値」という表現は誤解を招くだろうと思いました。

要素12を削除した場合、ただ一つの要素の移動だけで2分探索木を維持するには、
・節12から見た左部分木の中の最大値11
または
・節12から見た右部分木の中の最小値13
のどちらか、を削除した節12の位置に移動すればよい、という表現が良いと考えます。

問題文は、「要素12を削除したとき，その位置に別の要素を移動するだけ」となっています。
要素10を動かすと芋づる式に他の要素も動かすことになり「だけ」ではなくなります。
どちらを動かしてもよいのではなく、どちらも動かしてはダメ。

解説の図は、要素9と要素11のどちらも動かさない状態にすべきだと思います。

みなさま、意図をくみ取っていただき、また回答ありがとうございました。
「A要素の左部分はA要素より小さくなければならない」というルールを最大限遵守していたから、という結論だと私としてもまぁ納得がいくためそこで落ちたいと思います。