令和5年度秋期応用情報午後問3(2)

昨日、作成した2分探索木のプログラムを使って、

最悪の場合の2分探索木と
平衡2分探索木

が作られていく様子を見ていきたいと思います。

プログラム例(`r05a_ap_pm3.py`)

最悪の場合

107行目以降を以下のように変更します。関数insertを使って、1から順番に7までデータを挿入していきます。

# 最悪の場合の時間計算量はO(n)である。
root = None
for i in range(1, 8):
    root = insert(root, i)
    exec(f"fig{i} = draw_tree(root)")
    eval(f"fig{i}.view(\"fig{i}\")")

実行の様子

`1`と`2`が挿入された状態

`7`まで挿入された状態

途中、省略しますが、7まで挿入されると、右側だけに子ノードが存在する状態になります*1。

回転を利用して木のバランスを保つ

今度は、関数insertBを使って、1から順番に7までデータを挿入していきます。

# 回転を利用して木のバランスを保つと計算量はO(log n)となる。
root = None
for i in range(1, 8):
    root = insertB(root, i)
    exec(f"figB{i} = draw_tree(root)")
    eval(f"figB{i}.view(\"figB{i}\")")