4724


「アルゴリズムとデータ構造」紀平拓男／春日伸弥 著
（<http://www.sbcr.jp/products/4797324198.html?sku=4797324198>）第6章において
、２分木のデータ追加、サーチ、削除のコードが紹介されています。  
それを今Ruby版に置き換えたつもりなのですが、  
53を追加、25を追加、85を追加、83を追加、52を追加したあと、53を削除すると「52が二つ表示される」不具合が生じます。  
どこを修正すればよいか教えていただけないでしょうか？

[code]

    # -*- coding: cp932 -*-
    
    # Node Class
    class Node
      attr_accessor :value, :left, :right
      def initialize(val)
        @value = val   # ノードが保持する値
        @left = nil    # 左側のノード
        @right = nil   # 右側のノード
      end 
    end
    
    # ノードを生成する
    def create_new_node(val)
      newNode = Node.new(val)
      return newNode
    end
    
    # ノードの追加
    def insert_tree(num, node)
      # 1つも挿入されていない場合
      if node == nil
        @tree_root = create_new_node(num)
        return
      end 
      # num が現在の node の値よりも小さい場合
      if node.value > num
        if node.left != nil
          insert_tree(num, node.left)
        else
          node.left = create_new_node(num)
        end
      # num が現在の node の値以上の場合
      else
        if node.right != nil
          insert_tree(num, node.right)
        else
          node.right = create_new_node(num)
        end
      end
    end
    
    # ノードの検索
    def find_value(node, val)
      # 自分より小さい値ならば、左側
      if node.value > val
        if node.left == nil
          return nil
        end
        return find_value(node.left, val)
      end
      # 自分より大きい値ならば、右側
      if node.value < val
        if node.right == nil
          return nil
        end
        return find_value(node.right, val)
      end
      return node 
    end
    
    # ノードの削除
    def delete_tree(val)
      node = @tree_root
      parentNode = nil
      direction = 0
      # while文で削除すべき対象を見つける
      while (node != nil && node.value != val)
        if node.value > val
          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
          end
          if direction == 1
            parent_node.right = node.right
          end
          if direction == 0
            @tree_root = node.right
          end
        else
          if direction == -1
            parent_node.left = node.left
          end
          if direction == 1
            parent_node.right = node.left
          end
          if 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("%d\n", node.value)
      print_tree(depth + 1, node.right)
    end
    
    def main
      action = nil
      while action != 0
        print_tree(0, @tree_root)
        printf("実行する操作のタイプを入力してください。\n 1 ：追加\t2 ：検索\t3 ：削除\t それ以外：終了>")
        action = gets.chomp.to_i
        case action
          when 1
            printf("1 ～100の範囲で，追加する数字を入力してください:")
            i = gets.chomp.to_i
            if i < 1 || i > 100
              continue
            end
            insert_tree(i, @tree_root)
          when 2
            printf("検索する数字を入力してください:")
            i = gets.chomp.to_i
            if find_value(@tree_root, i) != nil
              printf("%dを発見しました\n", i)
            else
              printf("%dは見つかりませんでした\n", i)
            end
          when 3
            printf("削除する数字を入力してください:")
            i = gets.chomp.to_i
            if delete_tree(i)
              printf("%dを削除しました\n", i)
            else
              printf("%dは見つかりませんでした\n", i)
            end
          else
            break
        end
      end
    end
    
    main
    
[/code]


CC BY-SA 3.0
2015-01-17T03:41:06.620
4721
2015-01-18T08:21:45.097
2015-01-17T06:17:31.397
5363
5363
question
ruby アルゴリズム binary-tree
２分木のデータ追加、サーチ、削除について


最後の `direction = -1` が `direction = 1` でないといけないっぽい。

追加で `else` を `elsif` に、 `parentNode` を `parent_node` にしました。

### パッチ差分

[code]

    @@ -62,9 +62,10 @@
     # ノードの削除
     def delete_tree(val)
       node = @tree_root
    -  parentNode = nil
    +  parent_node = nil
       direction = 0
       # while文で削除すべき対象を見つける
       while (node != nil && node.value != val)
         if node.value > val
           parent_node = node
    @@ -78,26 +79,22 @@
       end
       if node == nil
         return false
    -  end
    -  if node.left == nil || node.right == nil
    + end
    +  if (node.left == nil || node.right == nil)
         if node.left == nil
           if direction == -1
             parent_node.left = node.right
    -      end
    -      if direction == 1
    +      elsif direction == 1
             parent_node.right = node.right
    -      end
    -      if direction == 0
    +      elsif direction == 0
             @tree_root = node.right
           end
         else
           if direction == -1
             parent_node.left = node.left
    -      end
    -      if direction == 1
    +      elsif direction == 1
             parent_node.right = node.left
    -      end
    -      if direction == 0
    +      elsif direction == 0
             @tree_root = node.left
           end
         end
    @@ -108,7 +105,7 @@
         while left_biggest.right != nil
           parent_node = left_biggest
           left_biggest = left_biggest.right
    -      direction = -1
    +      direction = 1
         end
         node.value = left_biggest.value
         if direction == -1
    
