令和6年度 秋期 応用情報技術者試験 午前 問5

【解説】

2分探索木（BST）において要素を削除する場合、以下のルールに従います：

1. 子がない場合：そのノードを単純に削除します。
2. 子が1つの場合：その子ノードを親ノードに接続します。
3. 子が2つの場合：
   • 右部分木の最小値 または
   • 左部分木の最大値

   を削除されたノードの位置に移動します。

この問題では 要素12 を削除します。ノード12には 2つの子（10 と 14）が存在します。

このような場合、右部分木の最小値をノード12の位置に移動するのが一般的です。

ノード14を根とする右部分木の最小値は 13 であるため、削除後にノード12の位置に移動するのは 13 になります。