Rubyで実装して楽しむ古典データ構造再入門（平衡木編） - hama_duのブログCompetitive Programming Advent Calendar 2014 7日目です。 今回は古典的なデータ構造をRubyで実装してみます。 まず通常の木、二分木からはじめ、その次に二分探索木、そして二分探索木に少し機能を加え高性能にした平衡二分探索木を扱います。 冒険の地図 木 二分木 二分探索木 平衡二分探索木 ランダム挿入二分探索木 Treap 基本 木(Tree) 以下の図は木の例です。一番上にある頂点（丸）を根と呼びます。各頂点に直接ぶら下がっている頂点たちをまとめて子と呼びます。子を持たない頂点を葉と呼びます。 頂点同士は辺（棒）で結ばれています。木には、辺によってループができないという特徴があります。 木の性質 木には素晴らしい性質があります。各頂点の子を根と考える（上の部分は無視する）と、それぞれの子も木になっているという点です。それらの木のことを部分木と呼
