今天有人问我一个问题，要从一组坐标而不是一组数字构建 BST。所以输入将是未排序的坐标
[(1,2), (5,7), (0,5)]或其他形式：
x = [1,5,0] y =[2,7,5]选择树上的点的启发式方法是使用具有最大范围的轴（中值切割算法）。有人可以解释为什么这种启发式是最好的吗？我们试图在每个步骤上切掉尽可能多的点，因此我们可以让 y 轴的范围非常小，但有很多具有该范围的点，而 x 轴的范围很宽，我只是不明白为什么会这样正在产生最好的结果...如果有人可以非常简单地解释这一点，我将不胜感激。
除了轴选择过程之外，您的树是一个 K-D 树。
选择范围最大的轴客观上并不是“最佳”启发式，但它是一个很好的启发式。 在这种树中，每个节点都有一个对应的矩形空间区域。例如，当您搜索特定半径内的所有点时，您必须访问具有与目标盘重叠的区域的每个节点。
最大范围启发式尝试使每个节点的矩形区域尽可能正方形。这可以防止具有“远”点的节点与目标盘重叠，因此您不必搜索它们。另一方面，长而细的矩形会重叠许多远离其大部分点的搜索区域。
当节点矩形区域的长宽比与搜索区域的长宽比相同时，这是最佳的。