我认为，正如您在评论中提到的那样，KD树或KNN树的增量构造的问题是，树最终将变得不平衡，并且您无法通过简单的树旋转来解决平衡问题并保持一致性。至少，重新平衡任务并非微不足道，并且绝对不会在每次插入时都这样做。通常，人们会选择使用批处理方法来构建树，插入一堆新点，并允许树在某一点之前变得不平衡，然后重新平衡。

要做的非常相似的事情是为M点批量构建数据结构，将其用于M’点，然后使用M +
M’点批量重建数据结构。由于重新平衡不是正常的快速算法，对于树我们是熟悉的快速算法，因此重建不一定会比较慢，并且在某些情况下重建会更快（取决于点进入增量算法的方式）。

话虽如此，如果您采用重建方法，那么编写的代码量，调试的难度以及其他人对代码的理解的难度就会大大减少。如果这样做，则可以使用批处理方法，并保留尚未插入树中的点的外部列表。可以使用蛮力方法来确保所有这些都不比树中的任何一个更近。

下面是一些与Python实现/讨论有关的链接，但我还没有发现任何明确声称是增量的链接。祝好运。

http://www.scipy.org/Cookbook/KDTree

http://cgi.di.uoa.gr/~compgeom/pycgalvisual/kdppython.shtml

http://sites.google.com/site/mikescoderama/Home/kd-tree-
knn

http://en.wikipedia.org/wiki/Kd-tree

注意：我在这里的评论适用于高维空间。如果您使用2D或3D，我所说的内容可能不合适。（如果在高维空间中工作，请使用蛮力或近似于最近的邻居。）