二分木/二分探索木

上記概念図において、○の部分を節（ノード）、線の部分を枝と呼ぶ。この概念図で上下を逆さまにしてみれば、木のような形をしていることが分かる。これが木構造と呼ばれる由来である。ここで、ある節から見て、その１つ下にある節のことを子と呼び、逆に１つ上の節を親と呼びます。一番上にある節のことを根（ルート）と呼び、一番下にある節のことを葉と呼ぶ。なお、葉のことを外部ノード、葉以外の節を内部ノードと呼ぶことがある。

二分木（バイナリツリー）

１つの節が、２つ以下の子を持つような木構造を二分木（バイナリツリー）と呼ぶ。もし、必ず２つの子を持つようならば、全二分木と呼ばれる。さらに、どの葉も同じ深さにある場合は、完全二分木と呼ばれる。最初の概念図では、根の下に子が３つあるので、これは二分木ではない。１つの節が、３つ以上の子を持つ木構造も考えられる。これは、多分木と呼ばれている。

１つの節が、１つしか子を持たない場合、これはもはや木構造とは呼べないような形になる。なぜなら、そのような構造は連結リストそのものであるからだ。木構造に要素を追加していくとき、節を置く位置を誤ると、このような状態になってしまうことがある。大抵の場合、これは性能を悪化させる結果になる。

再帰的な性質

囲まれた部分だけを単独で観察してみても、その部分もやはり二分木になっていることが分かる。このように、木構造はその一部分だけを取り出してみても、やはり木構造の形をしているという特徴がある。これを部分木と呼ぶ。この概念図の場合、全体としての根の右側にある部分木を囲っているが、この場合、根に対して右部分木、左側にあれば左部分木と呼ぶ。

もっと大きな木構造であれば、部分木の中にさらに部分木が、その中にさらに部分木があるという構造になる。このように、自分自身の一部が、自分自身と同じ形状をしているような構造は、再帰的な構造と呼ばれる。データ構造が再帰的になっているのであれば、プログラムも再帰処理を活用しやすくなる。

走査

二分木に含まれるすべての節を調べたいとする。このような処理を、走査（トラバース）と呼ぶ。ここで重要な点は、「すべてをもらさず」「同じものを重複せず」に調べつくすことである。二分木に対する走査の方法には、大きく分けると、深さ優先探索と幅優先探索の２つがある。前者はさらに、行きがけ順探索、通りがけ順探索、帰りがけ順探索に分類できる。これらは、調べる節の順序が異なる。

深さ優先探索では、根から始めて、葉に行き着くまで子を辿っていく。葉まで行き着いたら、その親に戻り、別の子の方を調べに行き、やはり葉まで辿る。これを繰り返せば、いずれすべての節を調べられる。

ここで、行きがけ順探索、通りがけ順探索、帰りがけ順探索の違いは、根とその２つの子をどんな順序で調べるかである。行きがけ順探索では、根→左の部分木→右の部分木の順で調べる。通りがけ順探索では、左の部分木→根→右の部分木の順で調べる。帰りがけ順探索では、左の部分木→右の部分木→根の順で調べる。幅優先探索の方は、まず根を調べ、次に１つ深い階層の左部分木、右部分木を調べる。１つの階層の節をすべて網羅してから、次の階層へ降りることを繰り返す。

二分探索木

二分探索木とは、「左の子の値＜親の値＜右の子の値」という条件を持たせるというルールを適用することによって、データの探索効率を向上させたデータ構造である。これだと同じ値を持てないが、２つの不等号のうち片方だけなら＝を付け加えれば対応できる。このルールを満たした木は、次のようになる。

このようなルールを満たしていれば、特定のデータを探すには、次のように行える。

１.根を調べる。一致していれば探索完了
２.根の値と探したい値を比較して、探したい値の方が小さければ左の子を、大きければ右の子を調べる
３.葉に行き着くまで上記を繰り返す。葉に行き着いても一致しなければ、探したい値は木の中にない

先ほどのイメージ図を見ながら考えると、例えば、最初に根を調べたとき、探したい値の方が小さかったとしたら、根の右部分木は調べる必要がない。これは、１回比較を行うたびに、探索する対象が半分になることを意味している。

この作業を繰り返すので、探索する対象はどんどん半分に減っていきます。これはつまり、二分探索と同じことが起きている訳である。したがって、二分探索木の探索の計算量は、二分探索と同じく O(log n) となる。

二分探索木の効率が落ちる例

二分探索木の効率を維持するためには、どの葉も同じような高さにあることが重要である。完全二分木という状態は、どの葉も同じ高さにある二分木のことであるが、これが理想的な状態と言える。なぜなら、どの節の値を探索しようとしても、必ず O(log n) 以内の計算量で済むからだ。要するに、二分探索並みの性能が保証される訳である。

しかし、要素の追加が、左部分木や右部分木の一方に偏ると、木構造ではなくリスト構造のような状態になってしまう。これは、次のような状態である。

この状態でも、二分探索木のルールは満たしているが、探索の性能は、二分探索レベルではなく、線形探索レベルになっている。つまり、計算量も O(log n) から O(n) に落ち込むということである。このような状態は、要素を昇順や降順に追加していけば容易に起こることなので、場合によっては重大な問題である。

対策として、常に木を整理して、葉の高さをできるだけ揃えるようにする方法がある。これは一般に、平衡木（バランス木）と呼ばれており、二分探索木であれば、平衡二分探索木と呼ぶ。平衡二分探索木には、いくつかの実装方法があります。例えば、AVL木、赤黒木、AA木などがある。

あるいは、可能であれば、昇順や降順に追加しないように、ランダム性を持たせるようにすれば、性能の低下を防げる。悪い状態を防げると仮定すると、二分探索木は、配列を二分探索することと比べて、要素の追加や削除が少ないコストで行えるという利点がある。配列の二分探索の場合は、常に配列全体をソート済みな状態にしなければならないから、要素の挿入や削除のたびに既存の要素をずらす操作が必要な配列では、効率が落ちる。つまり、配列を二分探索することは、探索自体は速くても、追加や削除が弱い。