Question

摘要

           | build      | build      | search     | orthogonal
           | time       | space      | (ins/del)  | range search
-----------+------------+------------+------------+--------------
KD-Tree    | O(NlogN)   | O(N)       | O(logN)    | O(N1-1/D + K)
Range Tree | O(NlogD-1N) | O(NlogD-1N) | O(logDN)   | O(logDN + K)

k 维树

大量储存多维平面上的点，并且依照地缘关係来排序。常缩写为 k-d tree、kd-tree。以下分别介绍一维和二维的情形。

一维 KD-Tree

1D-Tree 的原理与 Binary Search Tree 十分类似，但是长相却有点不同。在 1D-Tree 当中，资料全部集中在树叶；得补一些数据到内部节点，才能做搜寻。

一维 KD-Tree：建立

建立的方法，是把数线上的点分为左右两等份，然后分别递迴下去。习惯上是挑中位数位置的点作为分割点，分割点划分于左侧。

求分割点时，是使用时间为 O(N) 的求中位数演算法，而不是使用时间为 O(NlogN) 的排序演算法，才能达到理论上的时间複杂度。然而实际上排序演算法比较容易实作，效率也不错。

时间複杂度为 O(NlogN)，空间複杂度为 O(2N - 1) = O(N)。

一维 KD-Tree：插入、删除、搜寻

插入、删除、搜寻的方式跟 Binary Search Tree 的概念完全相同，时间複杂度都是 O(logN)。

一维 KD-Tree：大范围搜寻

有一个重要的应用，是找出一个区间裡面所有的点。概念上是以搜寻范围的左、右边界值，分别搜寻一次，途中顺便遍历符合搜寻范围内的子树。

真正在实作时，则是同时以搜寻范围的左、右边界值进行搜寻：甲、如果搜寻完全落在分割点的其中一侧，那麽就依照二元搜寻树的规则继续搜寻；乙、如果搜寻范围横跨分割点，那麽左右子树都要搜寻；丙、如果搜寻范围包含一整条分割区段，就可以直接遍历整棵子树，也可以当作是乙的情况来处理。

时间複杂度是 O(2*logN + 2*K-1) = O(logN + K)，K 为区间裡面的点数目。

延伸阅读：另外一种建立一维 KD-Tree 的方式

1D-Tree 另外有一种独特的建树方式：先排序所有资料，需时 O(NlogN)，然后再以 bottom-up 顺序建立 1D-Tree，需时 O(2N - 1) = O(N)。整体的时间複杂度仍相同。

读者可能会想：既然要先排序，那乾脆就把资料放到阵列，排序完之后，直接二分搜寻不就好了，干嘛需要 1D-Tree 呢？你想的没错，一维的情况下，资料又不会变动时，的确没有这个必要。

延伸阅读：内部节点有两种记录方式

内部节点有两种记录方式。基本的方式是记录分割点座标，这是仿照 Binary Search Tree 的原理；进阶的方式是记录其下所有树叶的数值范围，实作起来会複杂一点。这两种记录方式也可以同时使用。

採用进阶的方式有一个好处：可以允许树叶当中有许多相同座标的点。如此一来，座标相同的点就能进行左右两等份，闪避了分割点的二元搜寻规则。

一般来说，KD-Tree 没有必要使用进阶的方式。在 Range Tree 当中，才有必要用到进阶的方式。

二维 KD-Tree

两个维度依序作为等分的依据，轮流递迴下去。

二维 KD-Tree：建立

先以垂直线，把平面上的点分为左右两等份，左右两区域各自再以水平线，将平面上的点等分为上下两等份。垂直、水平如此不断轮流递迴下去，直到每个区域都只剩一个点。

时间複杂度为 O(NlogN)。空间複杂度为 O(2N - 1) = O(N)。

二维 KD-Tree：插入、删除、搜寻

插入、删除、搜寻的方式跟 Binary Search Tree 的概念完全相同，时间複杂度都是 O(logN)。

二维 KD-Tree：大范围搜寻

有一个重要的应用，是找出一个长方形范围裡面所有的点：甲、如果搜寻范围完全落在分割线的其中一侧，那麽就依照二元搜寻树的规则继续搜寻；乙、如果搜寻范围横跨分割线，那麽左右子树都要搜寻；丙、如果搜寻范围包含一整块分割区域，就可以直接遍历整棵子树，也可以当作是乙的情况来处理。

搜寻时，垂直方向最多遇到 O(sqrtN) 个区域，水平方向最多遇到 O(sqrtN) 个区域，因此搜寻的时间複杂度是 O(2*sqrtN + 2K-1) = O(sqrtN + K)，K 为长方形裡面的点数目。

高维 KD-Tree

建立时间为 O(NlogN)，建立空间为 O(N)，插入、删除、搜寻的时间为 O(logN)，搜寻 D 体形范围的时间为 O(N^1-1/D + K)。

