Yuics Blog

笛卡尔树学习笔记

二叉搜索树和堆的定义

想要引入笛卡尔树,首先需要了解二叉搜索树和堆各自的定义。

二叉搜索树的定义

二叉搜索树是一种二叉树的树形数据结构。

  1. 空树是二叉搜索树。
  2. 若二叉搜索树的左子树不为空,那么其左子树上所有的点的附加权值均 小于 其根节点的值。
  3. 若二叉搜索树的右子树不为空,那么其右子树上所有的点的附加权值均 大于 其根节点的值。
  4. 二叉搜索树的左右子树均为二叉搜索树。

二叉搜索树上的基本操作所花费时间与这棵树的高度成正比。

堆的定义

堆是一棵树,每个节点都有一个自己的 $value$,且每个节点的 $value$ 都 大于等于或小于等于 其父亲的 $value$。

笛卡尔树的定义和构建

笛卡尔树是一种二叉树,每个节点由二元组 $(k, w)$ 构成。要求 $k$ 满足二叉搜索树的性质且 $w$ 满足堆的性质。

注意到如果笛卡尔树的 $(k, w)$ 键值确定,且 $k$ 互不相同,$w$ 互不相同,那么其结构是唯一的。

tree

对于笛卡尔树的构建可以移步 OI Wiki,图片清晰,讲解透彻。

注意:对于任意一个笛卡尔树,对其进行中序遍历就可以得到原序列。

考虑使用栈来维护建立笛卡尔树的过程,复杂度显然 $O(n)$。

例题

#oi #数据结构