令和5年度秋期 応用情報技術者試験(AP)の午後問題3は、
- 2分探索木(AVL木)
に関する問題でした。2分探索木については、何度か出題されてますが、木の回転が出題されたのは初めてかもしれませんね。
学生時代に作った記憶がありますが、復習のつもりで取り組んでみました。
プログラム例(r05a_ap_pm3.py)
実行結果
% python r05a_ap_pm3.py
実行すると、fig1.png,fig2.png,fig3.pngが出力されます*1。
fig1.png
まずは、関数 insert を使って、問3の1ページ目に掲載されている図1を書いてみました。
fig2.png
図1の状態から、関数 insertB を使って、4 を挿入してバランスをとった状態です。
fig3.png
図2の状態から、関数 insertB を使って、8 を挿入してバランスをとった状態です。
