二叉查找树仍然是一个高效的查找结构，它也能够在节点插入和删除时做出平衡调整。但不幸的是，kd树的平衡调整就不这么容易了，因为有些深层次的结构信息和所表示的平面区域相关。最理想的解决方案是构建一棵kd树，使得a叶子节点都是在同一层，或者b所有的叶子节点在其他叶子节点一级。例9-4使用递归来迭代维度的每个坐标。它从点集中选择中位元素，然后将在这个元素“下方”的元素插入左子树，“上方”的元素插入右子树。这段代码适用于任何维度。
例9-4：递归构建kd树
选择操作在第4章的“快速排序”一节中已经描述过了。能够在平均情况下在O(n)时间内选择第k小的元素，但是，在最坏情况下会退化到O(n2)的性能。为了避免这种情况，我们使用BFPRT选择算法，在第4章中我们讨论过这个算法，这个算法能够保证，虽然在平均情况下性能不如标准选择算法，在最坏情况下的性能仍然为O(n)。