第 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。这可以由下面的子程序来完成。分别将节
2022-05-19 15:41:49
4.56MB
计算机和
1