区域树（Range Tree）的构建（Build）与查询（Query）

àì夳堔傛蜴生んèń 2022-12-28 07:20 70阅读 0赞

# 一、什么是区域树（Range Tree） #

首先以2D Range Tree为例，在一个二维平面上有很多点，点都有x和y坐标，现在要查询在区域 \[x1,x2\] × \[y1,y2\] 范围内的所有点，常用的方法一般是先将数据点预处理成一棵树，然后通过对数中点集的查找来实现。其中区域树就是一种正交查找的常用方法，**主要思路是将点沿X坐标建立一棵树，再将每个节点的子树按照Y坐标再建立一棵树**，具体实现与查找见下文。

# 二、区域树构建（Build） #

首先对于平面中的四个点，可以根据X坐标建立X-tree，如下所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70][]

接下来要将每一个节点对应的子树再建立一个Y-tree，比如对于根节点，他的子树中点有4个，那么Y-tree为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 1][]

X-tree根节点的两个子节点对应的子树都有两个点，于是对应的Y-tree为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 2][]

于是一个区域树就被构建好了：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 3][]

上边只是构建的大致思路，但是具体流程的伪代码应该怎么写呢？建立一棵树多采用递归的思路，如果点集只有一个，那么该点对应X-tree与Y-tree直接就是自身；如果点集中点不止一个，那么就用中位数将他们分为两部分，当前节点t的值为中位数，将两部分分别构建成当前节点t的两课子树，即t.left和t.right，此时已经完成了X-tree的构建，然后将两棵子树的点按Y坐标归并成一棵Y-tree，这样在一次递归过程中，以nlogn的时间开销和nlogn的空间开销完成了区域树构建。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 4][]

# 三、区域树查找（Query） #

区域树的查找是先查找X坐标，当点X坐标处于 \[x1,x2\] 之间时，再查找Y坐标是否在范围 \[y1,y2\] 内，如果是的话就将点输出。具体的查找过程是：从根节点入手，查看当前节点子树的X坐标是否在范围内，如果在的话，那就不需要再继续向下查找X-Tree了，可以直接查询Y坐标了；如果当前节点是一个叶子，那么只需要验证一下是否处于 \[x1,x2\] × \[y1,y2\]即可；若当前节点子树与查询范围有交叉，那么需要继续向下细分X-tree进行查询，重复上述过程直到查询完毕。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 5][]

**看明白的话记得点个赞哦~** 里边用图参考于：[https://www.cse.wustl.edu/~taoju/cse546/lectures/Lecture21\_rangequery\_2d.pdf][https_www.cse.wustl.edu_taoju_cse546_lectures_Lecture21_rangequery_2d.pdf]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70]: /images/20221120/358ba1e0f2fb4a0abe251a624d5119e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201215140109363.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201215140234614.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201215140311723.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201215140455596.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201215141004773.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1,size_16,color_FFFFFF,t_70
[https_www.cse.wustl.edu_taoju_cse546_lectures_Lecture21_rangequery_2d.pdf]: https://www.cse.wustl.edu/~taoju/cse546/lectures/Lecture21_rangequery_2d.pdf