У меня есть интересная проблема при создании моей кучи (вызов без использования массива) и интересно, может ли кто-нибудь помочь. Где я нахожусь до сих пор, я могу вставить несколько встроенных узлов, и моя структура кучи строит правильно через мой вывод. Однако, когда я перехожу на #find на определенный узел, я получаю nil, потому что он показывает, что мои узлы не совпадают с выведенным деревом. Держа его как конденсированное как я могу, вот что у меня есть:Ruby Binary Вставка кучи и поиск дилеммы
Узел конструктор & HeapTree #insert метод
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([email protected], 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
Изображение Проблема
Вы заметите, вставив martian, то дерево правильно перестраивается. Однако, когда я tree.find(matrix.title), он проходит как martian.title, и я получаю нуль в качестве возврата.
Я был озадачен с этим на некоторое время и не может найти что-либо через Интернет, чтобы помочь мне. Я заменяю названия и рейтинги node.parent, если node.parent рейтинг меньше, чем node. Идентификатор node: не изменение, только информация. Ищете решение для этой работы. Большинство будет показывать построенный массив, но я не хочу использовать массив для обучения. Благодаря
примечание
Я нашел свои программы перерывы из бурлит от в то время как петля в #insert. Сейчас я пытаюсь переместить node и node.parent, но оказалось, что это так же сложно.
Одна вещь, я замечаю, что, когда вы добавляете первый узел, вы не увеличивая '@ heapsize', так что ваш размер, кажется, один -off? – Coolness
'@ heapsize' меняется. Моя проблема находится внутри '# insert', когда я изменяю названия и рейтинги. К сожалению, каким-то образом он меняет данные моего объекта. Если я 'puts matrix.title' после вставки' martian', 'matrix.title = martian.title'. – DustinRW
То, что вы строите, является своего рода двоичным деревом, но это, конечно, не какая-то [куча] (https://en.wikipedia.org/wiki/Heap_ (data_structure)), о которой я знаю. Это определенно не [двоичная куча] (https://en.wikipedia.org/wiki/Binary_heap). Кроме того, куча не является особенно хорошей структурой данных для поиска, потому что вы должны выполнить исчерпывающий поиск дерева.Какую проблему вы пытаетесь решить с помощью этой «кучи»? –