在二叉搜索树节点方法中使用 Comparable Mixin

Question

我正在使用 Ruby 实现二叉搜索树。我实现了一个可比较的 mixin 来方便地比较树中的 Node 对象（比较数据属性），但是当“叶子？”时我发现了一个 NoMethodError。正在调用方法： <=>': undefined method 'data' for nil:NilClass (NoMethodError)

这是我的实现：

# Node Class
class BstNode

include Comparable

attr_accessor :left
attr_accessor :right
attr_reader :data

def initialize(val)
    @data = val
    @left = nil
    @right = nil
end

def <=>(node)
    return self.data <=> node.data
end

def leaf?
    return self.left == nil && self.right == nil
end

end

# Tree Class
class BstTree

attr_accessor :root

def initialize(arr)
    @root = build_tree(arr)
end

def build_tree(arr)
    arr.each.with_index do |val, i|
        if i == 0
            self.root = BstNode.new(arr[i])
        else
            insert_node(val)
        end
    end
    return self.root
end

def insert_node(val, node = self.root)
    
    curr = node
    left = val < curr.data ? true : false

    if curr.leaf?
        if left
            curr.left = BstNode.new(val)
        else
            curr.right = BstNode.new(val)
        end
    elsif curr.left == nil && left
        curr.left = BstNode.new(val)
    elsif curr.right == nil && !left
        curr.right = BstNode.new(val)
    else
        return left ? insert_node(val, curr.left) : insert_node(val, curr.right)
    end
    return true
end

end

tree = BstTree.new([4])

puts tree.insert_node(6)
puts tree.insert_node(8)

如有任何意见或建议，我们将不胜感激。

Answer 1

基本上 Comparable 模块在对象上实现了类似 <, <=, ==, >, >=, between? 的方法（完整列表在这里 https://docs.ruby-lang.org/en/2.5.0/Comparable.html）并且所有这些都基于 <=>(space-船舶操作员).

因此，当您将 BstNode 与 nil 进行比较时，例如 BstNode.new(8) == nil，== 方法将调用 space-ship 运算符来解析比较。因为它的实现会尝试在传递的任何内容上调用 data 方法，所以即使在 nil 上它也会尝试这样做（相当于调用 nil.data）。

像这样给 space-ship 添加安全导航器(&.)，如果你认为你会很好。

def <=>(node)
    return self.data <=> node&.data
end

在二叉搜索树节点方法中使用 Comparable Mixin

Using Comparable Mixin in Binary Search Tree Node Methods

ruby

binary-search-tree

mixins