Ruby 二进制堆插入和查找困境

Question

我在构建堆时遇到了一个有趣的问题（不使用数组的挑战），想知道是否有人可以提供帮助。到目前为止，我可以插入许多已构建的节点，并且我的堆结构可以通过我的输出正确构建。但是，当我转到 #find 一个特定节点时，我收到 nil 因为我的节点似乎与输出的树不匹配。尽可能保持简洁，这是我所拥有的：

节点构造器&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(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

问题图片

您会注意到，通过插入 martian，树会正确地重新排列。但是，当我 tree.find(matrix.title) 它作为 martian.title 传递时，我得到 nil 作为 return.

我对此困惑了一段时间，无法通过网络找到任何帮助我的东西。如果 node.parent 的评分低于 node，我将与 node.parent 交换标题和评分。 node ID 没有变化，只是信息。寻找解决方案来完成这项工作。大多数会显示一个内置数组，但我不想将数组用于学习目的。谢谢

注意

我发现我的程序在 #insert 中的 while 循环冒泡时中断了。我现在正在尝试移动 node 和 node.parent，但事实证明同样困难。

Answer 1

这是正确的，因为 HeapSearchTree#insert 改变节点而不是正确交换它们。您的插入代码会改变节点的标题和评级。变量 matrix 绑定到标题为 "The Matrix" 的节点，但通过插入方法将其更改为 "The Martian"。

[2] pry(main)> tree = HeapSearchTree.new
[3] pry(main)> matrix = Node.new("The Matrix", 87)
[4] pry(main)> martian = Node.new("The Martian", 92)

[5] pry(main)> tree.insert(matrix)
=> #<Node:0x007f92348c7c10
 @left=nil,
 @parent=nil,
 @rating=87,
 @right=nil,
 @title="The Matrix">
[6] pry(main)> matrix.object_id
=> 70132961787400
[7] pry(main)> matrix.title
=> "The Matrix"

[8] pry(main)> tree.insert(martian)
=> nil

[9] pry(main)> matrix.object_id
=> 70132961787400
[10] pry(main)> matrix.title
=> "The Martian"

[11] pry(main)> tree.find(matrix.title)
END OF RECURSION
movie_title entered: The Martian
root.title: The Martian

这表明绑定到变量 matrix 的节点正在显示正确的标题，因此搜索该标题 returns 会得到正确的结果。正如您提到的，我会重新实现插入以正确交换节点。

Answer 2

通过重新创建 #insert

解决了我的问题

def insert(root, node)
    root = @root
    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

    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

  #if rating > (greater than) its parents rating 
    while node.rating >= node.parent.rating
      loop = 1
      temp_parent = node.parent
      temp_parent_right = node.parent.right
      temp_parent_left = node.parent.left
      temp_node_left = node.left
      temp_node_right = node.right
  # if node is greater then its parent and node is to the left of parent
      if node.parent.parent.nil? && node == node.parent.left
        puts "im here on left and parents parent is nil"
        node.right = node.parent.right
        node.parent = node.parent.parent
        node.left = temp_parent

        node.left.parent = node
        node.left.left = temp_node_left
        node.left.right = temp_node_right

        if !node.right.nil?
          node.right.parent = node
        end

        @root = node
        break
  # if node is greater then its parent and node is to the right of parent
      elsif node.parent.parent.nil? && node == node.parent.right
        puts "im here on right and parents parent is nil"

        node.left = node.parent.left
        node.parent = node.parent.parent 
        node.right = temp_parent 

        node.right.parent = node
        node.right.right = temp_node_right
        node.right.left = temp_node_left
        node.left.parent = node

        @root = node
        break


      elsif !node.parent.nil? && node == node.parent.left
        puts "im here on left and my parents parent is not nil"

        if node.parent.parent.left == node.parent
          node.parent.parent.left = node
          node.parent.parent.left.parent = node.parent.parent
          node.left = temp_parent
          node.right = temp_parent_right
          node.left.parent = node
          unless node.right.nil?
            node.right.parent = node
          end
          node.left.left = temp_node_left
          node.left.right = temp_node_right
        elsif node.parent.parent.right == node.parent
          node.parent.parent.right = node
          node.parent.parent.right.parent = node.parent.parent
          node.left = temp_parent
          node.right = temp_parent_right
          node.left.parent = node
          unless node.right.nil?
            node.right.parent = node
          end
          node.left.left = temp_node_left
          node.left.right = temp_node_right
        end

      elsif !node.parent.nil? && node == node.parent.right

        if node.parent.parent.right == node.parent
          node.parent.parent.right = node
          node.parent.parent.right.parent = node.parent.parent
          node.right = temp_parent
          node.left = temp_parent_right
          node.right.parent = node
          unless node.left.nil?
            node.left.parent = node
          end
          node.left.left = temp_node_left
          node.left.right = temp_node_right
        elsif node.parent.parent.left == node.parent
          node.parent.parent.left = node
          node.parent.parent.left.parent = node.parent.parent
          node.left = temp_parent
          node.left = temp_parent_right
          node.right.parent = node
          unless node.right.nil?
            node.right.parent = node
          end
          node.left.left = temp_node_left
          node.left.right = temp_node_right
        end

      end
    end
  end

Ruby 二进制堆插入和查找困境

Ruby Binary Heap insertion and finding dilemma

ruby

heap

binary-tree

ruby-on-rails