Возникли проблемы при установке объекта в ноль в бинарном дереве поиска ruby - PullRequest
Новая
       12

Возникли проблемы при установке объекта в ноль в бинарном дереве поиска ruby

0 голосов
/ 02 ноября 2019

Я реализую бинарное дерево поиска в ruby ​​и пытаюсь определить функцию для удаления значения из дерева. Дерево имеет значение @root, которое указывает на объект Node. который определяется как: 

  class Node
    attr_reader :value
    attr_accessor :left, :right

    def initialize value=nil
      @value = value
      @left = nil
      @right = nil
    end

    # Add new value as child node to self, left or ride
    # allows for duplicates, to L side of tree
    def insert new_value
      if new_value <= @value
        @left.nil? ? @left = Node.new(new_value) : @left.insert(new_value)
      elsif new_value > @value
        @right.nil? ? @right = Node.new(new_value) : @right.insert(new_value)
      end
    end
  end

Таким образом, все узлы содержат ссылки на своих дочерних элементов L & R. Все работает на дереве, вставка, обход, выполнение поиска в ширину (level-order-traverse) для возврата значения Node, если оно найдено.

Проблема, с которой я сталкиваюсь, заключается в попытке удалитьУзловой объект. Я не могу понять, как установить фактический ОБЪЕКТ равным nil или его дочернему элементу, например, вместо переназначения POINTER / переменной на nil, и объект все еще существует.

Дерево имеет две функции, которыедолжен сделать это (вы можете предположить, что breadth_first_search правильно возвращает соответствующий найденный узел, как и smalllest_r_child_of) 

  def remove value
    node = breadth_first_search(value)
    return false if node.nil?

    remove_node(node)
  end

  def remove_node node
    if node.left.nil? && node.right.nil?
      node = nil
    elsif !node.left.nil? && node.right.nil?
      node = node.left
    elsif node.left.nil? && !node.right.nil?
      node = node.right
    else
      node = smallest_r_child_of(node)
    end

    return true
  end

Я думал, что, передав объект фактического узла в remove_node, я мог бы вызвать node = ____ и тому подобное, чтобы переназначить фактический объект на что-то другое, но, насколько я могу судить, все, что он делает, это сбрасывает переменную / указатель аргумента node, фактически не переназначая мои данные.

У кого-нибудь есть какие-либо советы / предложения о том, как выполнить то, что я пытаюсь сделать?

1 Ответ

2 голосов
/ 02 ноября 2019

Вы не можете "установить объект на nil". Объект никогда не может изменить свой класс, это либо экземпляр Node, либо экземпляр NilClass, он не может в один момент времени быть экземпляром Node, а в другой момент времени - экземпляромиз NilClass.

Аналогично, объект не может изменить свою идентичность, объект # 4711 всегда будет объектом # 4711, однако nil является одиночным, поэтому существует только один nil, и он имеетодин и тот же идентификатор в течение всего времени жизни системы.

Что вы можете сделать, это связать переменную , которая ссылается на объект nil. Вы делаете противоположную операцию внутри вашего insert метода.

...