ツリー構造（２分木）
7月 6th, 2008 admin Posted in アルゴリズムとデータ構造 | 2 Comments » 
今回も「アルゴリズムとデータ構造シリーズ」です。本日は「ツリー構造」について。
ツリー構造とは
ツリー構造とは樹形図のようになったデータ構造のことです。Windowsのファイル構造はツリー構造ですね。
難しそうに感じますが、以前やったリスト構造では、データが次のノードへのポインタを一つしかもっていなかったものを複数にするというだけで実現できます。
2分木
今回はツリー構造の中でも２分木と呼ばれるものを実装しました。2分木とはツリー構造の中でも各ノードが最大2個の子ノードしかもたない構造のことです。さらに今回は2分木の中でも、子ノードの並べ方に順序をつけ検索性をアップしたタイプ（左が小さい、右が大きい）にし、挿入・検索・削除ができるようにしました。
まとめ
挿入や、検索よりも削除が面倒でした。
ツリー構造にはいろいろな応用パターンがあっておくが深そうです。本書では常に検索効率の良いAVL木やデータベースエンジンでよく使用されているB木（B+木）の解説もあり非常に勉強になりました。
コード
今回はコードが長いので最後にしました
RUBY:
-
#Binary Tree
-
$KCODE = "SJIS"
-
-
class Node
-
attr_accessor :left,:right,:value
-
def initialize(value)
-
@value = value
-
@left = nil
-
@right = nil
-
end
-
end
-
-
class BinaryTree
-
attr_accessor :tree_root
-
-
def initialize
-
@tree_root = nil
-
end
-
-
def create_new_node(value)
-
Node.new(value)
-
end
-
-
def insert_tree(value, node)
-
if node.nil?
-
@tree_root = self.create_new_node(value)
-
return
-
end
-
-
if node.value> value
-
unless node.left.nil?
-
self.insert_tree(value,node.left)
-
else
-
node.left = self.create_new_node(value)
-
end
-
else
-
unless node.right.nil?
-
self.insert_tree(value,node.right)
-
else
-
node.right = self.create_new_node(value)
-
end
-
end
-
end
-
-
def find(node, value)
-
if node.value> value
-
return nil if node.left.nil?
-
return self.find(node.left, value)
-
end
-
-
if node.value <value
-
return nil if node.right.nil?
-
return self.find(node.right, value)
-
end
-
-
node
-
end
-
-
def delete(value)
-
direction = 0
-
parent_node = nil
-
node = @tree_root
-
-
while(node != nil && node.value != value) do
-
if(node.value> value)
-
parent_node = node
-
node = node.left
-
direction = -1
-
else
-
parent_node = node
-
node = node.right
-
direction = 1
-
end
-
end
-
-
return 0 if node.nil?
-
-
if(node.left.nil? || node.right.nil?)
-
#左右どちらかがnilだった場合
-
if(node.left.nil?)
-
parent_node.left = node.right if direction == -1
-
parent_node.right = node.right if direction == 1
-
@tree_root = node.right if direction == 0
-
else
-
parent_node.left = node.left if direction == -1
-
parent_node.right = node.left if direction == 1
-
@tree_root = node.left if direction == 0
-
end
-
else
-
#両者共nilでなかった場合
-
left_biggest = node.left
-
parent_node = node
-
direction = -1
-
while(left_biggest.right != nil) do
-
parent_node = left_biggest
-
left_biggest = left_biggest.right
-
direction = 1
-
end
-
-
node.value = left_biggest.value
-
if(direction == -1)
-
parent_node.left = left_biggest.left
-
else
-
parent_node.right = left_biggest.left
-
end
-
end
-
true
-
end
-
-
def print_tree(depth, node)
-
return if node.nil?
-
-
self.print_tree(depth+1, node.left)
-
(0...depth).each{|i|
-
printf(" ")
-
}
-
printf("%d\n",node.value)
-
self.print_tree(depth+1,node.right)
-
end
-
end
-
-
tree = BinaryTree.new
-
10.times{|i|
-
tree.insert_tree(rand(99),tree.tree_root)
-
}
-
tree.print_tree(0,tree.tree_root)
-
-
i = nil
-
while i != 0 do
-
print "現在のツリー\n"
-
tree.print_tree(0,tree.tree_root)
-
-
print "コマンドを入力して下さい\n0:終了 1:追加 2:検索 3:削除\n"
-
i = gets.chomp.to_i
-
-
case i
-
when 1
-
print "1~100の範囲で、追加する数字を入力してください："
-
j = gets.chomp.to_i
-
tree.insert_tree(j ,tree.tree_root) if (j>= 1 && j <= 100)
-
when 2
-
print "検索する数字を入力してください："
-
j = gets.chomp.to_i
-
if tree.find(tree.tree_root,j)
-
printf("%dは見つかりました。 \n",j)
-
else
-
print("見つかりませんでした。\n")
-
end
-
when 3
-
print "削除する数字を入力してください："
-
j = gets.chomp.to_i
-
if tree.delete(j)
-
printf("%dは削除しました。 \n",j)
-
else
-
print("見つかりませんでした。\n")
-
end
-
end
-
end
※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。
7月 6th, 2008 at 3:36:06
[...] 2分木（binary tree） はてなに追加 MyYahoo!に追加 del.icio.usに追加 livedoorClipに追加 10 Responses to “Rubyでアルゴリズムとデータ構造” [...]
7月 8th, 2008 at 3:28:03
[...] まず前章でやったツリー構造を使うのがツリーマップである。キーとなる文字列をstrcmp()関数などで数値化して2分木で保持するというものだ。ツリーのどこにデータがあるかによって計算時間にばらつきがでるので安定していないのが欠点である。 [...]