Having trouble setting an object to nil in ruby binary search tree

Question

I'm implementing a binary search tree in ruby, and I'm attempting to define a function to remove an value from the tree. The Tree has a @root value that points to a Node object. which is defined as such:

  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

Thus, the nodes all hold references to their L & R children. Everything works on the tree, inserting, traversing, performing a breadth-first-search (level-order-traverse) to return a Node value, if found.

The problem I'm having is when trying to remove a Node object. I can't figure out how to set the actual OBJECT to nil, or to its child, for example, rather than reassigning a POINTER/variable to nil and the object still existing.

Tree has two functions that are supposed to do this (you can assume that breadth_first_search correctly returns the appropriate found node, as does smallest_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

I thought that by passing in the actual node object to remove_node, that I could call node = ____ and the like to reassign the actual object to something else, but all it does, as far as I can tell, is reset the node argument variable/pointer, while not actually reassigning my data at all.

Does anyone have any tips/suggestions on how to accomplish what I'm trying to do?

Changing node has zero impact on the caller. Everything you do in remove_mode manipulates a local variable and does nothing to the node inside of remove(value). — tadman
– tadman, Commented Nov 2, 2019 at 18:27
@Jörg has given a good answer, which I do not think is likely to be improved upon, but you do yourself a disservice by selecting an answer so quickly, as it may well discourage other answers. Moreover, it may be considered a bit rude by those still working on their answers. Many askers wait a minimum of a couple of hours before making a selection; some wait considerably longer to allow readers around the world who are then fast asleep a chance to offer answers. There is no rush to make a selection. Please bear that in mind in future. — Cary Swoveland
– Cary Swoveland, Commented Nov 2, 2019 at 18:44

Jörg W Mittag · Accepted Answer · 2019-11-02 18:25:39Z

2

You cannot "set an object to nil". An object can never change its class, it either is an instance of Node or it is an instance of NilClass, it cannot at one point in time be an instance of Node and at another point in time be an instance of NilClass.

Likewise, an object cannot change its identity, object #4711 will always be object #4711, however, nil is a singleton, so there is only one nil and it has the same identity during the entire lifetime of the system.

What you can do is to bind the variable which references the object to nil. You are doing the opposite operation inside your insert method.

answered Nov 2, 2019 at 18:25

Jörg W Mittag

371k79 gold badges457 silver badges666 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

C. Norwood Over a year ago

Thanks Jörg. That makes sense. I guess I will need add a little extra logic to keep track of/identify parent Nodes efficiently, so I can set the references to the Nodes-to-be-removed to nil, thus sending them to the garbage collector.

Collectives™ on Stack Overflow

Having trouble setting an object to nil in ruby binary search tree

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related