2分探索木から、左右両方に子をもつ節点を削除する。2分探索木の性質を保つための置き換え方として、適切なものはどれか。

解説

正解は「右部分木の最小値の節点で置き換える」です。右部分木の最小値は、削除する節点の直後の値です。これをその位置に置くと、左部分木の値はすべてそれより小さく、右部分木に残る値はすべてそれより大きくなり、性質が保たれます。最小値の節点は左の子をもたないため、元の位置から外すのも容易です。左部分木の最大値（直前の値）で置き換えてもかまいません。「右部分木の最大値の節点で置き換える」と、右部分木にそれより小さい値が残り、性質が崩れます。「左部分木の最小値の節点で置き換える」と、左部分木にそれより大きい値が残ります。「最も深い位置にある葉の節点で置き換える」は値の大小を考慮していません。