Born Too Late

Ruby で BinaryTree (二分木) を実装してみた

この記事は個人的なメモです.

を読んでいて, 構造体の章に出てきた BinaryTree がよくわからないので, とりあえず Ruby で実装してみた.
単語をキーに, その回数を数えるだけの単純なプログラム.

BinaryTree::Node クラス

ツリー構造のノードを表すクラス.
単語, 回数, そして左/右のノードをプロパティとして持ちます.

RSpec

せっかくなので BDD (振る舞い駆動開発) の練習.

実行するとこのようになります.

$ rspec binarytree_spec.rb --format doc
BinaryTree::Node
  with word "foo" and no children
    it should behave like Node with word "foo"
      word
        should == "foo"
    it should behave like Node with no children
      left
        should be nil
      right
        should be nil
    size
      should == 1
    count
      should == 1
    words
      should == ["foo"]
    count_all
      should == 1
  with word "foo" and inserted a node with word "bar"
    it should behave like Node with word "foo"
      word
        should == "foo"
    it should behave like Node with one child with no children
      size
        should == 2
    right
      should be nil
    words
      should == ["bar", "foo"]
    count_all
      should == 2
    its child on the left
      it should behave like Node with no children
        left
          should be nil
        right
          should be nil
      word
        should == "bar"
      size
        should == 1
      count
        should == 1
      count_all
        should == 1
  with word "foo" and inserted a node with word "hoge"
    it should behave like Node with word "foo"
      word
        should == "foo"
    it should behave like Node with one child with no children
      size
        should == 2
    left
      should be nil
    words
      should == ["foo", "hoge"]
    count_all
      should == 2
    its child on the right
      it should behave like Node with no children
        left
          should be nil
        right
          should be nil
      word
        should == "hoge"
      size
        should == 1
      count
        should == 1
      count_all
        should == 1
  with word "foo" and inserted a node with word "foo"
    it should behave like Node with word "foo"
      word
        should == "foo"
    it should behave like Node with no children
      left
        should be nil
      right
        should be nil
    count
      should == 2
    words
      should == ["foo"]
    count_all
      should == 2
  with word "foo" and inserted a node with word "bar" 3 times
    it should behave like Node with word "foo"
      word
        should == "foo"
    right
      should be nil
    count
      should == 1
    size
      should == 2
    words
      should == ["bar", "foo"]
    count_all
      should == 4
    its child on the left
      word
        should == "bar"
      size
        should == 1
      count
        should == 3
      count_all
        should == 3
  with word "foo" and inserted a node with word "hoge" 3 times
    it should behave like Node with word "foo"
      word
        should == "foo"
    left
      should be nil
    count
      should == 1
    size
      should == 2
    words
      should == ["foo", "hoge"]
    count_all
      should == 4
    its child on the right
      word
        should == "hoge"
      size
        should == 1
      count
        should == 3
      count_all
        should == 3
  with word "a" and inserted nodes with word "b" ~ "j"
    size
      should == 10
    words
      should == ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]

Finished in 0.03146 seconds
57 examples, 0 failures

いやー, RSpec って楽しいですね.
PHP にもこういうの欲しい.

実行してみる

"to be or not to be" というフレーズ中に含まれる単語と, その回数を計算します.
結果は以下のとおり.

$ ruby example.rb
be (2)
not (1)
or (1)
to (2)

4 words.
6 nodes.

今度は C/C++ でも実装してみよう.
そして BTree や B+Tree についても勉強してみよう.

というわけで今日はここまで.