hama_duのブログ

ノンジャンル記事置き場

Rubyで実装して楽しむ古典データ構造再入門（平衡木編）

アルゴリズム プログラミング Ruby

Competitive Programming Advent Calendar 2014 7日目です。

今回は古典的なデータ構造をRubyで実装してみます。 まず通常の木、二分木からはじめ、その次に二分探索木、そして二分探索木に少し機能を加え高性能にした平衡二分探索木を扱います。

冒険の地図

  • 木
    • 二分木
      • 二分探索木
        • 平衡二分探索木
          • ランダム挿入二分探索木
          • Treap

基本

木(Tree)

以下の図は木の例です。一番上にある頂点（丸）を根と呼びます。各頂点に直接ぶら下がっている頂点たちをまとめて子と呼びます。子を持たない頂点を葉と呼びます。

頂点同士は辺（棒）で結ばれています。木には、辺によってループができないという特徴があります。

f:id:hama_DU:20141207161041p:plain

木の性質

木には素晴らしい性質があります。各頂点の子を根と考える（上の部分は無視する）と、それぞれの子も木になっているという点です。それらの木のことを部分木と呼びます。

頂点に整数値を持つ木を、以下のように再帰的に定義できます。

class Tree
  attr_reader :value, :children

  def initialize(v, c=[])
    @value = v
    @children = c
  end
end

# 1つの頂点から成る木
t1 = Tree.new(1)

# 子を複数持つ木
t2 = Tree.new(1, [
  Tree.new(2),
  Tree.new(3),
  Tree.new(4, [ Tree.new(5), Tree.new(6) ])
])

イメージとしては、Treeのインスタンス全てが部分木になります。そのうち、一番上にあるインスタンスが根になります。 上の例だと、t1 や t2 が根になります。

この木の機能を使うときは、主に根に対してメソッドを呼ぶことで行います。

深さ優先探索

この木から、値 v が入っている頂点があるかどうかを探したいとします。 ヒントがないので真面目に全部の頂点を探すしかないのですが、木の性質「各子供以下もまた木である」により、再帰関数を書いて簡単に実装できます。

def search(v)
  # 自身のvalueと等しければtrue
  return true if @value == v
  @children.each { |c|
    # 部分木以下に見つかればtrue
    return true if c.search(v)
  }
  # それ以外ならfalse
  false
end

# 根からメソッドを呼ぶ。t1以下から2を探す
t1.search(2)  # false

# 根からメソッドを呼ぶ。t2以下から5を探す
t2.search(5)  # true

再帰はややこしいですが、実装のコツは 頂点 v について考えるときは、v の子以下の答えは全部わかっている、と仮定することです。子の更に子の処理はどうしよう・・・とか余計なことは考えなくていいんです。

f:id:hama_DU:20141207164947p:plain

深さ優先探索の再帰による実装はこの後の内容でも頻出なのでここでマスターしておきましょう。

二分木

木のうち、全頂点において子の数が最大で2つまでのものを二分木(Binary Tree)と呼びます。 二分木はよりシンプルに実装できます。各頂点において左の部分木、右の部分木があればよいから、

class BinaryTree
  attr_reader :value, :left, :right

  def initialize(v, l=nil, r=nil)
    @value = v
    @left = l
    @right = r
  end
end

このように。要素の探索も次の通り簡単です。

def search(v)
  # 自身と一致してたら true を返す
  return true if @value == v

  # 左の子以下に見つかれば true
  return true if @left != nil and @left.search(v)

  # 右の子以下に見つかれば true
  return true if @right != nil and @right.search(v)

  # 何処にもなかった
  false
end

二分探索木

次は、二分探索木を紹介します。この木は二分木の一種ですが頂点の並びに特徴があります。 それは、(左の子の値) < (自分の値) < (右の子の値) を常に満たすという点です。

f:id:hama_DU:20141207161056p:plain

二分探索木のクラス定義

下記のように定義してみました。 @@empty はクラス変数で、その場所が空であることを示します。代わりに nil にしてもよいのですが、こうしておくと無駄な条件文を書かずに済むので実装が楽になります。

class BinarySearchTree
  @@empty = BinarySearchTree.new()

  attr_accessor :value, :left, :right

  def initialize(v, l=@@empty, r=@@empty)
    @value = v
    @left = l
    @right = r
  end
end

要素の探索

二分探索木の性質のおかげで、木の中である値を持つ頂点を探すのは容易です。 引数として 値 v を受け取り、値 v を持つ頂点を返す（もし存在しなければ @@empty を返す）関数を作りましょう。

