引入

首先我们看到这个序列 \([9,4,10,1,7,2,3]\)，现在我们找到它的最大值 \(10\)，并从中间劈开，此时分为了两个序列 \([9,4]\) 和 \([1,7,2,3]\)，接着对这两个序列继续这样的操作。

现在，将劈开后序列最大值和被劈开的数建立父子关系，于是便建立了这个树：

这也就是笛卡尔树。笛卡尔树满足堆，二叉搜索树的性质。

但是怎么建出这个树呢？

我们先看一下把这些结点连向其左右第一个比它大的结点的效果：

可以发现它的父亲刚好是其中较小的一个。证明也很简单，首先其父亲不可能小于它，其次，父亲一定是左右两边第一个比它大的数，如果不是那样，就只有可能是先选择离自己更远的数，再选择自己，但是还有比自己更大的数，矛盾。最后，父亲一定是较小的那个，因为较大的那个肯定更先选择，所以较小的才是父亲。