二分木
二分木(にぶんぎ)は、データ構造の1つである。二進木(にしんぎ)やバイナリツリー(英: binary tree)とも呼ばれ、根付き木構造の中で、全てのノード(節点 node)が持つ子の数が高々2であるものをいう。典型的には2つの子はそれぞれ「左」「右」と呼ばれる。
たとえば、二分探索や二分ヒープを実装するために使われる。
以後、括弧の中は英語表記。
二分探索木の検索効率が最高になるのは、木の高さが最低な時で、即ち根から各葉までの高さができるだけ等しくなった場合である。そのような二分探索木を平衡二分探索木と呼ぶ。詳細は平衡二分探索木を参照されたい。