平成27年度秋季応用情報午後問3

平成27年度秋季 応用情報技術者試験(AP)の午後問題3は2分探索木に関する問題でした。

• 2015h27a_ap_pm_qs.pdf

データを8個挿入後の2分探索木とデータを2個削除した後の2分探索木を図示するようにしています。Gvizを使いましたが、左の子は左気味に右の子は右気味に描く方法が分からなかったので少し見にくくなってしまいました。

2分探索木は、

• データの探索
• データの挿入

は簡単ですが、

• データの削除

特に子どもが2つあるノードの削除が理屈では分かっていても実際に作るとなると難しいですね。

h27a_ap_pm3.rb

実行結果

before.png

after.png

追記(2017/05/17)

2分探索木が最悪になるケースを追加しました。

q = nil
1.upto(5) {|i|
  q = addNode(i, q)
}
outputGraph(q, 'badcase')