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

「令和5年度秋期応用情報午後問3 - Mae向きなブログ」、「令和5年度秋期応用情報午後問3(2) - Mae向きなブログ」の続きです。

graphvizを使うと、2分探索木を見える化できるので、もう少し多くの要素を持つ2分探索木を描いてみました。

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

127個の要素を持つ2分探索木

127個の要素を、以下の2つの方法でランダムに2分探索木に挿入していきました。

insert関数を使う
insertB関数を使う(バランスをとる方法)

プログラム例(r05a_ap_pm3.py)の107行目以降を以下のように変更します。

import random

A = [i for i in range(1, 2**7)] 
random.shuffle(A)
root = None
for i in A:                     # 127個の要素を木に挿入
    root = insert(root, i)
fig = draw_tree(root)
fig.view("fig")

rootB = None
for i in A:                     # 127個の要素をバランスをとりながら挿入
    rootB = insertB(rootB, i)
figB = draw_tree(rootB)
figB.view("figB")