基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

2分探索木は、2分木の各節にデータをもたせることで探索を行えるようにした木です。各節がもつデータは「その節から出る左部分木にあるどのデータよりも大きく、右部分木のどのデータよりも小さい」という条件があり、これを利用して効率的なデータ探索を可能にしています。
問題文の2分探索木から要素12を削除すると、2分探索木の性質(要素同士の大小関係)を保つために12に最も近い値である「要素11」または「要素13」を新たな節点として再構成が行われます。

• 
  節点となる要素9の左部分木に要素10と要素11が存在することになるので不適切です。
• 
  節点となる要素10の左部分木に要素11が存在することになるので不適切です。
• 
  正しい。節点となる要素13の左部分木に要素9，要素10，要素11、右部分木に要素14，要素15が配置されることになるので適切です。
• 
  節点となる要素14の右部分木に要素13が存在することになるので不適切です。