有旋树堆-TREAP

HYLW · 2024-04-17 21:15:51 · 科技·工程

上集回顾-REVIEW

《二叉搜索树（BST）》:

特异性进化-EVOLUTION FOR SPECIFICTY

显然，满足 \texttt{BST} 性质且中序遍历相同的二叉查找树不唯一，如此，有可能树的深度达到 O(\frac{1}{2}n) ，从而被卡成 O(n^2) 的时间复杂度，所以，我们想要把中序遍历相>同的二叉树确定下来，确定成深度维持在 O(\log n) 的级别。

于是，下一代数据结构登场——堆树-TREAP。

一、\texttt{BST} 形态转换：旋转-THE RETATION OF \texttt{BST}

改变形态并维持 \texttt{BST} 性质的方法为“旋转”。分为左旋与右旋：

以右旋为例，在初始情况下，x 是 y 的左子节点，A 和 B 分别是 x 的左右子树，C 是 y 的右子树。

“右旋”操作在保持 \texttt{BST} 性质的基础上，把 x 变为 y 的父节点，因为 x 的关键码小于 y 的关键码，所以 y 应该作为 x 的右子节点。

当 x 变成 y 的父节点后，y 的左子树就空出来了，于是 x 原来的右子树 B 就恰好作为 y 的左子树。

其代码如下（定义按《二叉搜索树（BST）》中的例题代码）：

void zig(int &p){//把 p 的左子节点与 p 合法换位 
    int q=a[p].l;
    a[p].l=a[q].r;// 子节点的右子树成为 p 的左子树 
    a[q].r=p;//p 成为子节点的右子树 
    p=q;//p 是引用 
}

对应的，左旋为：

void zag(int &p){//把 p 的右子节点与 p 合法换位 
    int q=a[p].r;
    a[p].r=a[q].l;// 子节点的左子树成为 p 的右子树 
    a[q].l=p;//p 成为子节点的左子树 
    p=q;//p 是引用 
}

简记：左旋拎右左挂右，右旋拎左右挂左——AgOH

而这样的旋转操作可以使 \texttt{BST} 趋于平衡（左右子节点分布均匀）而不至于深度过大，问题在于，如何旋转？

然而，随机化便是答案。

二、树堆-TREAP

发现，再随机数据下，普通的 \texttt{BST} 是趋近于平衡的，\texttt{Treap} 的思想就是利用“随机”来创造平衡条件。

我们的想法是把“随机”作用在堆性质上，这也是为什么要叫树堆。具体地讲，每个节点新添一个变量作为随机域或重要性指数，同时要求该数据结构满足 \texttt{BST} 性质与堆性质。此时，其二叉搜索树的形式唯一且深度较小。

为什么深度较小？假设随机生成值与 \texttt{BST} 中的权值对应，因为在随机下以随机生成值插入 \texttt{heap} 后其结构期望为平衡的，在给原 \texttt{BST} 旋转一下，能够找到对应结构，因而平衡。

三、例题实操-PRACTICE FOR AN EXAMPLE

然而，用例题来实操一下：P3369 【模板】普通平衡树。

我们可以发现，有一些与 \texttt{BST} 类似的地方，所以就不再解释了，看《二叉搜索树（BST）》回顾。

然后，回顾堆的性质：《堆-HEAP》。这里使用大根堆。

initialization of the treap

三大基操（基本操作）：

void pushup(int p){
    tr[p].siz=tr[tr[p].l].siz+tr[tr[p].r].siz+tr[p].cnt;
}

void zig(int &p){//右旋 
    int q=tr[p].l;
    tr[p].l=tr[q].r;
    tr[q].r=p;
    p=q;
    pushup(tr[p].r),pushup(p);
}

void zag(int &p){//左旋 
    int q=tr[p].r;
    tr[p].r=tr[q].l;
    tr[q].l=p;
    p=q;
    pushup(tr[p].l),pushup(p);
}

结构体初始化，TREAP初始化：

const int N = 1e5+10,inf = 1e8;
struct treap{
    int l,r;
    int key,val;//val是随机赋值域
    int cnt,siz;
}tr[N];

int root,idx;

int add(int key){
    tr[++idx].key=key;
    tr[idx].val=rand();//随机域赋值
    tr[idx].siz=tr[idx].cnt=1;
    return idx;
}

