回転の実装

回転の実装

　ここではAVL木のように完全なバランスを目指すのはさておき、単純に回転してみましょう。右回転をPHPで書いてみます（図3-1）。

　いかがでしょうか？図2-8で示したことを素直に実行しています。最終的なrootに元の左側のノードが来ることがわかると思います。同様に左回転も作れますがここでは省きます。

　さて部分的な理屈ばかり書いてきましたので、全体的かつ実践的なことをしましょう。前回、リスト構造にデータを追加して、後でそこから探索をしました。ここでも同様に、次のことをします。

（1）木構造に要素を追加する
（2）その構造から要素を探す

　はじめに、要素を追加するプログラムを作りますが、追加した結果を目に見えるようにしないとわかりません。それをprintNode()としましょう。図3-2のようになるでしょう。ノードのレベルを表すためにスペースを印字している点にだけ注意していただければ、再帰呼び出しをしているだけです。

挿入と探索

　これで木を印刷することができるようになりましたので、アプリケーションを作りましょう。リンクトリストのときと同様に、はじめにデータを登録して、後でそれを探索します。

　リンクトリストのときのサンプルプログラムとほとんど同じですが、図3-3のようなテスト用プログラムを作りました。$rootの代わりに$anchorすればリンクトリスト版と同じです。木構造を操作する関数（insert() など）は、別のモジュールbtree.phpで定義されています。

　これを実行すると図3-4のようになります。首を左に傾けて見ると、木に見えませんか？この結果を印刷して「枝」を手で書き込んだものを図3-5に示します。この結果を見た限りでは、そこそこバランスのとれた木になっていますね。たまたまですがmodula-2を根とする木になりました。

　ここで「たまたま」と言ったのにはわけがあります。

　二分探索木へ要素を追加（挿入）する場合、挿入するものの順番によっては結果が異なります。要素がソートされているという条件は保証されますが、AVL木を構成しない限り、データの発生順序によってはバランスの崩れ方が変わるためです。

　試しに、データを挿入する前にシャッフルしてから同じことをしてみます（元の「順序」の意味がメチャメチャになりますが...）。上のテストプログラム（図3-3）のforループの前にshuffle($langs)を入れるだけです。結果は図3-6の通りです。今度はlispが根になりました。このプログラムのソースコードはこちら（http://www.thinkit.co.jp/images/article/159/2/15921.zip）からダウンロードできます（15921.zip/3 KB）。みなさんも試してみてください。実行するたびに表示が変わるはずです。shuffleのためにどの順序で木への挿入が起こるかわからないためです。

　では、最後にこの木の探索をしましょう。

　根から探し始めますが、キーの値を比較して小さければ左の枝へ、大きければ右へ進みます。それをプログラムにすると図3-7のようになります。プログラム自体はとても単純ですね。キーが一致するまで探します（見つからないこともありますが）。

　さて、もうお気づきかもしれませんが、木がバランスよくなっていれば、この探索は二分探索と同様の性能が出ます。木が偏っていると、一方の側をひたすら探すことになりますので、最悪の場合はリンクトリストをたどるのと同じように線形探索の性能しか出ません。

　つまり、二分探索木はその名の通り、二分探索とほぼ同等の性能ができることがわかります。動的に増減するデータを扱いの基本的な構造と言えます。データベースの索引部などには、二分木ではありませんがバランス木が使われます。アプリケーションで直接このような構造をプログラミングすることはあまりないと思いますが、基本ソフトウエアのさまざまな場面で使われていることを少しばかり、知っていただけると幸いです。

　前回と今回で、動的に増減するデータに対する線形探索と二分探索を取り上げました。オーダーはそれぞれO(n^2)とO(log2(n))です。次回は、O(1)であるアルゴリズムを取り上げましょう。O(1)であるということは、データ量にかかわらず一定の時間で目的のものが見つかるというものです。そんな夢のような方法があるのでしょうか？それは次回のお楽しみ。

　なお、本稿の執筆にあたって、以下を参考にしました。

Niklaus Wirth『Algorithms + Data Structures = Programs』Prentice-Hall,（発行年：1976）