平衡树第一章 -------- treap

· · 个人记录

前置知识

BST.

BST 例题.

堆.

正文

注，此文内容均以 P3369 展开讲解。

treap 是一种弱平衡的平衡树，是重要又简单的 FHQ-treap 的铺垫。

顾名思议 treap=tree+heap。

如果我们在同样的 val 下，堆性质和 BST 性质不可能同时满足。

但是，我们肯定得先满足 BST 性质，那么堆性质又该怎么满足呢。

那么只维护 BST 性质可不行呀，我们的树的平衡哪去了。

BST 有个性质，就是随机键值下 BST 的每个操作时间复杂度为 \text O(\log n)。

于是我们可以以随机键值来维护堆，以保证树的平衡。

这两个性质维护下来，那颗 BST 的结构就是唯一的了。

.

先看节点定义。

struct node{
    node *l,*r;//子节点
    int val,data,cnt,siz;//权值，随机键值，数据数量，子树大小
};

treap内的定义。

node *root;//根节点
node *null;//模拟空节点
node* new_root(int val){//新建节点
    node *p=new node;
    p->val=val,p->data=rand();
    p->cnt=p->siz=1,p->l=p->r=null;
    return p;
}
void update(node *x){//重置节点的siz
    x->siz=x->l->siz+x->r->siz+x->cnt;
}
void build(){//建树
    null=new node;
    null->l=null->r=null;
    null->siz=null->val=null->cnt=null->data=0;
    root=null;
}
tree(){//新建空树
    build();
}

前面说到，我们需要维护这个堆性质。

那怎么维护呢。

那就是左旋(zag)与右旋(zig)。

左旋操作，可以将 A 下旋至这颗子树的根节点的右节点并不改变 BST 性质。

也可以改变 ABCDE 的随机键值的位置以维护堆性质。

        A
       / \
      B   C
         / \
        D   E

To

        C
       / \
      A   E
     / \
    B   D

右旋操作,可以将 A 下旋至这颗子树的根节点的左节点并不改变 BST 性质。

可以改变 ABCDE 的随机键值的位置以维护堆性质。

        A
       / \
      B   C
     / \
    D   E

To

        B
       / \
      D   A
         / \
        E   C

神奇吗，treap 就是用旋转维护堆性质的。

左右旋转的代码。

void zig(node *&p){
    node *q=p->l;
    p->l=q->r,q->r=p,p=q;
    update(p->r),update(p);
}
void zag(node *&p){
    node *q=p->r;
    p->r=q->l,q->l=p,p=q;
    update(p->l),update(p);
}

插入，与普通 BST差不多，当然，边插入边维护堆性质。

void insert(int val,node *&p){
        if(p==null){
            p=new_root(val);
            return;
        }
        if(val==p->val){
            p->cnt++;
            update(p);
            return;
        }
        if(val<p->val){
            insert(val,p->l);
            if(p->data<p->l->data) zig(p);
        }
        else{
            insert(val,p->r);
            if(p->data<p->r->data) zag(p);
        }
        update(p);
    }

删除，这里与 BST 不一样，如果与 BST 一样删除，堆性质的维护会很复杂。

所以我们用旋转将需要删除的节点旋转到叶节点直接删除。

void erase(int val,node *&p){
    if(p==null) return;
    if(val==p->val){
        if(p->cnt>1){
            p->cnt--,update(p);
            return;
        }
        if(p->l!=null || p->r!=null){
            if(p->r==null || p->l->data>p->r->data)
                zig(p),erase(val,p->r);
            else
                zag(p),erase(val,p->l);
            update(p);
        }
        else p=null;
        return;
    }
    if(val<p->val) erase(val,p->l);
    else erase(val,p->r);
    update(p);
}

查排名，与 BST 差不多。

int ranks(int x){
    int ans=1;
    node *p=root;
    while(p!=null){
        if(p->val>=x) p=p->l;
        else{
            ans+=p->l->siz+p->cnt;
            p=p->r;
        }
    }
    return ans;
}

