有关笛卡尔树的定义与实际解题中的常用性质
有关笛卡尔树的定义与实际解题中的常用性质
二叉搜索树和堆的定义
想要引入笛卡尔树，首先需要了解二叉搜索树和堆各自的定义。
二叉搜索树的定义
二叉搜索树是一种二叉树的树形数据结构。
- 空树是二叉搜索树。
- 若二叉搜索树的左子树不为空，那么其左子树上所有的点的附加权值均 小于 其根节点的值。
- 若二叉搜索树的右子树不为空，那么其右子树上所有的点的附加权值均 大于 其根节点的值。
- 二叉搜索树的左右子树均为二叉搜索树。
二叉搜索树上的基本操作所花费时间与这棵树的高度成正比。
堆的定义
堆是一棵树，每个节点都有一个自己的 $value$，且每个节点的 $value$ 都 大于等于或小于等于 其父亲的 $value$。
笛卡尔树的定义和构建
笛卡尔树是一种二叉树，每个节点由二元组 $(k, w)$ 构成。要求 $k$ 满足二叉搜索树的性质且 $w$ 满足堆的性质。
注意到如果笛卡尔树的 $(k, w)$ 键值确定，且 $k$ 互不相同，$w$ 互不相同，那么其结构是唯一的。
对于笛卡尔树的构建可以移步 OI Wiki，图片清晰，讲解透彻。
注意：对于任意一个笛卡尔树，对其进行中序遍历就可以得到原序列。
考虑使用栈来维护建立笛卡尔树的过程，复杂度显然 $O(n)$。
- 每个右子树根节点的父亲节点就是它左边第一个大于他的数的位置。
- 每个节点的左子树根节点就是它左边小于该值的数中的最大值的最小下标