In不会太担心这个问题，这有点像哈希Map，如果所有条目都必须使用相同的哈希码，那么理论上最坏的情况是**O（n）**查找，但实际上这不太可能发生，除非哈希函数有问题。
为了避免不平衡，你应该确保你的点数没有以任何方式排列。如果它们是，考虑在插入它们之前打乱它们。
另外，一些kd-tree实现有一个rebalance()函数，可以在插入（大量）数据后调用，这将在内部重新平衡树。
最后，如果你真的想使用一个特定的插入顺序来避免不平衡，你可以做以下的事情。注意，这个方法不是最优的，它可以避免最坏的情况，但通常不会产生一个完全平衡的树：按x坐标对点排序，然后使用二进制拆分搜索将其插入。例如，如果有15个点，则按'x'对它们排序以获得点p0...p14的排序列表。然后：
1.取范围（p7）的中点并插入。
1.为拆分点的每一侧创建一个新范围：p0-p6和p8-p15
1.从1）两个范围中的每一个开始
这将产生以下插入顺序：
1.圆形：p7
1.轮次：p3和p11
1.轮次：p1、p5、p9、p13
1.四舍五入：p0、p2、p4、p6、p8、p10、p12、p14
为什么这不理想？

• 我们完全忽略了y坐标，这种方法只能避免x坐标的不平衡。
• 典型的kd树在x和y之间交替分裂。然而，我们不知道在给定的实现中哪个先出现，所以我们只能假设它总是在x上分裂。这没有立即的伤害，但它阻止了更优化的插入。