二分探索木の利用例 (ソート済みデータの効率的な管理、辞書や集合の実装)
**二分探索木の利用例 (ソート済みデータの効率的な管理、辞書や集合の実装)**は、探索範囲を中央の比較で半分ずつ捨てる探索法である。
仕組み
整列済み列で中央値と目的値を比較し、小さければ左半分、大きければ右半分へ境界を更新する。
計算量・性質
反復回数は高々⌈log2(n+1)⌉程度で時間O(log n)、反復実装の補助領域O(1)。
具体例
[2,5,8,12,16]から12を探すと8より右、次の12で発見する。
限界と注意点
未整列データには使えず、境界更新と中央計算のoff-by-oneに注意する。