一维区域查找-wcn39xx_connectivity_software_programmers_guide

第 5 章 正交区域查找：数据库查询 5.1 一维区域查找 125 组点。这样，查询各数据域分别介于特定范围内的记录，就转化为“报告出落在某个与坐标轴平行 的d维（超）长方体内的所有点”的问题。在计算几何（computational geometry）中，这类查询被称 为矩形区域查询（rectangular range query），或者正交区域查找（orthogonal range query）。本章将 研究支持这类查找的数据结构。 5.1 一维区域查找 在着手处理二维或更高维矩形区域查找问题（range searching problem）之前，让我们首先来看 看一维的情形。给我们的输入数据是一维空间中⎯⎯即一条直线上⎯⎯的一个点集。需要查询的， 是该点集中落在某个一维矩形⎯⎯即某个区间[x : x']⎯⎯内的所有点。 设直线上给定的这一点集为 P := { p1, …, pn }。这个一维的区域查找问题可以有效的解决，为此 可以利用某种众所周知的数据结构⎯⎯平衡二分查找树 T。（当然，直接使用数组也可以圆满地解决 这一问题。然而，这种方法既不能推广到更高维的空间，也不能有效地支持对 P 的动态更新。）T 的叶子分别存储了 P 中的各点，而 T 的内部节点则记录了划分的数值，用来引导查找。将（内部） 节点 v 所对应的划分值记为 xv。我们假设：v 的左子树中存储了（坐标）不超过 xv的所有点，而其 右子树中则存储了（坐标）严格大于 xv 的所有点。 图5-3 在二分查找树上的一维区域查找 为了报告出落在待查询区域[x : x']内的所有点，可以如下进行。在T中分别查找x和x'，设两次查 找分别终止于叶子μ和μ'。于是，位于区间[x : x']之内的点，就对应于介于μ和μ'之间的那些叶子（可 能还要加上μ或μ'本身）。以如 图 5-3 所示的树为例，如果查询的区间是[18 : 77]，需要报告的就是 深灰色的那些叶子，再加上叶子μ自己。那么，如何才能找出介于μ与μ'之间的那些叶子呢？由 图 5-3 可以看出：在对应于μ和μ'的两条查找路径之间，存在一些子树；而需要找出的那些叶子，都分别来 自于其中的某棵子树。（在 图 5-3 中，这些子树已被标为深灰色，而分布于这两条查找路径上的各 个顶点都是淡灰色的。）更准确地讲，我们所选出的每一棵子树，都以介于这两条查找路径之间的 某个节点v为根，而且v的父亲节点位于某条查找路径之上。为了找到这类节点，首先要确定与x和x' 对应的两条查找路径开始分叉的位置，记这个节点为vsplit。这可以由下面的子程序来完成。分别将节