Question

楔子

请你尝试发掘，这一系列的资料结构是为了解决什麽问题呢？

Uniform Grid

嗯，就是方格纸。将整个世界划分为等宽方格。

实作方式是一个二维阵列，对应方格纸。阵列每一格是一个串列，对应每个方格包含的资料。

资料可以是任何东西，例如点、线段、三角形。

如果资料跨据多个格子，那麽可以同时储存于多个格子，或者只储存于其中一个格子。随你开心。

插入、删除、搜寻的时间複杂度是 O(N)，N 为资料数量；然而，串列长度通常远少于 N，因此这种时间複杂度标记法缺乏意义。

Region 资料结构: Quadtree

Bitree / Quadtree / Octree / Hextree

二元树、四元树、八元树、十六元树，分别是一、二、三、四维的版本。

以四元树为例：分割平面为四等分，视情况可以递迴分割下去，越分越细。

资料放在树叶。资料可以是任何东西，例如点、线段、三角形。

插入、删除、搜寻的时间複杂度是 O(N)，N 为资料数量；然而，树的高度通常远少于 N，因此这种时间複杂度标记法缺乏意义。确切的时间複杂度难以估计，取决于树深与分枝数。

UVa 297 806 11941 11948

Region 资料结构: k-Dimensional Tree

k-Dimensional Tree

额外绘制垂直线、水平线来分割区域。由于概念类似 KD-Tree，所以大家没有另起他名，直接沿用旧名。

此处的 KD-Tree，注重每笔资料的边界范围；原本的 KD-Tree，注重每个座标点的位置先后顺序。两者用途不一样。

採 top-down 方式，依照某一个座标轴排序所有资料（通常是跨距最广的那个座标轴），将资料等分为左右两堆，递迴分割下去。

插入、删除、搜寻的时间複杂度是 O(N)，N 为资料数量；然而，树的高度通常远少于 N，因此这种时间複杂度标记法缺乏意义。

缺点是：资料跨区时，不知该安置于哪区。除非资料是点。

Region 资料结构: Bounding Volume Hierarchy

Bounding Interval Hierarchy / Bounding Region Hierarchy / Bounding Volume Hierarchy

BIH、BRH、BVH 分别是一、二、三维的版本。

採 top-down 方式，依照某一个座标轴排序所有资料（通常是跨距最广的那个座标轴），将资料等分为左右两堆，递迴分割下去。

插入、删除、搜寻的时间複杂度是 O(N)，N 为资料数量；然而，树的高度通常远少于 N，因此这种时间複杂度标记法缺乏意义。

优点是：不必烦恼该安置于哪区。可以旋转节点，令树平衡。

UVa 12312 ICPC 7605

Region 资料结构: R-Tree

R-Tree

Bounding Volume Hierarchy 与 B-Tree 合体。