二分探索木 (binary search tree)
二分木のうち、すべてのノードの値が、
[左の子の値] ≦ [自分の値] ≦ [右の子の値] となっているもの。
この図は二分探索木の条件をみたしている。
∵ 4 ≦ 5 ≦ 8 だし、 7 ≦ 8 ≦ 9 になっている。
1. 検索
二分探索木では、データを高速に検索することができる場合がある。∵あるノードの値より大きな値は、そのノードの右側の木にしか存在しない、と、一発でわかる。つまり二分探索(のような検索)が可能。
手順:
- 検索したいノード(目的ノード)を決め、手順2を実行。
- ルートノードを着目ノードとし、 3 を実行。
- 目的ノードと着目ノードが等しければ検索終了(成功)。なければ 4 を実行。
- 着目ノードと目的ノードを比較し、
「目的ノード < 着目ノード」なら左の木へ。左の木がなければ検索終了(失敗)。
「着目ノード < 目的ノード」なら右の木に対して 2 を実行。右の木がなければ検索終了(失敗)。
最も計算量が大きいのは、一番深い葉へ進んだ場合 ⇒ [木の高さ] = [計算量]
木の高さは最悪でノードの数と同程度になるため、最悪の場合の計算量はO(n)
木がうまく分散して作られた場合、木の高さはlog(n)程度になるので、平均の計算量はO(long(n))
※ 木をうまく分散させてつくるには、平衡木をつくればOK
2. 挿入
手順:
- 挿入したいノード(目的ノード)を決め、手順2を実行。
- ルートノードを着目ノードとし、3 を実行。
- 着目ノードと目的ノードを比較し、
「目的ノード < 着目ノード」なら左の木へ移動。
「着目ノード ≤ 目的ノード」なら右の木へ移動。
移動する木がなければ、その位置に挿入して終了。存在するなら、2へ。
計算量
最悪の場合の計算量は O(n)
平均の計算量は O(long(n))