Lib.rs

BallTree 是一种空间分割数据结构，允许以对数时间找到最近邻。

它通过将数据分割成一系列嵌套的边界球体（文献中的“球”）来实现。使用球体是因为计算点与球体之间的距离很简单（到球心距离减去半径）。关键观察结果是，潜在邻居必定比位于上述邻居之外的所有边界球体中的邻居更近。

图形表示

   A -  
   |  ----         distance(A, B) = 4
   |      - B      distance(A, S) = 6
    |       
     |
     |    S
       --------
     /        G \ 
    /   C        \
   |           D |
   |       F     |
    \ E         /
     \_________/

在图中，A 比 B 更接近，而因为 S 包含 C、D、E、F 和 G，因此可以确定 A 必定比其他点更接近 B，甚至不需要计算到它们的精确距离。

球树通常用作一种预测模型，其中点代表特征，每个点都与一个值或标签相关联。因此，此实现允许用户将值与每个点相关联。如果不需要此功能，可以使用 () 作为值。

此实现返回最近邻、它们的距离以及它们关联的值。返回距离允许用户对邻居进行某种加权插值，以便进行预测。