四叉树[51]（quadtree）是2d-树的简化形式，其简化策略包括：
直接沿区域的（水平或垂直）平分线切分，从而省略了中位点的计算沿垂直方向切出的每一对节点（各自再沿水平方向切分）都经合并后归入其父节点被合并的节点即便原先（因所含输入点与足两个）而未继续切分，在此也需要强行（沿水平方向）切分一次
a） 与 kd-树与同，四叉树可能包含大量的空（即与含任何输入点的）节点。更糟糕的是，此类节点的数目无法仅由输入规模 n 界定。对二任意的 N > 0，试构造一个仅含 n = 3 个点的输入点集，使得在其对应的四叉树中，空节点的数目超过 N 个。
b） 对于任一输入点集 P，若将其中所有点对的最长、最小距离分别记作 D 和 d，则l = D/d 称作 P 的散布度（spread）。试证明，P 所对应的四叉树高度为
(log
)。
c） 按照以上描述，试用 C/C++语言实现四叉树结构
d） 试基于四叉树结构设计相应的范围查询算法，并利用你的四叉树结构实现该算法。
