KD-tree/寻找k维树的n个最近邻居和删除

本文主要是介绍KD-tree/寻找k维树的n个最近邻居和删除，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

KD树在查找和搜索方面表现出了良好的性能，但是在删除节点时却十分麻烦。

为了降低删除的性能开销，一个自然而然的想法就是不去真正删除KD树的子节点，而是给每一个子节点打上一个标记，当遇到带标记的子节点时忽略就是。

建立哈希表，储存要删除的节点：

    // Mark deleted points     // node is not deleted actually.     Set<Integer> hash = new HashSet<Integer>();

 public boolean deletePoint(Point point) {           if (isPointIn(point)) {             hash.add(point.hashCode());             return true;         }         return false;     }

在判断条件里加上许多的hash.contain(point)来实现虽然可行，但这个逻辑实在是十分复杂。

回到KD树寻找最近的节点的依据，是它和节点的距离远近。如果我们将已经标记过的节点的距离替换成一个很大(最好是无穷，但可惜不能）的数，KD树在比较的时候就会自然略过这些点：

if (hash.contains(point.hashCode()))             Distance = 9999999;

这篇关于KD-tree/寻找k维树的n个最近邻居和删除的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！