笛卡尔树cartesian tree

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

定义

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

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

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

a binary search tree is a rooted ordered binary tree, such that for its every node x the following condition is satisfied: each node in its left subtree has the key less then the key of x, and each node in its right subtree has the key greater then the key of x. 
That is, if we denote left subtree of the node x by L(x), its right subtree by R(x) and its key by kx then for each node x we have 

• if y ∈ L(x) then ky < kx 
  
• if z ∈ R(x) then kz > kx

• if y is the parent of x then ay < ax

【http://poj.org/problem?id=2201】

from:

http://blog.csdn.net/pipisorry/article/details/39033269

ref:

笛卡尔树 http://zh.wikipedia.org/zh-cn/%E7%AC%9B%E5%8D%A1%E5%B0%94%E6%A0%91