讲义

一、定义与性质

    笛卡尔树是一种特殊的二叉树数据结构，每个节点都由一对键值构成，即 (k, w)，其中 k 满足二叉搜索树的性质，而 w 满足堆的性质。具体来说：

    二叉搜索树性质：

        对于任意节点 x，其左子树中的所有键值 k 都小于 x的键值 k[x],右子树中的所有键值 k 都大于 x 的键值 k[x]。

    堆性质：

      对于任意节点 x，其左子树和右子树的权值 w都满足堆的性质，即左子树的权值 w小于等于父节点的权值 w，右子树的权值 w大于等于父节点的权值 w。

二：构建笛卡尔树

观察上图小根堆笛卡尔树，我们发现，一个节点的父亲就是左边第一个比它小的与右边第一个比它小的较大的那个。写个单调队列即可。

三：核心代码

详解

前置知识

二叉搜索树：
中序遍历是有序的
插入一个值，这个值比节点的值大，就插入右子树中
否则就插入左子树中

等于这个值怎么办？随便一端，右左都ok
O(logn)