笛卡尔树学习笔记

学习笔记 数据结构

目录

• 笛卡尔树学习笔记
  • 基础知识
    • 定义
    • 实现
    • 代码
  • 应用
    • 构造Treap
      • 练习题：[POJ 1785] Binary Search Heap Construction
    • 非旋转式Treap

基础知识

定义

• 笛卡尔树是一颗二叉树，每个节点有两个值，一个为维护的值$val$，另一个为分配的优先级$key$；
• 对于值$val$，笛卡尔树是一颗二叉搜索树，即中序遍历序列和维护的原序列相同；
• 对于值$key$，它又是一个堆（大小根堆视个人喜好而定）；
• 所以，笛卡尔树其实和Treap极为相似，但也有独特的优点，这在后文有介绍。

实现

严格说来，笛卡尔树不是一种平衡树，它没有后续的插入等操作，只有建树操作，因此建树后的功能操作通常用Treap实现，我们在此也只讨论建树的实现：
- 笛卡尔树的构造类似左偏树，只是它是“右偏的”；
- 我们先将节点按$val$值升序排列，这样按顺序每次只向树的右侧插入即可；
- 但我们还要维护该树的堆性质（这里小根堆会方便些），所以我们考虑用一个栈维护树最右边的一条链；
- 我们先令节点$0$入栈，即超级根，因为rand()函数值域非负，所以构造小根堆就不需考虑将超级根$0$的$key$赋为$INF$了

1. 对于一个节点$u$，我们从栈顶开始找，找到第一个$key$小于$key(u)$的节点$v$；
2. 令$v$的右子树成为$u$的左子树，$u$成为$v$的右儿子；
3. 这样栈中$v$之上的节点均不在树的最右边的链上了，所以都将其弹出，并让$u$入栈。
4. 最后，超级根$0$的右儿子就是真正的根。

以上操作贪心（每次找第一个满足$key$要求的节点$v$）的保证了笛卡尔树的两个性质。同时，每个节点只入栈出栈各1次，瓶颈只在排序，因此复杂度$O(n \log n)$。

代码

void build(int n,int val[],int key[]){
    static stack<int> stk;
    for(int i=1;i<=n;++i){
        d[i].val=val[i];
        d[i].key=key[i];
        d[i].sz=1;
    }
    sort(d+1,d+n+1);
    stk.push(0);
    for(int i=1,fa;i<=n;++i){
        while(fa=stk.top(),d[fa].key>d[i].key){
            upd(fa);
            stk.pop();
        }
        d[i].ls=d[fa].rs;
        d[fa].rs=i;
        stk.push(i);
    }
    while(stk.size()>1){
        upd(stk.top());
        stk.pop();
    }
    stk.pop();
    rt=d[0].rs;
}

应用

构造Treap

• Treap之所以平衡，就是因为每个节点的$key$是随机分配的；
• 于是建树就相当于按随机顺序插入这些节点，树高便是期望$O(\log n)$；
• 但当题目给定这个$key$时，便可以把Treap树高卡到$O(n)$，建树就成了$O(n^2)$；
• 这时笛卡尔树的优势就体现出来了，它的建树与分配的$key$无关，是稳定的$O(n \log n)$，所以这种情形就可以用它来建树了，后续操作再用Treap。

练习题：[POJ 1785] Binary Search Heap Construction

• 就是给定$val$和$key$，构造一颗Treap，然后中序遍历输出（显然正常建会被卡T）。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <utility>
#include <climits>
#include <cctype>
#include <iostream>
#include <stack>
#define val first
#define key second
using std::sort;
using std::pair;
using std::ostream;
using std::cout;
using std::stack;
template<const int MAXN>
class string{
    private:
        int sz;
        char c[MAXN];
    public:
        string(){};
        string(char chr,int cnt){
            for(int i=0;i<cnt;++i)
                c[i]=chr;
            sz=cnt;
        }
        string& operator+= (char chr){c[sz++]=chr;}
        friend bool operator< (const string &a,const string &b){
            return strcmp(a.c,b.c)<0;
        }
        friend ostream& operator<< (ostream &out,const string &a){
            printf("%s",a.c);
            return out;
        }
};
typedef pair<string<20>,int> data;
const int MAXN=50005;
data tmp[MAXN];
struct node{
    int ls,rs;
    data w;
    friend bool operator< (const node &a,const node &b){
        return a.w<b.w;
    }
};
class CartesianT{
    private:
        int rt;
        node d[MAXN];
        void inorder_prt(int u){
            putchar('(');
            if(d[u].ls) inorder_prt(d[u].ls);
            cout<<d[u].w.val;
            putchar('/');
            printf("%d",d[u].w.key);
            if(d[u].rs) inorder_prt(d[u].rs);
            putchar(')');
        }
    public:
        void clear(){memset(d,0,sizeof(d));}
        void build(int n,data a[]){
            static stack<int> stk;
            for(int i=1;i<=n;++i)
                d[i].w=a[i];
            sort(d+1,d+n+1);
            stk.push(0);
            d[0].w=data(string<20>(CHAR_MAX,20),INT_MAX);
            for(int i=1,fa;i<=n;++i){
                while(fa=stk.top(),d[fa].w.key<d[i].w.key)
                    stk.pop();
                d[i].ls=d[fa].rs;
                d[fa].rs=i;
                stk.push(i);
            }
            while(stk.size()) stk.pop();
            rt=d[0].rs;
        }
        void inorder_prt(){inorder_prt(rt);}
}T;
int main(){
    int n;
    char c;
    while(scanf("%d",&n),n){
        T.clear();
        memset(tmp,0,sizeof(tmp));
        for(int i=1;i<=n;++i){
            do{c=getchar();}while(!islower(c));
            while(islower(c)){
                tmp[i].val+=c;
                c=getchar();
            }
            scanf("%d",&tmp[i].key);
        }
        T.build(n,tmp);
        T.inorder_prt();
        putchar('\n');
    }
    return 0;
}

非旋转式Treap

其实也是用于建树，单独拿出来说是因为用于这种Treap建树是一般性的而不是只用于刚刚说的特殊情况。因为非旋转式Treap的ist()需要一次split()和两次merge()，常数略大，用笛卡尔树建树比较快。