4780


「アルゴリズムとデータ構造」紀平拓男／春日伸弥 著
（<http://www.sbcr.jp/products/4797324198.html?sku=4797324198>）第6章において
、２分木を使ったマップのコードが紹介されています。  
前回の質問「２分木のデータ追加、サーチ、削除について」の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に対応させる値

「２分木のデータ追加、サーチ、削除について」のHiroshi
Yamamotoさんのコードでは同じことを行っても上手くいっているので、difff《ﾃﾞｭﾌﾌ》で比較したのですが、main以外大きな違いがなくどこが間違いかわかりません。  
どこを修正すればよいか教えていただけないでしょうか？

[code]

    # -*- 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
    
[/code]


CC BY-SA 3.0
2015-01-18T05:45:15.653
4774
2015-01-18T07:40:50.280
2015-01-18T06:21:25.030
5363
5363
question
ruby アルゴリズム binary-tree
２分木を使ったマップについて


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

そのため，`delete_tree` の `node.value = left_biggest.value` 部分に  
`node.key = left_biggest.key` を追加したらいいと思います．

### 差分

[code]

    @@ -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
    
[/code]

### コード（追加部分の抜粋）

[code]

      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
    
[/code]

### 実行結果

[code]

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


CC BY-SA 3.0
2015-01-18T06:31:47.197
4780
2015-01-18T06:37:45.720
2015-01-18T06:37:45.720
5447
5447
4774
answer