void build(){
    add(-inf),add(inf);
    root=1,tr[1].r=2;
    tr[1].cnt=tr[1].siz=tr[2].cnt=tr[2].siz=0;//哨兵无实意
    pushup(root);
    if(tr[1].val < tr[2].val) zag(root);
    //万一随机有问题，然而 是否需要这么做 是有争议的，因为哨兵无实意
}

insert

void insert(int &p,int key){
    if(!p)  p=add(key);
    else if(key==tr[p].key) tr[p].cnt++;
    else if(key<tr[p].key){
        insert(tr[p].l,key);
        if(tr[tr[p].l].val>tr[p].val)   zig(p);
    }else{
        insert(tr[p].r,key);
        if(tr[tr[p].r].val>tr[p].val)   zag(p);
    }
    pushup(p);
}

可以看到，我们总是在插入过程中通过旋转使结构合理的同时在叶子节点插入数据，这一点可以尽可能使树的深度较小，因此叫平衡树。

delete（remove）

void remove(int &p,int key){
    if(!p)  return ;
    else if(key==tr[p].key){
        if(tr[p].cnt>1) tr[p].cnt--;
        else if(tr[p].r || tr[p].l){
            if(!tr[p].r || tr[tr[p].l].val>tr[tr[p].r].val){
                zig(p);
                remove(tr[p].r,key);
            }else{
                zag(p);
                remove(tr[p].l,key);
            }
        }else p=0;
    }else if(tr[p].key>key) remove(tr[p].l,key);
    else remove(tr[p].r,key);

    pushup(p);
}

在删除之前，我们总是将要删除节点向子节点移动。

get（rank by key/key by rank）

int get_rank_by_key(int p,int key){
    if(!p)  return 1;
    if(tr[p].key==key)  return tr[tr[p].l].siz+1;
    if(tr[p].key>key)   return get_rank_by_key(tr[p].l,key);
    return tr[tr[p].l].siz+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}

int get_key_by_rank(int p,int rank){
    if(!p)  return inf;
    if(tr[tr[p].l].siz>=rank)
        return get_key_by_rank(tr[p].l,rank);
    if(tr[tr[p].l].siz+tr[p].cnt>=rank) return tr[p].key;
    return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].siz-tr[p].cnt);
}

查询排名的过程就像走分叉路，然而通过 \texttt{TREAP} 的性质我们知道，分叉路口的另一条路有时是有意义的（当查找数在右子树时，左子树中任意数都小于查找数；然而向左子树查询时，右子树中任意数都不小于查找数），所以，在查找过程中，加加减减的事是常有的。

get lower-bound or upper-bound

int get_pre(int p,int key){
    if(!p)  return -inf;
    if(tr[p].key>=key)  return get_pre(tr[p].l,key);
    return max(tr[p].key,get_pre(tr[p].r,key));
}

int get_suf(int p,int key){
    if(!p)  return inf;
    if(tr[p].key<=key)  return get_suf(tr[p].r,key);
    return min(tr[p].key,get_suf(tr[p].l,key));
}

其实，还有一种非递归的写法，但倘若递归用不了，那么 \texttt{TREAP} 的大部分操作都用不了了。

int get_pre(int p,int key){
    int ans=1;
    //tr[ans].key=-inf，初始化答案 
    while(p){
        if(tr[p].key==key){
            //若有查找数，则其pre一定是其左子树的最右子节点 
            if(tr[p].l){
                p=tr[p].l;
                while(tr[p].r)  p=tr[p].r;
                ans=p;
            }
            break;//直接找到 
        }

        if(tr[p].key<key && tr[p].key>tr[ans].key)  ans=p;
        //尽可能更新答案 

        if(tr[p].key>key)   p=tr[p].l;
        else    p=tr[p].r;
        //p=(tr[p].key>key)?tr[p].l:tr[p].r;
    }

    return tr[ans].key;
}

