hama_duのブログスマートフォン用の表示で見るhama_duのブログノンジャンル記事置き場この広告は、90日以上更新していないブログに表示しています。今回は古典的なデータ構造をRubyで実装してみます。通常の木、二分木からはじめ、その次に二分探索木、そして二分探索木に少し機能を加え高性能にした平衡二分探索木を扱います。木(Tree)以下の図は木の例です。上にある頂点(丸)を根と呼びます。各頂点に直接ぶら下がっている頂点たちをまとめて子と呼びます。子を持たない頂点を葉と呼びます。頂点同士は辺(棒)で結ばれています。木には、辺によってループができないという特徴があります。木には素晴らしい性質があります。各頂点の子を根と考える(上の部分は無視する)と、それぞれの子も木になっているという点です。それらの木のことを部分木と呼びます。頂点に整数値を持つ木を、以下のように再帰的に定義できます。])])イメージとしては、Treeのインスタンス全てが部分木になります。そのうち、一番上にあるインスタンスが根になります。この木の機能を使うときは、主に根に対してメソッドを呼ぶことで行います。入っている頂点があるかどうかを探したいとします。ヒントがないので真面目に全部の頂点を探すしかないのですが、木の性質「各子供以下もまた木である」により、再帰関数を書いて簡単に実装できます。根からメソッドを呼ぶ。根からメソッドを呼ぶ。子以下の答えは全部わかっている、と仮定することです。子の更に子の処理はどうしよう・・・とか余計なことは考えなくていいんです。深さ優先探索の再帰による実装はこの後の内容でも頻出なのでここでマスターしておきましょう。Tree)と呼びます。二分木はよりシンプルに実装できます。endendこのように。要素の探索も次の通り簡単です。次は、二分探索木を紹介します。この木は二分木の一種ですが頂点の並びに特徴があります。常に満たすという点です。下記のように定義してみました。クラス変数で、その場所が空であることを示します。してもよいのですが、こうしておくと無駄な条件文を書かずに済むので実装が楽になります。二分探索木の性質のおかげで、木の中である値を持つ頂点を探すのは容易です。返す)関数を作りましょう。右の子について上記プロセスを繰り返す(右の子に以降の処理を任せ、自分はその結果を返す)この時の探索コストは、最大で木の高さに比例します。通常の木において、全頂点を探さなければならなかった時代から大きく進歩しました。二分探索木に要素を追加するときは、探索と同じ要領で上記ルールを満たすような位置を探してやればよいです。受け取り、要素を追加する関数を作りましょう。同じ値が入る場合はとりあえず考えないことにします。