1
ヒープを構築するとき（配列を使わないでチャレンジ）、誰かが助けることができるかどうか疑問に思っています。私がこれまで行ってきたところでは、いくつかのビルドされたノードを挿入することができ、ヒープ構造は出力から正しく構築されます。しかし、特定のノード#findに行くと、私のノードが出力されたツリーと一致しないように見えるので、nilを受け取る。私ができるように凝縮としてそれを維持する、ここで私が持っているものです。Rubyバイナリヒープ挿入とジレンマの発見
ノードコンストラクタ& 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に満たない場合は、node.parentでタイトルとレーティングを交換しています。 node IDはではなく、であり、情報のみです。この仕事をするための解決策を探しています。ほとんどの場合、ビルドされた配列が表示されますが、私は学習目的で配列を使用したくありません。おかげ
ノート
私は#insertでから湧き上がっしばらくループから私のプログラムブレークを見つけました。私は現在、nodeとnode.parentを動かそうとしていますが、それほど難しいと証明しています。
を再作成することによって、私の問題を解決しました-オフ？ – Coolness
'@ heapsize'が変更されています。私の問題はタイトルと評価を並べ替えるときに '＃insert'の中にあります。残念ながら、何とか私のオブジェクトデータを変更します。 'martian'を挿入した後に' matrix.title'を置くと 'matrix.title = martian.title'となります。 – DustinRW
ビルドしているのは、ある種のバイナリツリーですが、私が知っていることは確かに[ヒープ]（https://en.wikipedia.org/wiki/Heap_（data_structure））ではありません。間違いなく[バイナリヒープ]（https://en.wikipedia.org/wiki/Binary_heap）です。さらに、ヒープは、ツリーの網羅的な検索を行う必要があるため、検索のための特に優れたデータ構造ではありません。この "ヒープ"で解決しようとしている問題は何ですか？ –