二分探索木
意味・解説
各節点（ノード）が「左の子の値 ＜ 親の値 ＜ 右の子の値」という大小関係を持つ二分木構造のデータ形式。
効率的なデータ探索を目的に設計されたツリー構造（木構造）。このルールにより、左側には親より小さい値、右側には大きい値が整理されている。データの検索、挿入、削除を高速に行うことができ、理想的な状態では計算量が $O(log n)$ となる。RDBのインデックスなどの基盤技術。
くわしく
「ある数字より『小さいなら左』『大きいなら右』というルールで、データを綺麗に枝分かれさせたピラミッド型の名簿」です。
1.探索の速さ:
1回チェックするたびに、探す範囲を半分に絞り込めるため、大量のデータから一瞬で目的の値を見つけ出せます。
2.注意点:
データの追加順序によっては「ひょろ長い」形になり、効率が落ちることがあります。これを防ぐ工夫をした「赤黒木」や「AVL木」などの進化形も存在します。
例文
数万件のIDを高速に検索するため、データ構造に二分探索木を採用した。
同義語: 2分探索木, BST
分類: データ構造 / 木構造