查第 k 小的数，与 BST 差不多。

int get(int x,node *p){
    if(p->l->siz<x && x<=p->l->siz+p->cnt) return p->val;
    else if(p->l->siz+p->cnt<x) return get(x-p->l->siz-p->cnt,p->r);
    else return get(x,p->l);
}

查前驱后继，与 BST 差不多。

int pre_find(int val){
    return get(ranks(val)-1,root);
}
int next_find(int val){
    return get(ranks(val+1),root);
}

代码。

#include<bits/stdc++.h>
using namespace std;
struct node{
    node *l,*r;
    int val,data,cnt,siz;
};
struct tree{
    node *root;
    node *null;
    node* new_root(int val){
        node *p=new node;
        p->val=val,p->data=rand();
        p->cnt=p->siz=1,p->l=p->r=null;
        return p;
    }
    void update(node *x){
        x->siz=x->l->siz+x->r->siz+x->cnt;
    }
    void build(){
        null=new node;
        null->l=null->r=null;
        null->siz=null->val=null->cnt=null->data=0;
        root=null;
    }
    tree(){
        build();
    }
    int ranks(int x){
        int ans=1;
        node *p=root;
        while(p!=null){
            if(p->val>=x) p=p->l;
            else{
                ans+=p->l->siz+p->cnt;
                p=p->r;
            }
        }
        return ans;
    }
    int get(int x,node *p){
        if(p->l->siz<x && x<=p->l->siz+p->cnt) return p->val;
        else if(p->l->siz+p->cnt<x) return get(x-p->l->siz-p->cnt,p->r);
        else return get(x,p->l);
    }
    void zig(node *&p){
        node *q=p->l;
        p->l=q->r,q->r=p,p=q;
        update(p->r),update(p);
    }
    void zag(node *&p){
        node *q=p->r;
        p->r=q->l,q->l=p,p=q;
        update(p->l),update(p);
    }
    void insert(int val,node *&p){
        if(p==null){
            p=new_root(val);
            return;
        }
        if(val==p->val){
            p->cnt++;
            update(p);
            return;
        }
        if(val<p->val){
            insert(val,p->l);
            if(p->data<p->l->data) zig(p);
        }
        else{
            insert(val,p->r);
            if(p->data<p->r->data) zag(p);
        }
        update(p);
    }
    int pre_find(int val){
        return get(ranks(val)-1,root);
    }
    int next_find(int val){
        return get(ranks(val+1),root);
    }
    void erase(int val,node *&p){
        if(p==null) return;
        if(val==p->val){
            if(p->cnt>1){
                p->cnt--,update(p);
                return;
            }
            if(p->l!=null || p->r!=null){
                if(p->r==null || p->l->data>p->r->data)
                    zig(p),erase(val,p->r);
                else
                    zag(p),erase(val,p->l);
                update(p);
            }
            else p=null;
            return;
        }
        if(val<p->val) erase(val,p->l);
        else erase(val,p->r);
        update(p);
    }
};
tree p=tree();
int main() {
    int t;
    cin>>t;
    while(t--){
        int opt,x;
        cin>>opt>>x;
        if(opt==1) p.insert(x,p.root);
        if(opt==2) p.erase(x,p.root);
        if(opt==3) cout<<p.ranks(x)<<"\n";
        if(opt==4) cout<<p.get(x,p.root)<<"\n";
        if(opt==5) cout<<p.pre_find(x)<<"\n";
        if(opt==6) cout<<p.next_find(x)<<"\n";
    }
    return 0;
}

总结

我们来对比一下一些平衡树。

treap 是所有平衡树中最基础的那个。

它的旋转操作与随机权值用到了很多平衡树上。

treap 的代码还是有点长度的。

所以有没有更好写的平衡树呢。

所以下一章，平衡树第二章 -------- 大获全胜的暴力 之 替罪羊树，能解决此问题。