基本情報技術者平成16年秋期 午前問12

午前問12

次の2分探索木から要素12を削除したとき,その位置に別の要素を移動するだけで2分探索木を再構成するには,削除された要素の位置にどの要素を移動すればよいか。
12.gif/image-size:278×181
  • [この問題の出題歴]
  • 基本情報技術者 H13秋期 問12
  • 基本情報技術者 H25春期 問5

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

2分探索木は、2分木の各節にデータをもたせることで探索を行えるようにした木です。各節がもつデータは「その節から出る左部分木にあるどのデータよりも大きく、右部分木のどのデータよりも小さい」という条件があり、これを利用して効率的なデータ探索を可能にしています。
問題文の2分探索木から要素12を削除すると、2分探索木の性質(要素同士の大小関係)を保つために12に最も近い値である「要素11」または「要素13」を新たな節点として再構成が行われます。
  • 12a.gif/image-size:278×181
    節点となる要素9の左部分木に要素10と要素11が存在することになるので不適切です。
  • 12i.gif/image-size:278×181
    節点となる要素10の左部分木に要素11が存在することになるので不適切です。
  • 12u.gif/image-size:278×181
    正しい。節点となる要素13の左部分木に要素9,要素10,要素11、右部分木に要素14,要素15が配置されることになるので適切です。
  • 12e.gif/image-size:278×181
    節点となる要素14の右部分木に要素13が存在することになるので不適切です。
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop