Vantage Point Tree / VP树 - Project1

#==============================================================================
# ■ VPTree
#------------------------------------------------------------------------------
# 用于metric space的搜索树
#==============================================================================
class VPTreeNode
#--------------------------------------------------------------------------
# ● 实例变量
#--------------------------------------------------------------------------
attr_accessor :parent, :left, :right, :data, :threshold, :dist_proc
#--------------------------------------------------------------------------
# ● 初始化
#--------------------------------------------------------------------------
def initialize(args, &block)
# 如果传递了块
if block != nil
@dist_proc = block
# 没有传递块的话就用distance(other)
else
@dist_proc = Proc.new{|a, b|
a.distance(b)
}
end
# 大于两个数据的话，随机取一个数据为这个节点的data（这里取中间一个）
# 用其他数据到这个数据的距离的中位数作为threshold，
# 小于等于threshold加入左子树，大于threshold加入右子树
if args.size > 2
median = args.size / 2
@data = args.delete_at(median)
args.sort!{|a, b| @dist_proc.call(@data, a) <=> @dist_proc.call(@data, b)}
@threshold = @dist_proc.call(@data, args[median - 1])
@left = VPTreeNode.new(args[0, median], &@dist_proc)
@left.parent = self
@right = VPTreeNode.new(args[median, args.size - median], &@dist_proc)
@right.parent = self
# 如果只剩2个数据的话
elsif args.size == 2
@data = args[0]
@threshold = @dist_proc.call(@data, args[1])
@left = VPTreeNode.new(args[1, 1], &@dist_proc)
@left.parent = self
# 只剩一个数据的话
elsif args.size == 1
@data = args[0]
end
end
#--------------------------------------------------------------------------
# ● 是否叶节点
#--------------------------------------------------------------------------
def leaf?
return (@left == nil && @right == nil)
end
#--------------------------------------------------------------------------
# ● 输出
#--------------------------------------------------------------------------
def inspect
return "<Node: #{@data.inspect}, @threshold = #{@threshold}>"
end
#--------------------------------------------------------------------------
# ● 检查节点有效性
#--------------------------------------------------------------------------
def node_valid?
if @left != nil
@left.each{|child_data|
if @dist_proc.call(@data, child_data) > @threshold
return false
end
}
end
if @right != nil
@right.each{|child_data|
if @dist_proc.call(@data, child_data) <= @threshold
return false
end
}
end
return true
end
#--------------------------------------------------------------------------
# ● 检查树有效性
#--------------------------------------------------------------------------
def valid?
each{return false if !node_valid?}
return true
end
#--------------------------------------------------------------------------
# ● 迭代小于等于dist的所有data
#--------------------------------------------------------------------------
def each_within(sample, dist, &block)
# 获得sample到data的距离
sample_dist = @dist_proc.call(@data, sample)
# 如果这个距离小于dist，就迭代data
if sample_dist <= dist
yield(@data)
end
# 需要迭代左子树的情况
if @left != nil && @threshold + dist >= sample_dist
@left.each_within(sample, dist, &block)
end
# 需要迭代右子树的情况
if @right != nil && sample_dist + dist > @threshold
@right.each_within(sample, dist, &block)
end
end
#--------------------------------------------------------------------------
# ● 迭代
#--------------------------------------------------------------------------
def each(&block)
yield(@data)
@left.each(&block) if @left != nil
@right.each(&block) if @right != nil
end
end

复制代码