Vantage Point Tree / VP树

じ☆ve冰风

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树的实现代码，不保证优化，仅供参考：

复制

测试工程下载：

             本帖来自P1论坛作者veal，因Project1站服务器在国外有时候访问缓慢不方便作者交流学习，经联系P1站长fux2同意署名转载一起分享游戏制作经验，共同为国内独立游戏作者共同创造良好交流环境，原文地址：https://rpg.blue/forum.php?mod=viewthread&tid=130819  若有侵权，发帖作者可联系底部站长QQ在线咨询功能删除，谢谢。