https://monobook.org/w/index.php?action=history&feed=atom&title=%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8 2026-06-04T12:13:59Z このウィキのこのページに関する変更履歴 MediaWiki 1.42.1 https://monobook.org/w/index.php?title=%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8&diff=3549&oldid=prev 2013-08-24T13:23:07Z

<p>作成</p> <p><b>新規ページ</b></p><div>&#039;&#039;&#039;二分探索木&#039;&#039;&#039;とは、大小関係を決めることができる[[データ]]の挿入と検索を[[オーダー|O]](log N)でできることを期待した[[データ構造]]である。<br /> <br /> [[木|根つき木]]で表され、ある要素の子は必ず2個以下である。また、子に順番の区別がある。<br /> [[ファイル:Binary_search_tree.png|thumb|right|二分探索木の例]]<br /> <br /> ==データ操作==<br /> ===挿入===<br /> # 木の根に注目する。根が無ければ、挿入するデータを根にして終了する。<br /> # 今注目している要素のデータと挿入するデータを比較する。<br /> # 挿入するデータが今注目している要素のデータより大きければ右の子へ、小さければ左の子へ注目を移す。<br /> # 注目しようとした子が無ければ、その位置に挿入するデータを子として置き、終了する。<br /> # 注目を移したら、2に戻る。以下、繰り返す。<br /> 挿入するデータと今注目している要素のデータが同じだった場合、目的の処理によって、<br /> 挿入するデータを破棄する、注目している要素に関連付けられた値を書き換える([[連想配列]]の場合)、<br /> あらかじめ左または右に行くと決めておく、などの処理が考えられる。<br /> <br /> ===検索===<br /> # 木の根に注目する。根がなければ、見つからなかったとして終了する。<br /> # 今注目している要素のデータと検索したいデータを比較する。<br /> # 検索したいデータと今注目している要素のデータが同じなら、見つかったとして終了する。<br /> # 検索したいデータが今注目している要素のデータより大きいなら右の子へ、小さければ左の子へ注目を移す。<br /> # 注目しようとした子がなければ、見つからなかったとして終了する。<br /> # 注目を移したら、2に戻る。以下、繰り返す。<br /> <br /> ==長所==<br /> * [[実装]]が比較的単純<br /> * [[ランダム]]なデータに対しては、ほぼO(log 挿入されたデータ数)で挿入と検索ができる<br /> <br /> ==短所==<br /> * [[昇順]]や[[降順]]にデータが挿入されると、挿入や検索にO(挿入されたデータ数^2)かかってしまう<br /> <br /> ==関連項目==<br /> * [[平衡二分探索木]]<br /> * [[ハッシュテーブル]]<br /> * [[データ構造]]</div>

imported>MikeCAT