2分探索木（BST）とは？

2分探索木（BST：Binary Search Tree）とは、各ノードが最大2つの子（左・右）を持つ木構造のうち、「左の子＜親＜右の子」という大小関係を、どのノードでも満たすものです。

この一貫したルールがあるので、値を探すときは「今より小さければ左、大きければ右」と降りるだけ。比べるたびに探す範囲が半分ずつ絞られ、バランスが取れていれば探索・挿入は平均 O(log n) で済みます。

図：中間順（左→自分→右）にたどると 20→30→40→50→60→70→80 と昇順に並ぶ

特徴的なのが、中間順（左→自分→右）で巡回すると必ず昇順に並ぶこと。一方で、すでに小さい順に挿入すると一直線に伸びた木になり、実質は連結リストと同じで最悪 O(n) まで遅くなります。これを防ぐのがAVL木・赤黒木などの平衡木です。

基本情報技術者試験では、木の性質、挿入後の形、前順・中間・後順の巡回結果、偏った木の計算量が問われます。