I have an interesting problem when building my Heap (challenge without using an array), and wondering if anyone can help. Where I am at so far, I can insert a number of built nodes and my Heap structure builds correctly via my output. However, when I go to #find a particular node, I receive nil because it appears my nodes aren't matching with the outputted tree. Keeping it as condensed as I can, here is what I have:
Node constructor & HeapTree #insert method
class Node
attr_accessor :title
attr_accessor :rating
attr_accessor :parent
attr_accessor :left
attr_accessor :right
def initialize(title, rating)
@title = title
@rating = rating
@parent = nil
@left = nil
@right = nil
end
end
class HeapSearchTree
def initialize
@root = nil
@heapsize = 1
end
def insert(node)
return nil if node.nil?
if @root.nil?
@root = node
else
current = @root
@heapsize += 1 #every insert increases heapsize; used for balancing heap
until current.left.nil? || current.right.nil?
if @heapsize % 2 == 0
current = current.left
else
current = current.right
end
end
#after figuring out to go left or right, find the first nil spot
if current.left.nil? && current.right.nil?
current.left = node
node.parent = current
elsif current.left.nil? && !current.right.nil?
current.left = node
node.parent = current
elsif !current.left.nil? && current.right.nil?
current.right = node
node.parent = current
end
#heapify by swapping titles and ratings because if I swap parent node for higher node it doesnt stick.
while node.rating >= node.parent.rating
if node.parent.rating <= node.parent.left.rating
temp_title = node.parent.title
temp_rating = node.parent.rating
node.parent.title = node.parent.left.title
node.parent.rating = node.parent.left.rating
node.parent.left.title = temp_title
node.parent.left.rating = temp_rating
elsif node.parent.rating <= node.parent.right.rating
temp_title = node.parent.title
temp_rating = node.parent.rating
node.parent.title = node.parent.right.title
node.parent.rating = node.parent.right.rating
node.parent.right.title = temp_title
node.parent.right.rating = temp_rating
end
end
end
end
def find(root=@root, movie_title)
if root.title == movie_title
puts "END OF RECURSION"
puts "movie_title entered: #{movie_title}"
puts "root.title: #{root.title}"
return root
else
loop = 0
left = find(root.left, title) if root.left
right = find(root.right, title) if root.right
left || right
loop += 1
puts loop
end
end
Picture of Problem
You will notice by inserting martian, the tree rearranges properly. However, when I tree.find(matrix.title) it passes in as martian.title and I get nil as a return.
I've been puzzled with this for awhile and cannot find anything via the web to help me. I am swapping titles and ratings with node.parent if node.parent's rating is less then passed in node. The node ID is not changing, just the information. Looking for a solution to make this work. Most will show a built array, but I do not want to use an array for learning purposes. Thanks
note
I've found my program breaks from the bubbling up from while loop in #insert. I'm now trying to move node and node.parent, but proving to be just as difficult.
solved my issue by recreating
#insert