修了試験 2017-12-10実施分 基本情報技術者試験 問5

解説

正解はウ。 削除される12の位置には，中間順序での直後の要素（右部分木の最小値）を移動するのが定石。 12の右部分木は14（左13，右15）なので最小値は13。 13は子をもたない葉なので，そのまま移動しても左側（9・10・11＜13）と右側（14・15＞13）の大小関係が保たれる。 9・10・14は子をもち単純な移動では木が崩れる。