二分探索木

提供: MonoBook
ナビゲーションに移動 検索に移動

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

根つき木で表され、ある要素の子は必ず2個以下である。また、子に順番の区別がある。

二分探索木の例

データ操作[編集 | ソースを編集]

挿入[編集 | ソースを編集]

  1. 木の根に注目する。根が無ければ、挿入するデータを根にして終了する。
  2. 今注目している要素のデータと挿入するデータを比較する。
  3. 挿入するデータが今注目している要素のデータより大きければ右の子へ、小さければ左の子へ注目を移す。
  4. 注目しようとした子が無ければ、その位置に挿入するデータを子として置き、終了する。
  5. 注目を移したら、2に戻る。以下、繰り返す。

挿入するデータと今注目している要素のデータが同じだった場合、目的の処理によって、 挿入するデータを破棄する、注目している要素に関連付けられた値を書き換える(連想配列の場合)、 あらかじめ左または右に行くと決めておく、などの処理が考えられる。

検索[編集 | ソースを編集]

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

長所[編集 | ソースを編集]

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

短所[編集 | ソースを編集]

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

関連項目[編集 | ソースを編集]