Timus 1369 ICPC 6041

大量 Point 资料结构: Range Tree

范围树

大量储存多维平面上的点，并且依照地缘关係来排序，用途和“k 维树”一模一样。

“范围树”的基本操作都比“k 维树”略逊一筹，但是“范围树”做大范围搜寻时，竟神奇地比“k 维树”快上许多。以下分别介绍一维和二维的情形。

一维 Range Tree

就是一维 KD-Tree。

二维 Range Tree

一棵 X 座标为主的 1D-Tree，每一个内部节点都连繫到一棵 Y 座标为主的 1D-Tree，由内部节点所管辖的点所构成。

X 树可能有 X 座标相同、Y 座标不同的点；Y 树可能有 Y 座标相同、X 座标不同的点。因此，内部节点改为记录其下所有树叶的数值范围，如此一来，座标相同的点就能进行左右两等份。

二维 Range Tree：建立

甲、首先建立 X 树；乙、于回溯时，使用 Merge Sort 将子树的点重新依照 Y 座标排序；丙、同时，拿排序好的点，以 bottom-up 方式，建立 Y 树。

X 树的高度是 O(logN)，树根到树叶的路径长度是 O(logN)。对于 X 树的其中一个树叶，只可能出现在 O(logN) 棵 Y 树当中。如此便算出空间複杂度为 O(NlogN)。

时间複杂度为 O(NlogN)，空间複杂度为 O(NlogN)。

二维 Range Tree：插入、删除、搜寻

先以 X 座标搜寻 X 树，沿途每一个内部节点，再以 Y 座标深入搜寻 Y 树。

时间複杂度是 O((logN)^2)。

二维 Range Tree：大范围搜寻

有一个重要的应用，是找出一个长方形范围裡面所有的点。以长方形的左、右边界值，分别搜寻 X 树，找出在左、右边界范围内的所有子树及树叶，再以上、下边界值，深入搜寻 Y 树。

概念上可以解读成：先过滤 X 座标，再过滤 Y 座标。

时间複杂度是 O((logN)^2 + K)，K 为长方形裡面的点数目。终于比 KD-Tree 快！

高维 Range Tree

建立时间为 O(Nlog^D-1N)，建立空间为 O(Nlog^D-1N)，插入、删除、搜寻的时间为 O(log^DN)，搜寻 D 体形范围的时间为 O(log^DN + K)。

延伸阅读：Fractional Cascading

当资料不会变动时，可以把最深维度的 1D-Tree 改为阵列，就可以利用 Fractional Cascading 减少搜寻的时间，搜寻的时间可以除掉一个 logN。

搜寻的时间变为 O(log^D-1N)，搜寻 D 体形范围的时间变为 O(log^D-1N + K)。

ICPC 6045

大量 Interval 资料结构: Interval Tree

区间树

置放大量区间，并且进行排序的资料结构。

排序 2N 个区间端点，以中位数位置的端点做为分界线。树根是横跨两侧的区间，依照左端点排序；左子树是位于左侧的区间；右子树是位于右侧的区间。

空间 O(N)，建立 O(NlogN)，搜寻 O(logN + K)。

另一种区间树

平衡的 Binary Search Tree，以区间左端点作为键值。每个节点额外记录其子树所有区间的右边界。

空间 O(N)，建立 O(NlogN)，搜寻 O(logN + K)。

大量 Interval 资料结构: Segment Tree

线段树

置放大量区间，并且进行排序的资料结构。

排序 2N 个区间端点，将数线切成最多 2N-1 个区段，一个区段对应一个树叶。

top-down 观点：标记区间涵盖的子树，只标记子树树根。

bottom-up 观点：标记区间涵盖的树叶，往上合併标记。

储存一个区间，每一层最多标记两个节点，整棵树最多标记 2logN 个节点。储存 N 个区间的空间複杂度为 O(NlogN)。

空间 O(NlogN)，建立 O(NlogN)，搜寻 O(logN + K)。

UVa 10535 ICPC 4108

大量 Shape 资料结构: Binary Space Partitioning Tree

Binary Space Partitioning Tree

http://en.wikipedia.org/wiki/Binary_space_partitioning

大量储存多维空间裡的图形，并且依照地缘关係来排序。常缩写为 BSP tree。

概念仿照 KD-Tree。任取一笔资料，做为分界处，将空间划分成左右两区，将剩馀资料分为左右两堆，递迴分割下去。横跨分界处的资料，必须切开，成为左右两份。

三维空间，资料是三角形：随便抓一个三角形，做为分界面，将空间划分成左右两区，并将其馀三角形们划分成左右两堆，递迴分割下去。

二维平面，资料是线段：仿前。

二维平面、三维空间，资料是点：即是 KD-Tree。

UVa 1542 ICPC 2105