「二分探索木」を編集中

'''二分探索木'''とは、大小関係を決めることができる[[データ]]の挿入と検索を[[オーダー|O]](log N)でできることを期待した[[データ構造]]である。

[[木|根つき木]]で表され、ある要素の子は必ず2個以下である。また、子に順番の区別がある。
[[ファイル:Binary_search_tree.png|thumb|right|二分探索木の例]]

==データ操作==
===挿入===
# 木の根に注目する。根が無ければ、挿入するデータを根にして終了する。
# 今注目している要素のデータと挿入するデータを比較する。
# 挿入するデータが今注目している要素のデータより大きければ右の子へ、小さければ左の子へ注目を移す。
# 注目しようとした子が無ければ、その位置に挿入するデータを子として置き、終了する。
# 注目を移したら、2に戻る。以下、繰り返す。
挿入するデータと今注目している要素のデータが同じだった場合、目的の処理によって、
挿入するデータを破棄する、注目している要素に関連付けられた値を書き換える([[連想配列]]の場合)、
あらかじめ左または右に行くと決めておく、などの処理が考えられる。

===検索===
# 木の根に注目する。根がなければ、見つからなかったとして終了する。
# 今注目している要素のデータと検索したいデータを比較する。
# 検索したいデータと今注目している要素のデータが同じなら、見つかったとして終了する。
# 検索したいデータが今注目している要素のデータより大きいなら右の子へ、小さければ左の子へ注目を移す。
# 注目しようとした子がなければ、見つからなかったとして終了する。
# 注目を移したら、2に戻る。以下、繰り返す。

==長所==
* [[実装]]が比較的単純
* [[ランダム]]なデータに対しては、ほぼO(log 挿入されたデータ数)で挿入と検索ができる

==短所==
* [[昇順]]や[[降順]]にデータが挿入されると、挿入や検索にO(挿入されたデータ数^2)かかってしまう

==関連項目==
* [[平衡二分探索木]]
* [[ハッシュテーブル]]
* [[データ構造]]