[/code]

### コード (更新分)

[code]

    # -*- coding: cp932 -*-
    
    # Node Class
    class Node
      attr_accessor :value, :left, :right
      def initialize(val)
        @value = val   # ノードが保持する値
        @left = nil    # 左側のノード
        @right = nil   # 右側のノード
      end 
    end
    
    # ノードを生成する
    def create_new_node(val)
      newNode = Node.new(val)
      return newNode
    end
    
    # ノードの追加
    def insert_tree(num, node)
      # 1つも挿入されていない場合
      if node == nil
        @tree_root = create_new_node(num)
        return
      end 
      # num が現在の node の値よりも小さい場合
      if node.value > num
        if node.left != nil
          insert_tree(num, node.left)
        else
          node.left = create_new_node(num)
        end
      # num が現在の node の値以上の場合
      else
        if node.right != nil
          insert_tree(num, node.right)
        else
          node.right = create_new_node(num)
        end
      end
    end
    
    # ノードの検索
    def find_value(node, val)
      # 自分より小さい値ならば、左側
      if node.value > val
        if node.left == nil
          return nil
        end
        return find_value(node.left, val)
      end
      # 自分より大きい値ならば、右側
      if node.value < val
        if node.right == nil
          return nil
        end
        return find_value(node.right, val)
      end
      return node 
    end
    
    # ノードの削除
    def delete_tree(val)
      node = @tree_root
      parent_node = nil
      direction = 0
      # while文で削除すべき対象を見つける
      while (node != nil && node.value != val)
        if node.value > val
          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("%d\n",node.value)
      print_tree(depth + 1, node.right)
    end
    
    def main
      action = nil
      while action != 0
        print_tree(0, @tree_root)
        printf("実行する操作のタイプを入力してください。\n 1 ：追加\t2 ：検索\t3 ：削除\t それ以外：終了>")
        action = gets.chomp.to_i
        case action
          when 1
            printf("1 ～100の範囲で，追加する数字を入力してください:")
            i = gets.chomp.to_i
            if i < 1 || i > 100
              continue
            end
            insert_tree(i, @tree_root)
          when 2
            printf("検索する数字を入力してください:")
            i = gets.chomp.to_i
            if find_value(@tree_root, i) != nil
              printf("%dを発見しました\n", i)
            else
              printf("%dは見つかりませんでした\n", i)
            end
          when 3
            printf("削除する数字を入力してください:")
            i = gets.chomp.to_i
            if delete_tree(i)
              printf("%dを削除しました\n", i)
            else
              printf("%dは見つかりませんでした\n", i)
            end
          else
            break
        end
      end
    end
    
    main
    
[/code]


CC BY-SA 3.0
2015-01-17T04:38:19.397
4724
2015-01-17T04:45:46.403
2015-01-17T04:45:46.403
4978
4978
4721
answer


以前にあった質問 [２分木へのデータの追加について](https://ja.stackoverflow.com/questions/4704) での
katoy
の回答のコードでは、質問文にある追加・挿入操作を行うとつぎのように正常動作します。書籍のコードとは趣が異なるコードになっていますが、比較検討してみてはいかがでしょうか？(コード作成時に参照している
web ページも参照してください)

[code]

    実行する操作のタイプを入力してください。
     1:追加 2：検索  3:削除 4: 表示 9:終了>1
    追加する数字を入力してください:53
    53
    実行する操作のタイプを入力してください。
     1:追加 2：検索  3:削除 4: 表示 9:終了>1
    追加する数字を入力してください:25
        25
    53
    実行する操作のタイプを入力してください。
     1:追加 2：検索  3:削除 4: 表示 9:終了>1
    追加する数字を入力してください:85
        25
    53
        85
    実行する操作のタイプを入力してください。
     1:追加 2：検索  3:削除 4: 表示 9:終了>1
    追加する数字を入力してください:83
        25
    53
            83
        85
    実行する操作のタイプを入力してください。
     1:追加 2：検索  3:削除 4: 表示 9:終了>1
    追加する数字を入力してください:52
        25
            52
    53
            83
        85
    実行する操作のタイプを入力してください。
     1:追加 2：検索  3:削除 4: 表示 9:終了>3
    削除する数字を入力してください:53
        25
            52
    83
        85
    
[/code]


CC BY-SA 3.0
2015-01-17T06:40:04.223
4731
2015-01-18T08:21:45.097
2017-04-13T12:52:39.113
-1
2987
4721
answer