図解！二分探索のプログラミング

実装

　リンクトリストのときと同様にclassを使って定義します（図2-1）。このclass Nodeのイメージを絵にすれば図2-2のようになります。leftとrightはほかのノードへの枝を表すポインタです。つながったイメージは図2-3のようになります。この図で下にある2つのノードは枝を持たないので「葉」です。よってポインタ部分がnullになっています。

　また、根を表すノードへのポインタをrootというものが保持するものとします。木自体が「からっぽ」の場合はこのrootの値がnullになります。リンクトリストのアンカー（anchor）に相当します。

　リスト構造の場合と同様、この構造に対しても、配列を初期化するようにはデータを入れることはできません。ひとつひとつの要素のための構造を作って、ポインタをつないでいかなければなりません。

　そしてここで重要なことは、要素を入れる際にどこに新しい要素を入れるか、ということです。探索木ですからこれらの要素はある関係を持っています。あるノードについてみたとき、そのキーより小さいキーを持っているノードは、必ず左側にあります。また、大きいキーを持っているノードは右の枝にあります。

　リンクトリストで、挿入ソートをする際に「自分が入るべき位置を」探してポインタをつけました。それと同じように、二分探索木では「自分が入るべき位置」に自分を入れなければなりません。

　今、図1-1の状態で新たにキーが「B」のものを入れるとします。どこに入るでしょう？

　「B」は「A」よりも右に、「C」よりも左に入ります。ですから図2-4のように「A」の右下にぶら下がります。

実装と平衡木

　さて、この手順をプログラムにしてみましょう。「適切な」入れ場所を探して要素を挿入することを考えます。キーを比較しながら、左か右に「降りて」行き、枝がないところに自分自身を挿入します。

　PHPで書けば図2-5のようになるでしょう。このプログラムでは図2-6のようにはならないことに注意してください。

　図2-4でも図2-6でもちょっとバランスがよくないですね。根から見て左側が大き過ぎます。できれば図2-7のようになるとよいのですが。

　この図2-7のように完全にバランスがとれている木は平衡木（AVL木）と呼ばれます。AVL木は「どのノードにおいてもその左部分木の高さと右部分木の高さの差が1以下になる木」のことです。

　ここではAVL木を作ることはしませんが、もう少しバランスをよくすることを考えます。そのために、木を「回転」させることを考えます。木の回転とは、次のようなことです。

　もし、あるノードの左側の部分が「大き過ぎる」場合には、左部分木の根を木全体の根の位置に持ってきて、左側を小さく、右側を大きくすることです（図2-8）。

　図2-8でαとβはそれぞれノードを表します。T1、T2、T3は、部分木を表します。三角形の大きさは、部分木の大きさをイメージ的に表していると思ってください。ここで、T1に含まれるノードのキーはみなαのキーよりも小さいはずです。これをT1
T1
　ここでは「右回転」をしていますが、回転後も上記の関係が維持されていることを確認してください。

　しかし、残念ながらこのような回転が必ずしもよい結果をもたらすとは限りません。左右の部分木の大きさ（あるいは高さ）をできるだけ等しくしたいのですが、回転の結果がそうなるとは限りません。図2-8ではT1をT2よりも大きく書いていますが、T2が大きい場合は回転した後の方がかえってバランスが悪くなってしまうこともあるでしょう。