データ構造とアルゴリズム

二分探索木

　二分探索木は木のような生え方をしたデータの記録方法で、単純なルールしかないので理解しやすいです。

二分探索木のルール

サンプル

平衡木（AVL木）

　平衡木とは二分探索木がいびつなかたちになってしまって検索の効率が悪くなるのを防ぐことができる木です。Adelson-Velsky（アデルソン＝ヴェルスキー）とLandis（ランディス）という人たちが世界で最初に平衡木を考案したのでAVL木と名付けられています。

値をセットするたびに木をチェックするAVL木

　AVL木はデータを登録するたびに木をチェックして、足の長さが２以上にならないように修正を入れるロジックがある木です。以下に１から順に見ていきます。

ＡＶＬ木の二重回転

木を二重回転という回転のさせかたをして均衡を取り戻す方法があります。
たとえば以下のような例です。

この例ではすべての節（数字が入っている丸）の高さの差が２未満で釣り合っている状態です。

ここで新しく４７を追加してみます。すると以下のようになります。

４７の足を新しく足す順序は以下のとおりです。
まずは根から見ていきます。
４７は根の５０より小さいので左へ行きます（３０の節に来ます）。
次に３０より大きいので右へ行きます（４０の節に来ます）。
次に４０より大きいので右へ行きます（４６の節に来ます）。
４６の節には足がないので４６より大きい４７は４６の右の節になります。

さらに、
４７が新しく加わったのでチェックを行います。
４６➤４０➤３０とさかのぼって見ていくと、３０を頂点とする木までの高さの差は２未満ですので、３０を頂点とする木は均衡が取れています。

ところが一番上の根（５０の節）から見ると、５０の右の８０を頂点とする木の高さは３なのに対して、３０を頂点とする左の木は５段目に届いているので、この３０の木の高さは５です。したがって高さの差が２になってしまいました。

このような場合は下の図のように三角形の木を連想するとわかりやすくなります。

上の図では、３０の節から見て右側の４０を頂点とする三角形が高すぎるために起こっている不均衡（LR型不均衡）でしたので、４０の木を二重回転という動作で均衡化します。
不均衡を検出した節は根の５０であり、実際に不均衡の原因を作ったのは、４０の木ですから、４０を新しい根にして５０を右にずらします。
４０より下の節は一旦分解して保留しておきます。

ＬＲ型右２重回転をした結果です。
４０の左にあった３５は新しく３０の右の節になります。
４０の右にあった４６と４７は５０の下につけます。
こうすることで二分木のルール（左の節は小さい数字で、右の節が大きい数字）のルールを保ったまま、すべての節の高さが２未満に揃いました。

もしも原因を作った木が、不均衡を検出した節（このサンプルの場合は根）の右側にあった場合は、ＲＬ型不均衡として根を左にずらして原因となった木の節を根に持っていきます。

実際にテストを受ける際のポイント

AVL木の問題がでたら、頭で考えるのではなく、即興で紙に書いてみるとわかりやすくなります。

Ｂ木

Ｂ木は二分探索木とちがって視覚的に理解しやすいです。
Ｂ木もいろいろルールはありますが、一番シンプルに解説していきます。

基本のかたち

　以下の図はＢ木の基本的な形です。一番上の枠は「根」と呼びます。２段目以降は何段あってもすべて「節」と呼びます。筆者が勝手に命名した節は次の節または葉への「ポインタ」と、そのポインタを検索するためのキーが入る「インデックス」があります。このインデックスがあるおかげで、目的のデータがどこにあるか検討がつくわけです。そして実際のデータ（葉）は必ず一番下の段にぶら下がります。

上記の図では、葉も１段と数えるので、段数が３段のＢ木となります。

もしも１つの節の中にすべての葉が入ってしまう場合は、その節が「節の無い根」になります。

サンプル

Ｂ木の動きを追ってみましょう。