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