0

I was trying to implement a ruby binary search tree, creating, adding and printing node is fine, the problem rose when i was implementing #delete

(i will post the code below) the structure for this tree is nested binary nodes (why? I am no nothing about ruby pointers)

class BinaryNode
  attr_accessor :value
  attr_accessor :left_node
  attr_accessor :right_node

  def initialize (value = nil, left_node = nil, right_node = nil)
    @value = value
    @left_node = left_node
    @right_node = right_node
  end
end

the left and right nodes will be another binary node, and it goes on

so when i want to insert a node (which is fine), i use a temp binary node to traverse the tree and when i reach my goal (if no duplicates encountered) I simply make the temp's child (left or right according to comparison), but why this works, i mean i copied the binary node, AND modified the COPIED one, but works,

here is the #insert if you need more insight

def insert (value, node = @root)
  if value == node.value
    return nil
  elsif value > node.value
    if node.right_node == nil
      node.right_node = BinaryNode.new(value)
    else
      insert value, node.right_node
    end
  else
    if node.left_node == nil
      node.left_node = BinaryTree.new(value)
    else
      insert value, node.left_node
    end
  end
end

now when i apply the same logic for deleting node (currently stuck with leaves, have not yet explored and tested other cases) it fail, here is the code if my statement is not sufficient

def delete (value)
  temp = @root
  sup_node = temp
  while temp.value != value
    puts "currently at #{temp.value}"
    if temp.value > value
      temp = temp.left_node
      puts "going left"
    elsif temp.value < value
      temp = temp.right_node
      puts "going right"
    end
    target_node = temp
    puts "target_node: #{target_node.value}"
  end

  if target_node.right_node == nil
    puts "right node is nil"
    if target_node.left_node == nil
      puts "left node is nil"
      puts "deleting node"
      target_node = nil
    else
      temp_node = target_node.left_node
      target_node.left_node = nil
      target_node = temp_node
    end
  else
    target_node_right = target_node.right_node
    last_left_node = target_node_right
    while last_left_node.left_node != nil
      last_left_node = last_left_node.left_node
    end
    if last_left_node.right_node == nil
      target_node.value = last_left_node.value
      last_left_node = nil
    else
      last_left_parent_node = target_node_right
      while last_left_parent_node.left_node != last_left_node
        last_left_parent_node == last_left_parent_node.left_node
      end
      #some chaos going on here
      last_left_parent_node.right_node = last_left_node.right
      last_left_parent_node.left_node = nil

      target_node.value = last_left_node.value
      last_left_node = nil
    end
  end
end

My main question why an approach works fine in one situation but break in another, and how ruby can track copied data, and modify original, I am not interested in the binary tree algorithms it self (any problem probably will be easily searchable)

Thanks in advance

by the way sorry for being long, if you want the whole code (although I think what i copied is sufficient) you can find it on github

Lukas Baliak
  • 2,849
  • 2
  • 23
  • 26
  • 1
    "i copied the binary node, AND modified the COPIED one" - you didn't copy a node, you copied a reference to a node. That's why modification done through one reference can be observed through another. – Sergio Tulentsev Sep 08 '20 at 13:13
  • 1
    You are setting variable `target_node` to NIL value, you just removing the reference from variable not the node it self., you need to set `temp.right_node` or `temp.left_node` to nil to remove it. – Lukas Baliak Sep 08 '20 at 13:15
  • @sergio can you point me to a reference to learn more about this stuff, or what is it's technical term, knowing this stuff will basicly solve the problem – Allaw Hussein Sep 08 '20 at 13:19
  • @LukasBaliak yeah some how similar to sergio, it would be much appreciated if i get the technical term to search it – Allaw Hussein Sep 08 '20 at 13:20
  • 1
    @AllawHussein the terms are "pass by reference" and "pass by value" https://stackoverflow.com/questions/1872110/is-ruby-pass-by-reference-or-by-value – Sergio Tulentsev Sep 08 '20 at 13:21
  • Btw in your case its `target_node` will be always last definition of `temp` variable. So you can save information of `right_node` or `left_node` inside variable as `target_node = :right_node` and then remove it as `temp.send("#{target_node}=", nil)` – Lukas Baliak Sep 08 '20 at 13:23
  • Man thanks for cooperation, i will apply these solutions when i am able to – Allaw Hussein Sep 08 '20 at 13:24
  • "it fail" is not a precise enough error description for us to help you. *What* doesn't work? *How* doesn't it work? What trouble do you have with your code? Do you get an error message? What is the error message? Is the result you are getting not the result you are expecting? What result do you expect and why, what is the result you are getting and how do the two differ? Is the behavior you are observing not the desired behavior? What is the desired behavior and why, what is the observed behavior, and in what way do they differ? https://idownvotedbecau.se/itsnotworking/ – Jörg W Mittag Sep 08 '20 at 13:57
  • @JörgWMittag got it, next time i will improve (not this time because my question is actually answered) – Allaw Hussein Sep 08 '20 at 14:51

0 Answers0