IT用語入門：2分木【各節が2本以下の子を持つ木構造】

2分木とは

2分木は、木構造の一種で、各節（ノード）が持てる子の数が最大2つに制限されたデータ構造です。上にひとつだけある根から枝分かれし、子を持たない終端は葉と呼びます。1つの節が3つ以上の子を持つものは多分木（N分木）と区別されます。

2分木では子を左と右に分けて扱います。代表例の二分探索木では、左の部分木に小さい値、右の部分木に大きい値を置く規則を使い、目的の値へ枝を辿るだけで探索できます。木が適度にバランスしていれば、探索・挿入・削除はおおむね対数時間で済みます。

木が片側に偏ると効率が落ちるため、自己平衡化する方式（AVL木や赤黒木）も使われます。階層データの表現、優先度付き処理、順序付けの走査など、多様な場面で役立つ基本構造です。