二分探索木
二分探索木とは、大小関係を決めることができるデータの挿入と検索をO(log N)でできることを期待したデータ構造である。
根つき木で表され、ある要素の子は必ず2個以下である。また、子に順番の区別がある。
目次
データ操作編集
挿入編集
- 木の根に注目する。根が無ければ、挿入するデータを根にして終了する。
- 今注目している要素のデータと挿入するデータを比較する。
- 挿入するデータが今注目している要素のデータより大きければ右の子へ、小さければ左の子へ注目を移す。
- 注目しようとした子が無ければ、その位置に挿入するデータを子として置き、終了する。
- 注目を移したら、2に戻る。以下、繰り返す。
挿入するデータと今注目している要素のデータが同じだった場合、目的の処理によって、 挿入するデータを破棄する、注目している要素に関連付けられた値を書き換える(連想配列の場合)、 あらかじめ左または右に行くと決めておく、などの処理が考えられる。
検索編集
- 木の根に注目する。根がなければ、見つからなかったとして終了する。
- 今注目している要素のデータと検索したいデータを比較する。
- 検索したいデータと今注目している要素のデータが同じなら、見つかったとして終了する。
- 検索したいデータが今注目している要素のデータより大きいなら右の子へ、小さければ左の子へ注目を移す。
- 注目しようとした子がなければ、見つからなかったとして終了する。
- 注目を移したら、2に戻る。以下、繰り返す。