A little bit of everything

元・情報系大学院生の備忘録

二分探索木 (binary search tree)

二分木のうち、すべてのノードの値が、
[左の子の値] ≦ [自分の値] ≦ [右の子の値] となっているもの。 f:id:yuukiyg:20160116202229p:plain この図は二分探索木の条件をみたしている。
∵ 4 ≦ 5 ≦ 8 だし、 7 ≦ 8 ≦ 9 になっている。

1. 検索

二分探索木では、データを高速に検索することができる場合がある。∵あるノードの値より大きな値は、そのノードの右側の木にしか存在しない、と、一発でわかる。つまり二分探索(のような検索)が可能。

手順:

  1. 検索したいノード(目的ノード)を決め、手順2を実行。
  2. ルートノードを着目ノードとし、 3 を実行。
  3. 目的ノードと着目ノードが等しければ検索終了(成功)。なければ 4 を実行。
  4. 着目ノードと目的ノードを比較し、
    「目的ノード < 着目ノード」なら左の木へ。左の木がなければ検索終了(失敗)。
    「着目ノード < 目的ノード」なら右の木に対して 2 を実行。右の木がなければ検索終了(失敗)。

最も計算量が大きいのは、一番深い葉へ進んだ場合 ⇒ [木の高さ] = [計算量]
木の高さは最悪でノードの数と同程度になるため、最悪の場合の計算量はO(n) 木がうまく分散して作られた場合、木の高さはlog(n)程度になるので、平均の計算量はO(long(n))
※ 木をうまく分散させてつくるには、平衡木をつくればOK



2. 挿入

手順:

  1. 挿入したいノード(目的ノード)を決め、手順2を実行。
  2. ルートノードを着目ノードとし、3 を実行。
  3. 着目ノードと目的ノードを比較し、
    「目的ノード < 着目ノード」なら左の木へ移動。
    「着目ノード ≤ 目的ノード」なら右の木へ移動。
    移動する木がなければ、その位置に挿入して終了。存在するなら、2へ。



計算量

最悪の場合の計算量は O(n)
平均の計算量は O(long(n))