def search(v)
  return @@empty if self == @@empty
  return self if @value == v
  if v < @value
    # 小さければ左へ
    @left.search(v)
  else
    # 多きければ右へ
    @right.search(v)
  end
end
  • 自身が @@empty の場合、それ以下にはもう頂点がないので @@empty を返す
  • 自分の値と v を比べる。
    • 同じ場合、目的はその頂点だったので、その頂点を返す
    • 小さい場合
      • 左の子について上記プロセスを繰り返す（左の子に以降の処理を任せ、自分はその結果を返す）
    • 大きい場合
      • 右の子について上記プロセスを繰り返す（右の子に以降の処理を任せ、自分はその結果を返す）

この時の探索コストは、最大で木の高さに比例します。通常の木において、全頂点を探さなければならなかった時代から大きく進歩しました。

要素の追加

二分探索木に要素を追加するときは、探索と同じ要領で上記ルールを満たすような位置を探してやればよいです。 引数として 値 v を受け取り、要素を追加する関数を作りましょう。 ※ 同じ値が入る場合はとりあえず考えないことにします。

def add(v)
  # 空だったら、新しく作る
  return self.class.new(v) if self == @@empty
  if v < @value
    # 小さければ、左へ。もし @left == @@empty の場合はここでリンクが貼られる
    @left = @left.add(v)
  else
    # 大きければ、右へ。もし @right == @@empty の場合はここでリンクが貼られる
    @right = @right.add(v)
  end
  # 自分自身を返す
  self
end
  • 自身が @@empty の場合、新しい頂点を作成して返す
  • まず、根の値と v を比べる。
    • 小さい場合
      • 左の子について add(v) を呼び、上記プロセスを繰り返す（帰ってきた頂点を @left に代入する）
    • 大きい場合
      • 右の子について add(v) を呼び、上記プロセスを繰り返す（帰ってきた頂点を @right に代入する）

例えば、二分探索木に値 7 を追加するときは以下の様な動きになります。

f:id:hama_DU:20141207161541p:plain

f:id:hama_DU:20141207161547p:plain

f:id:hama_DU:20141207161550p:plain

f:id:hama_DU:20141207161552p:plain

要素を根に挿入する

先程は葉に要素を追加する関数を紹介しましたが、少し手間を加えることで要素を根に挿入する（追加した頂点が新たな根になる）関数を作ることもできます。 根挿入のメリットは、最近追加した頂点が上の方に来ることです。 実世界では最近追加したものを探したい場面はしばしば訪れるので、この性質は有用です。

要素を根に挿入するには、まず通常通り要素を葉に置いてから、それを回転操作によって根まで持ちあげるというステップを取ります。回転操作には左回転と右回転があります。

左回転

自分の右の子を、左に回転して「持ち上げ」る操作です。 そのとき、元々の右の子の左のリンクが新たに自分を指すように、 自分の右のリンクは、元々の右の子の左を指すようにします。

実装は以下のとおりです。

def rotate_left()
  # 右の頂点を tmp に保存
  tmp = @right
  # 自分の右頂点を、右の頂点の左の子へ
  @right = tmp.left
  # 右の頂点の左の子は自分を指すように
  tmp.left = self
  return tmp
end

右回転

自分の左の子を、右に回転して「持ち上げ」る操作です。 そのとき、元々の左の子の右のリンクが新たに自分を指すように、 自分の左のリンクは、元々の左の子の右を指すようにします。

実装は以下のとおりです。

def rotate_right()
  # 左の頂点を tmp に保存
  tmp = @left
  # 自分の左頂点を、左の頂点の右の子へ
  @left = tmp.right
  # 左の頂点の右の子は自分を指すように
  tmp.right = self
  return tmp
end

これらの回転関数を使うことで、根挿入の関数を作ることができます。

def self.add_root(root, v)
  # 最下部にまず追加する
  return self.new(v) if root == @@empty

  if v < root.value
    # 自分の左に持ってくる
    root.left = self.add_root(root.left, v)
      
    # 右回転で持ち上げる
    root = root.rotate_right()
  else
    # 自分の右に持ってくる
    root.right = self.add_root(root.right, v)
      
    # 左回転で持ち上げる
    root = root.rotate_left()
  end
  
  # 持ち上げた頂点を返す
  root
end

少し実装がトリッキーですが、やってることは図示すると以下のとおりです。

f:id:hama_DU:20141207161952p:plain

これを・・・

f:id:hama_DU:20141207161957p:plain

こうして

f:id:hama_DU:20141207162000p:plain

こうして

f:id:hama_DU:20141207162002p:plain

こうじゃ

平衡木

二分探索木において、データの入る順番が偏るとまずいことになります。 たとえば、

  • 1 -> 2 -> 3 -> 4 -> 5 -> 6
  • 1 -> 6 -> 2 -> 5 -> 3 -> 4

