笛卡尔树

笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、范围top k查询（range top k queries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。笛卡尔树结构由Vuillmin(1980)^[1]在解决范围搜索的几何数据结构问题时提出。从数列中构造一棵笛卡尔树可以线性时间完成，需要采用基于栈的算法来找到在该数列中的所有最近小数。

某個數組，及其對應的笛卡爾樹

定义

无相同元素的数列构造出的笛卡尔树具有下列性质：

1. 结点一一对应于数列元素。即数列中的每个元素都对应于树中某个唯一结点，树结点也对应于数列中的某个唯一元素
2. 中序遍历（in-order traverse）笛卡尔树即可得到原数列。即任意树结点的左子树结点所对应的数列元素下标比该结点所对应元素的下标小，右子树结点所对应数列元素下标比该结点所对应元素下标大。
3. 树结构存在堆序性质，即任意树结点所对应数值大／小于其左、右子树内任意结点对应数值

根据堆序性质，笛卡尔树根结点为数列中的最大／小值，树本身也可以通过这一性质递归地定义：根结点为序列的最大／小值，左、右子树则对应于左右两个子序列，其结点同样为两个子序列的最大/小值。因此，上述三条性质唯一地定义了笛卡尔树。若数列中存在重复值，则可用其它排序原则为数列中相同元素排定序列，例如以下标较小的数为较小，便能为含重复值的数列构造笛卡尔树。

笛卡尔树应用

范围最值查询与最低公共祖先

 

三边范围查询问题

笛卡尔树可以有效地处理范围最值查询（range minimum queries），通过将定义在数列上的RMQ问题转化为定义在树结构上的最低公共祖先（lowest common ancestor）问题。数列以线性时间构造出笛卡尔树，笛卡尔树则能以常数时间处理最低公共祖先查询，因此在线性时间的预处理后，范围最值查询能以常数时间完成。

Bender & Farach-Colton (2000)^[2]则提出了RMQ与LCA问题的新联系，他们通过不基于树的算法处理RMQ问题从而有效地解决LCA问题。其使用欧拉路径的技巧将树结构转化为数列，此数列具有特定性质（相邻数值代表树中的相邻顶点，即在树中高度差为1的顶点），利用这一性质RMQ问题可以很高效地得到解决。通常的数列则不具备此性质，为了将一般的数列转化为具有上述性质的数列，需要应用到笛卡尔树，具体过程为在普通数列上构造笛卡尔树，在笛卡尔树上使用欧拉路径转化的方法将树转化为具有上述性质的新数列。

范围最值查询问题也可以解释为二维范围查询问题，或者三边范围查询问题（three sided range queries），笛卡尔平面上的有限点集可以用来构造笛卡尔树，首先将这些点按照x取值排序，然后将y值作为数列中元素的值，以此数列建立笛卡尔树。若 S 为有限点集中满足 ${\displaystyle L\leq x\leq R}$ 条件的点集，设 p 是 S 中x值最小的点，q 是 S 中 x 值最大的点，则笛卡尔树中 p 与 q的最低公共祖先即为该点集中处于该x值范围内y值最高／低的点 b。三边范围查询问题，即给定条件 ${\displaystyle L\leq x\leq R,y\leq T}$ ，取出所有满足条件的点。其解决是以笛卡尔树找到b 点，若b点的y 值满足条件，则递归地在 p, b 所约束的子树以及b, q 所约束的子树内重复这一过程，这一查询可以使每个被报告的点都在常数时间内找到，总体的时间复杂度为 ${\displaystyle O(k)}$ ，k即为满足条件的点数。

笛卡尔树同样可以应用于以常数时间查询超度量空间内点对的距离。超度量空间内距离的定义与最宽路径问题中的权重相同。从最小生成树上可以构造一个笛卡尔树，根结点表示最小生成树中的权值最大的边，撤去此边会将最小生成树分割为两个子树，笛卡尔树递归地从这两棵子树上构造。笛卡尔树的叶结点表示度量空间内的点，两个叶结点的最低公共祖先则是这两个点在最小生成树中最重的边，代表这两点间的距离。获得了最小生成树及将边按照权值排序后，笛卡尔树即可在线性时间内构造出来。

Treap

笛卡尔树是二叉树，对于数列而言将其作为二叉搜索树是自然的。若将二叉搜索树结点关联上一个权值，并且保证此权值在树结构中遵循堆中的序关系，即父结点权值比子结点权值大，则此二叉搜索树又被称为Treap. 其名称来源于树与堆两英文词的组合（tree ＋ heap -> treap）。Treap与笛卡尔树在结构上是相同的，只是两者的应用不同。

参考文献

1. Vuillmin 1980. "A unifying look at data structures", Commun. ACM (New York, NY, USA: ACM) 23 (4): 229–239, doi:10.1145/358841.358852
2. Bender, Michael A.; Farach-Colton, Martin (2000), "The LCA problem revisited", Proceedings of the 4th Latin American Symposium on Theoretical Informatics, Springer-Verlag, Lecture Notes in Computer Science 1776, pp. 88–94.