驱动因素

二叉查找树仍然是一个高效的查找结构,它也能够在节点插入和删除时做出平衡调整。但不幸的是,kd树的平衡调整就不这么容易了,因为有些深层次的结构信息和所表示的平面区域相关。最理想的解决方案是构建一棵kd树,使得a叶子节点都是在同一层,或者b所有的叶子节点在其他叶子节点一级。例9-4使用递归来迭代维度的每个坐标。它从点集中选择中位元素,然后将在这个元素“下方”的元素插入左子树,“上方”的元素插入右子树。这段代码适用于任何维度。

例9-4:递归构建kd树

阅读 ‧ 电子书库

选择操作在第4章的“快速排序”一节中已经描述过了。能够在平均情况下在O(n)时间内选择第k小的元素,但是,在最坏情况下会退化到O(n2)的性能。为了避免这种情况,我们使用BFPRT选择算法,在第4章中我们讨论过这个算法,这个算法能够保证,虽然在平均情况下性能不如标准选择算法,在最坏情况下的性能仍然为O(n)。

广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元