二分探索木　アルゴリズムを実装してみる【python】

今日は、二分探索木のアルゴリズムについて扱っていきます。二分探索木の基本的な考えは、Atcoderでも二分探索木の考えも出てきているのでアウトプットのために書きました。今日は二分探索木を参考書などで調べたので、何か間違えていたら教えてください。

二分探索木
扱うコード
実行結果

二分探索木

ソースコード

配列内の数を二分探索木で調べる

二分探索木

二分探索木(二分探索木)とは「左の子孫の値<=親の値<=右の子孫の値」という制約を持つ二分木である。

ja.wikipedia.org

二分探索方の実行時間はO(logn)となっている。また二分探索法は配列がソートされている場合に使用することが大半です。なのでソート時間は含まれていません。

また、これから扱うコード内の配列もソートされている配列前提で話しています。

扱うコード

x=[1,2,5,7,3,6,34,43,54,34,45,76]
l=sorted(x)
search=54
left=0
right=len(x)
t=(right+left)//2
while left<=right:
  if search == l[t]:
     break
  elif search > l[t]:
    left=t
  elif search < l[t]:
    right=t
  t=(left+right)//2
if search == l[t]:
  print("配列内の{}番目です".format(t+1))
else:
  print("配列内にありません")

このコードは配列x内の数(search=54)が配列内の何番目に位置しているかを知れべるコードです。実際はfor文を使うことでも同じようにできますが、atcoderなどではfor文の探索でも10^7で大体実行時間がオーバーしてしまいますが、二分探索木では10^30までは可能です。なのでデータ数が多い場合は二分探索木が有効なのです。