といった順番だと木の高さが 6 (= 頂点数) となり、探索したり、要素を新しく入れたりする最悪コストが高くなってしまいます。

そこで、左右の高さがなんとかバランスするようにして、木の高さを抑える試みが成されています。 このような木を平衡木 (Balanced Tree)と呼びます。 平衡木にはいくつか種類がありますが、今回はそのうち

  • ランダム挿入二分探索木
  • Treap

を紹介します。

ランダム挿入二分探索木

ランダム挿入二分探索木の基本的なアイデアは、「そもそも挿入の順番がランダムならば、木はバランスするんじゃないのか」 という考えです。実際このアイデアは正しく、挿入順がランダムなら木の高さが N になることはほとんどありません。これを実現するために、要素を追加するときに少し工夫をします。

その工夫とは要素を追加するときに、ランダムで根に挿入するか、通常通り挿入するか決めるということです。 より詳細に述べると、通常の探索通りにある頂点に来たとき、

  • ある頂点 v 以下の部分木のサイズ（頂点の数）を X と置く。
    • 1/(X+1) の確率で、頂点を v の位置に根挿入する。
    • 1-1/(X+1) の確率で、左右どちらかの子において同様のプロセスを繰り返す。

これにより、新しい頂点は根から本来挿入されるべき点のどの場所にも入る確率があります。 また、全体で見るとどの頂点も根に選ばれる確率が等しいことがわかります。

具体的な実装は以下の通りです。新たに @count というインスタンス変数を導入してます。これは各頂点での部分木のサイズを表しています。この値は、add とか rotate_{left,right} を行う度に更新が必要です。

def add(v)
  # 空の場合はそこに追加
  return self.class.new(v)  if self == @@empty
    
  # 部分木サイズ(=count)+1の確率でこの場所に追加する
  return self.class.add_root(self, v) if rand(@count+1) == 0

  # 後は通常通り
  if v < @value
    @left = @left.add(v)
  else
    @right = @right.add(v)
  end
    
  # 部分木のサイズを更新
  self.update
    
  # 自身を返す
  self
end

# 部分木のサイズ更新。（左の子）+（右の子）+ 1(自分)
def update()
  @count = @left.count + @right.count + 1
end

早速、データを入れて実験してみましょう。「木の高さ」を調べる関数を書いて、

# 高さを調べる
def depth()
  # @@empty なら高さ 0
  return 0 if self == @@empty

  # それ以外なら左と右の大きい方に+1する
  [@left.depth, @right.depth].max + 1
end

100頂点を昇順に挿入した時の高さを調べてみます。

# 値1を持つ頂点からのみ成る木を作る
rbst = RandomizedBinarySearchTree.new(1)

# 2〜100まで順に追加
(2..100).each do |v|
  # add は新しい根を返すので rbst に再代入する
  rbst = rbst.add(rbst, v)
end
# 高さを出力
p rbst.depth()

# > 何回か実行したら12〜17ぐらいでした

このように、高さがバランス（欲を言えば 27 = 128 > 100 なので高さ7にしたいけど・・・）していることが確認できます。 ちなみに、ここで使っているランダム性の選択は非常に重要です。ランダムだからといって適当でよいわけではありません。 例えば、rand(@count) == 0 の部分を rand(2) == 0 に変えてみるとどうでしょうか。試してみてください。

以下はフル実装のgistへのリンクです。

randomized_binary_search_tree.rb

Treap

ランダム性を用いた平衡木のバリエーションとして、Treap というものがあります。 Treapはより実装がシンプルです。各頂点に値とは別の優先度を割り当て、根への挿入時に（親の優先度）＜（自分の優先度）を満たす限り回転操作を繰り返します。優先度が高い頂点ほど上に来るイメージです。

これでも、部分木を含め根がランダムに選ばれることが保証されます。 また、追加と探索だけなら、部分木のサイズを保つ必要がなくなるので、若干実装が楽になります。 詳しい実装の説明は省略しますが、以下にコメントを付けた実装例を示します。（追加と探索をサポート）

treap.rb

ところで、Treapの高さについて確率的に議論する楽しい問題に、 UTPC2011-J : 乱択平衡分二分探索木 があります。興味のある人は考えてみましょう。

おしまい

みなさまも、普段お使いの言語でデータ構造の実装にチャレンジしてみてはいかがでしょうか。普段の開発とは一味違ったプログラミングが楽しめるはず！

※今回は「k番目の値を探す」「木を分割／併合する」といった操作は時間の都合上端折りました。読者への練習問題とします（丸投げ）