Метод удаления в бинарном дереве поиска: исходный узел не удаляется

Question

Я делаю метод удаления в бинарном дереве поиска, но когда я нахожу удаляемый узел, я не могу удалить его. Я смотрел на многие разные вещи и не могу понять это для себя. Я включил класс, который строит узлы, и класс, который строит дерево (build_tree). Метод delete находится в классе Tree ...

class Node
  attr_accessor :data, :left, :right

  def initialize(data)
    @data = data
    @left = nil
    @right = nil
  end

end

def build_tree(array)
  root_value = array[0]
  if array.length == 0
    return
  elsif array.length == 1 
    root = Node.new(array)
  elsif array.length == 2
    if array[1] > root_value
      root = Node.new(root_value)
      root.right = Node.new(array[1])
    else
      root = Node.new(root_value)
      root.left = Node.new(array[1])
    end  
  else
    left_side = []
    right_side = []

    for i in 0...array.length
      if array[i] < root_value
        left_side << array[i]
      elsif array[i] > root_value
        right_side << array[i]
      end
    end

  root = Node.new(root_value)
  root.left = build_tree(left_side)
  root.right = build_tree(right_side)

  end
  root

end

class Tree

  def initialize(array)
    @root = build_tree(array)
  end

  def inorder(root=@root)
    if root
      inorder(root.left)
      puts(root.data)
      inorder(root.right)
    end
  end

  #!!!
  def delete(root=@root, value)
    if root.data == nil
      return root
    elsif root.data < value
      delete(root.right, value)
    elsif root.data > value
      delete(root.left, value)
    else
     # no child node
      if root.right == nil && root.left == nil
        #v Something must be wrong with this here v
        root = nil

      end
    end
    root
  end

end

test_array = [10,7,14,20,1,5,8]

new_tree = Tree.new(test_array)

new_tree.delete(20)

new_tree.inorder()

#prints [1,5,7,8,10,14,20]

Узел со значением 20 все еще находится в дереве. Как мне исправить это, чтобы он был удален?

Answer 1

Настройка root = nil просто обнуляет местную ссылку. Это не ноль родительского значения right или left, которое вы бы хотели удалить из дерева.

Один из способов это сделать - передать блок, который вызывается, если у ребенка нет дочерних узлов. Это захватывает требуемую операцию и позволяет повторяющемуся вызову метода вызывать ее, если он определяет, что удаление действительно должно быть.

  def delete(root=@root, value, &block)
    return root if root.data.nil?

    if root.data < value
      delete(root.right, value) { root.right = nil }
    elsif root.data > value
      delete(root.left, value) { root.left = nil }
    elsif root.right.nil? && root.left.nil?
      yield if block_given?
    end

    root
  end

(Дополнительно: здесь есть потенциальная ошибка. Первые два условия не делают t проверьте, равны ли root.right или root.left нулями, и попытаются вернуться в них независимо. Возможно, вы захотите добавить дополнительных охранников для такой возможности.)