ツリー構造（２分木）

7月 6th, 2008 admin Posted in アルゴリズムとデータ構造 |

ツリー構造とは

ツリー構造とは樹形図のようになったデータ構造のことです。Windowsのファイル構造はツリー構造ですね。
難しそうに感じますが、以前やったリスト構造では、データが次のノードへのポインタを一つしかもっていなかったものを複数にするというだけで実現できます。

2分木

今回はツリー構造の中でも２分木と呼ばれるものを実装しました。2分木とはツリー構造の中でも各ノードが最大2個の子ノードしかもたない構造のことです。さらに今回は2分木の中でも、子ノードの並べ方に順序をつけ検索性をアップしたタイプ（左が小さい、右が大きい）にし、挿入・検索・削除ができるようにしました。

まとめ

挿入や、検索よりも削除が面倒でした。
ツリー構造にはいろいろな応用パターンがあっておくが深そうです。本書では常に検索効率の良いAVL木やデータベースエンジンでよく使用されているB木（B+木）の解説もあり非常に勉強になりました。

コード

今回はコードが長いので最後にしました

PLAIN TEXT

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でアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。

toyosystem | Rubyでアルゴリズムとデータ構造 Says:
7月 6th, 2008 at 3:36:06

[...] 2分木（binary tree）はてなに追加 MyYahoo!に追加 del.icio.usに追加 livedoorClipに追加 10 Responses to “Rubyでアルゴリズムとデータ構造” [...]

toyosystem | マップとハッシュ（ハッシュ値生成） Says:
7月 8th, 2008 at 3:28:03

[...] まず前章でやったツリー構造を使うのがツリーマップである。キーとなる文字列をstrcmp()関数などで数値化して2分木で保持するというものだ。ツリーのどこにデータがあるかによって計算時間にばらつきがでるので安定していないのが欠点である。 [...]