2分木を使ったマップについて
「アルゴリズムとデータ構造」紀平拓男/春日伸弥 著 (http://www.sbcr.jp/products/4797324198.html?sku=4797324198)第6章において 、2分木を使ったマップのコードが紹介されています。
前回の質問「2分木のデータ追加、サーチ、削除について」のHiroshi Yamamotoさんの回答をもとにRuby版で置き換えました。
しかし、key:6を追加、key:9を追加、key:7を追加、key:5を追加したあと、key:6を削除すると以下の太字のような不具合が生じます。
5 :5に対応させる値
6 :6に対応させる値
7 :7に対応させる値
9 :9に対応させる値
0:終了1:挿入2:探索3:削除>3
削除する文字列:>6
削除しました
6 :5に対応させる値
7 :7に対応させる値
9 :9に対応させる値
「2分木のデータ追加、サーチ、削除について」のHiroshi Yamamotoさんのコードでは同じことを行っても上手くいっているので、difff《デュフフ》で比較したのですが、main以外大きな違いがなくどこが間違いかわかりません。
どこを修正すればよいか教えていただけないでしょうか?
# -*- coding: cp932 -*-
# Node Class
class Node
attr_accessor :key, :value, :left, :right
def initialize(num, val)
@key = num # ノードのキー
@value = val # ノードが保持する値
@left = nil # 左側のノード
@right = nil # 右側のノード
end
end
# ノードを生成する
def create_new_node(num, val)
newNode = Node.new(num, val)
return newNode
end
# ノードの追加
def insert_tree(num, val, node)
# 1つも挿入されていない場合
if node == nil
@tree_root = create_new_node(num, val)
return
end
if node.key > num
if node.left != nil
insert_tree(num, val, node.left)
else
node.left = create_new_node(num, val)
end
else
if node.right != nil
insert_tree(num, val, node.right)
else
node.right = create_new_node(num, val)
end
end
end
# ノードの検索
def find_value(node, num)
if node.key > num
if node.left == nil
return nil
end
return find_value(node.left, num)
end
if node.key < num
if node.right == nil
return nil
end
return find_value(node.right, num)
end
return node
end
# ノードの削除
def delete_tree(num)
node = @tree_root
parent_node = nil
direction = 0
# while文で削除すべき対象を見つける
while (node != nil && node.key != num)
if node.key > num
parent_node = node
node = node.left
direction = -1
else
parent_node = node
node = node.right
direction = 1
end
end
if node == nil
return false
end
if node.left == nil || node.right == nil
if node.left == nil
if direction == -1
parent_node.left = node.right
elsif direction == 1
parent_node.right = node.right
elsif direction == 0
@tree_root = node.right
end
else
if direction == -1
parent_node.left = node.left
elsif direction == 1
parent_node.right = node.left
elsif direction == 0
@tree_root = node.left
end
end
else
left_biggest = node.left
parent_node = node
direction = -1
while left_biggest.right != nil
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
return true
end
def print_tree(depth, node = nil)
if node == nil
return
end
print_tree(depth + 1, node.left)
i = 0
while i < depth
printf ""
i += 1
end
printf("%s :%s \n", node.key, node.value)
print_tree(depth + 1, node.right)
end
def main
action = nil
while action != 0
print_tree(0, @tree_root)
printf("0:終了1:挿入2:探索3:削除>")
action = gets.chomp.to_i
case action
when 1
printf("挿入する文字列(キー):>")
key = gets.chomp.to_i
printf("キーに対応させる値:>")
value = gets.chomp
insert_tree(key, value, @tree_root)
when 2
printf("探索する文字列:>")
i = gets.chomp.to_i
node_found = find_value(@tree_root, i)
if node_found != nil
printf("対応する値は%sです\n", node_found.value)
else
printf("見つかりませんでした\n")
end
when 3
printf("削除する文字列:>")
i = gets.chomp.to_i
if delete_tree(i)
printf("削除しました\n")
else
printf("見つかりませんでした\n")
end
end
end
end
main