VP树是由Peter N. Yianilos 在1993年的论文
Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces中提出的一种搜索度量空间(Metric Space)的二叉搜索树。
用途：
最邻近搜索。任何在度量空间的数据都可以生成VP树进行搜索。
度量空间定义（来自
http://zh.wikipedia.org/wiki/%E5%BA%A6%E9%87%8F%E7%A9%BA%E9%97%B4）：
1. d(x, y) ≥ 0 (非负性)
2. d(x, y) = 0 当且仅当 x = y (不可区分者的同一性)
3. d(x, y) = d(y, x) (对称性)
4. d(x, z) ≤ d(x, y) + d(y, z) (三角不等式)。
在RM中可能的应用：
1. 坐标系就是度量空间，可用于给出一个点，寻找一定半径内的所有点（测试工程的测试就是这个）
2. 拼写纠错，词汇之间的编辑距离也是度量距离
优点：
搜索复杂度：O(log(N))，当然随着搜索半径的增加，复杂度会增加。例如你有一本10万字的词典，给你一个词，搜索所有只差一个字母的词，全部词遍历一次的话要访问10万个词，用VP树最优化的情况下只需要访问(log(100000)/log(2)约等于17)个词。
缺点：
由于VP树是静态的，无法在其身上实现插入和删除操作。
大量距离查询操作，所以最好能缓存距离查询。
更先进的最邻近搜索算法请参考下面的链接或Google。
扩展阅读：
http://en.wikipedia.org/wiki/Nearest_neighbor_search
下面是VP树的实现代码，不保证优化，仅供参考：
- #==============================================================================# ■ 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 "" 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 @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 endend复制代码
测试工程下载：
本帖来自P1论坛作者veal，因Project1站服务器在国外有时候访问缓慢不方便作者交流学习，经联系P1站长fux2同意署名转载一起分享游戏制作经验，共同为国内独立游戏作者共同创造良好交流环境，原文地址：
https://rpg.blue/forum.php?mod=viewthread&tid=130819 若有侵权，发帖作者可联系底部站长QQ在线咨询功能删除，谢谢。
Vantage Point Tree / VP树: VPTree.rar