1

「アルゴリズムとデータ構造」紀平拓男/春日伸弥 著 (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
1
  • 紙にデータの変化を書いていって流れを追ってみるとかすればいいんじゃないかな。 Commented 2015年1月18日 7:40

1 件の回答 1

1

削除するノードの左右両方に子供が存在する際に,
左の子孫の最大値のものを代入すると思いますが,
その時に value だけ代入して key を代入していないのが原因でしょうか.

そのため,delete_treenode.value = left_biggest.value 部分に
node.key = left_biggest.key を追加したらいいと思います.

差分

@@ -104,6 +104,7 @@
       left_biggest = left_biggest.right
       direction = 1
     end
+    node.key = left_biggest.key
     node.value = left_biggest.value
     if direction == -1
       parent_node.left = left_biggest.left

コード(追加部分の抜粋)

  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.key = left_biggest.key  # 追加した行
    node.value = left_biggest.value
    if direction == -1
      parent_node.left = left_biggest.left
    else
      parent_node.right = left_biggest.left
    end
  end

実行結果

5 :5に対応させる値
6 :6に対応させる値
7 :7に対応させる値
9 :9に対応させる値
0:終了1:挿入2:探索3:削除>3
削除する文字列:>6
削除しました
5 :5に対応させる値
7 :7に対応させる値
9 :9に対応させる値

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。