笛卡尔树(Cartesian Tree)

定义

笛卡尔树(Cartesian Tree)是针对一个序列构建的二叉树:中序遍历恰好还原原序列(下标满足 BST 性质),而节点键值满足堆性质(如小根堆)。该结构由 Vuillemin 于 1980 年提出。

构造

利用单调栈可以 O(n) 构建:从左到右处理元素,维护树的右链,把栈中大于当前元素的节点弹出并挂为当前节点的左子树,当前节点接到栈顶节点的右孩子位置。

应用

笛卡尔树是 RMQ 与 LCA 互相归约的桥梁:序列区间最小值恰为对应两节点在笛卡尔树上的最近公共祖先,基于此可实现 O(n) 预处理、O(1) 查询的 RMQ;Treap 本质是随机优先级的笛卡尔树;它还用于 Range Top-k 查询和某些排序算法的分析。

优缺点

优点是构建线性、性质优美、与多种经典问题互通;缺点是形态完全由数据决定,可能严重不平衡,直接作为动态查找树使用并不合适。