Ruby で BinaryTree (二分木) を実装してみた
2011-02-06 23:11:29
この記事は個人的なメモです.
を読んでいて, 構造体の章に出てきた 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 についても勉強してみよう.
というわけで今日はここまで.
