\(16.1\)四叉树

1.问题的引入

  考虑这样的问题：给定下面一系列点，求落入矩形区域的点的数量。

  我们希望不用遍历所有的点，一个自然的想法是利用\(BST\)的性质进行搜索。在对一系列的点坐标\((x,y)\)构建\(BST\)时。对于单个的\(x\)坐标或\(y\)坐标，我们可以很容易地构建出对应的\(BST\)。但对于二维的坐标，当一个点的\(x\)坐标大于另一个点、而\(y\)坐标小于另一个点时，我们该怎么排序呢？

2.四叉树

  该问题的解决办法为：让我们的树从四个方向同时(\(simultaneously\))分割空间，实现这一操作的结构称作四叉树。

  \(a.\)四叉树的构建

  四叉树具有四个指针，每个指针分别指向东南、东北、西南、西北区域。假如我们以\(A\)为根节点，则初始的四叉树如下：

  对应的二维空间如下：

  接下来，我们插入\(B(2,2)\)这个节点。由于\(B\)在\(A\)的东北方向，\(A\)的\(NE\)指针指向\(B\)：

  此时对应的二维空间如下：

  我们以同样地方式插入\(C\)、\(D\)、\(E\)，可得到以下的四叉树和二维空间：

  \(b.\)四叉树的搜索

  回到开篇的问题，我们用我们构建的四叉树来搜索符合条件的节点。

1. 从根节点\(A\)开始搜索。\(A\)不属于矩形区域，故返回\(null\)。
2. 然后，我们考虑：\(A\)的哪个子空间(\(subspace\))可能会有符合条件的点？由于矩形区域在\(A\)的东北方向，因此我们只需搜索\(A\)的\(NE\)子树：

3. 接着我们搜索\(B\)节点，\(B\)在矩形区域内，所以返回它的坐标。
4. 接着我们考虑：\(B\)的哪个子空间可能会有符合条件的点？可以看到\(B\)的四个方向都符合条件。
5. ......

  可以看到，四叉树具有良好的剪枝(\(pruning\))效果，这提高了我们的搜索效率，我们可以利用递归进行我们的搜索流程。