int get_suf(int p,int key){
    int ans=2;
    //tr[ans].key=inf，初始化
    while(p){
        if(tr[p].key==key){
            if(tr[p].r){
                p=tr[p].r;
                while(tr[p].l)  p=tr[p].l;
                ans=p;
            }
            break;
        }

        if(tr[p].key>key && tr[p].key<tr[ans].key)  ans=p;
        p=(tr[p].key<key)?tr[p].r:tr[p].l;
    }
    return tr[ans].key;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10,inf = 1e8;
struct treap{
    int l,r;
    int key,val;
    int cnt,siz;
}tr[N];

int root,idx;

int n;

void pushup(int p){
    tr[p].siz=tr[tr[p].l].siz+tr[tr[p].r].siz+tr[p].cnt;
}

void zig(int &p){//右旋 
    int q=tr[p].l;
    tr[p].l=tr[q].r;
    tr[q].r=p;
    p=q;
    pushup(tr[p].r),pushup(p);
}

void zag(int &p){//左旋 
    int q=tr[p].r;
    tr[p].r=tr[q].l;
    tr[q].l=p;
    p=q;
    pushup(tr[p].l),pushup(p);
}

int add(int key){
    tr[++idx].key=key;
    tr[idx].val=rand();
    tr[idx].siz=tr[idx].cnt=1;
    return idx;
}

void build(){
    add(-inf),add(inf);
    root=1,tr[1].r=2;
    tr[1].cnt=tr[1].siz=tr[2].cnt=tr[2].siz=0;
    pushup(root);
    if(tr[1].val < tr[2].val) zag(root);
}

void insert(int &p,int key){
    if(!p)  p=add(key);
    else if(key==tr[p].key) tr[p].cnt++;
    else if(key<tr[p].key){
        insert(tr[p].l,key);
        if(tr[tr[p].l].val>tr[p].val)   zig(p);
    }else{
        insert(tr[p].r,key);
        if(tr[tr[p].r].val>tr[p].val)   zag(p);
    }
    pushup(p);
}

void remove(int &p,int key){
    if(!p)  return ;
    else if(key==tr[p].key){
        if(tr[p].cnt>1) tr[p].cnt--;
        else if(tr[p].r || tr[p].l){
            if(!tr[p].r || tr[tr[p].l].val>tr[tr[p].r].val){
                zig(p);
                remove(tr[p].r,key);
            }else{
                zag(p);
                remove(tr[p].l,key);
            }
        }else p=0;
    }else if(tr[p].key>key) remove(tr[p].l,key);
    else remove(tr[p].r,key);

    pushup(p);
}

int get_rank_by_key(int p,int key){
    if(!p)  return 1;
    if(tr[p].key==key)  return tr[tr[p].l].siz+1;
    if(tr[p].key>key)   return get_rank_by_key(tr[p].l,key);
    return tr[tr[p].l].siz+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}

int get_key_by_rank(int p,int rank){
    if(!p)  return inf;
    if(tr[tr[p].l].siz>=rank)
        return get_key_by_rank(tr[p].l,rank);
    if(tr[tr[p].l].siz+tr[p].cnt>=rank) return tr[p].key;
    return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].siz-tr[p].cnt);
}

int get_pre(int &p,int key){
    if(!p)  return -inf;
    if(tr[p].key>=key)  return get_pre(tr[p].l,key);
    return max(tr[p].key,get_pre(tr[p].r,key));
}

int get_suf(int &p,int key){
    if(!p)  return inf;
    if(tr[p].key<=key)  return get_suf(tr[p].r,key);
    return min(tr[p].key,get_suf(tr[p].l,key));
}

int main(){
    srand((unsigned)time(0));
    build();
    scanf("%d",&n);
    while(n--){
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1)  insert(root,x);
        else if(opt==2) remove(root,x);
        else if(opt==3) printf("%d\n",get_rank_by_key(root,x));
        else if(opt==4) printf("%d\n",get_key_by_rank(root,x));
        else if(opt==5) printf("%d\n",get_pre(root,x));
        else    printf("%d\n",get_suf(root,x));
    }
    return 0;
}

四、FHQ-treap

树的平衡不一定要用随机化来维持，有时也可以用上分块的思想。

FHQ-treap 是一种基于分裂、合并两种基础操作的强大平衡树。

关于具体原理，类比快排，先确定一个关键，将整个域分成具有关于关键的且不同的性质的两块，利用其中的信息进行查询，并在合并两块时使整棵树平衡，就和快排前半段小于等于、后半段大于等于类似。

FHQ-treap 支持一些 treap 不支持、splay 难以实现的操作，并且相对 treap 来讲，代码更简洁、更具使用价值。

贝抬：luogu 日报

有旋树堆-TREAP

上集回顾-REVIEW

特异性进化-EVOLUTION FOR SPECIFICTY

一、\texttt{BST} 形态转换：旋转-THE RETATION OF \texttt{BST}

简记：左旋拎右左挂右，右旋拎左右挂左——AgOH

二、树堆-TREAP

三、例题实操-PRACTICE FOR AN EXAMPLE

initialization of the treap

insert

delete（remove）

get（rank by key/key by rank）

get lower-bound or upper-bound

四、FHQ-treap