笛卡尔树

2022/1/19 23:52:12

本文主要是介绍笛卡尔树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

笛卡尔树

定义:笛卡尔树是一种二叉树,每一个结点由一个键值二元组 \((k,w)\) 构成。要求 \(k\) 满足二叉搜索树的性质,而 \(w\) 满足堆的性质。一个有趣的事实是,如果笛卡尔树的 \((k,w)\) 键值确定、并且 \(k\) 不相同, \(w\) 不相同,那么这个笛卡尔树的结构是唯一的。


建树方法:

给定一个序列A,下面建树的过程中以小根堆为例,定义序列中第 \(i\) 个元素的键值为 \((i,A_i)\) ,也就是 \(i\) 对应 \(k\) ,\(A_i\) 对应 \(w\) ,我们要求 \(k\) 满足二叉搜索树的性质,那么此时我们进行思考,我们每插入一个新的点,由于 \(k\) 必然是递增关系,所以这个新点的 \(k\) 比上一个点大,这个时候我们能确定,这两个点的关系必然是 \(k-1\) 点是 \(k\) 点的左儿子或者 \(k\) 点是 \(k-1\) 点的右儿子,直接和上一次的点比较 \(w\) 即可,如果后来的 \(w\) 大,就直接成为前一个的右儿子,同时也和下面的右儿子比较一下,看看符不符合这个关系,不然的话,成为前一个的父亲,同时与上方的父亲进行比较,继续判断是否交换

我们发现,上述操作维护的都是原节点的右链,所以我们可以选择直接处理

实现方法:每个数只会进出右链一次,这个过程我们用栈维护,如果一个数不在右栈上的话就弹出,栈中维护当前笛卡尔树的右链上的结点,复杂度 \(O(n)\)


rep(i, 1, n){
    int k = top;
    while (k && h[stk[k]] > h[i]) k--;
    if (k) rs[stk[k]] = i;  // rs代表笛卡尔树每个节点的右儿子
    if (k < top) ls[i] = stk[k+1];  // ls代表笛卡尔树每个节点的左儿子
    stk[++k] = i;
    top = k;
}
新建一个大小为 n 的空栈。用 top 来标操作前的栈顶,k 来标记当前栈顶。
For i := 1 to n
    k := top
    While 栈非空 且 栈顶元素 > 当前元素 
        k--
    if 栈非空
        栈顶元素.右儿子 := 当前元素
    if k < top
        当前元素.左儿子 := 栈顶元素
    当前元素入栈
    top := k


这篇关于笛卡尔树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程