平衡树 非旋Treap(FHQ_Treap)

普通的Treap已经在我草稿箱里面带了快五个月了,咕咕咕
这篇文章就讲非旋Treap, 在一些比较正常的平衡树的题中非旋Treap相对于Splay,有代码量更少,细节更少,更好差错等诸多有点,因此除非必要情况我一般来说还是比较喜欢写非旋Treap,Splay每次都要重新推一遍旋转的关系感觉好烦QAQ,
非旋Treap一听就是一个不用旋转的,平衡树和堆的性质的东西,因此和Treap一样需要随机数来维护堆的性质(大根堆和小根堆无所谓,只要样子上还是一个堆的样子就好)
PS:我就不说怎么不让他变维护nlogn了,就默认Treap已经会的差不多了
Treap也是需要通过旋转来维护堆的性质,如果不满足的话就旋转这个结点,
但是非旋Treap维护的就很暴力, 非旋Treap只有两个核心操作分类Split和合并Merge这种两个操作

// split 就是以val的值分裂成两个树,两个根分别为x和y,x上的值均小于等于val,y上的值均大于val
void split(int u, int val, int& x,int& y);
// 将两棵树按照BST和随机堆的性质合并, 
int Merge(int x, int y);
// 新建结点,并且返回结点下标
int newnod(int val);

在下面会详细介绍上面的两部操作,目前只是引入这两个函数
若是已经实现这两步操作的话,那么对于insert操作

现在我只需要按照数值11来分裂这颗树,然后依次合并 树 newnode 树,这三部分形成新的树,
对于其他的题可能是会需要按照下标来分裂的

这样在合并成新的树就会得到一个满足BST和随机堆性质的树,
对于删除等操作依然是基于这两个函数,这里并不会详细介绍了(大概)

Split操作


void split(int u, int val, int& x,int& y)
{
    if(!u) x = y = 0; 
    else
    {
        if(tr[u].val <= val){x = u;split(tr[u].r, val, tr[u].r, y);}
        // 如果这个结点小于等于val, 那么我们就把这个节点接到上一层的x上,并且继续把这个结点的右儿子继续分裂
        else{y = u;split(tr[u].l, val, x, tr[u].l);}
        // 如果这个点大于val那么这个点需要接到上一层的y上,并且继续分裂这个结点的左儿子
        update(u); // 每次有对结点修改都需要更新结点的一些信息
    }
}
PS:上一层和下一层的关系是x,ytr[u].l, tr[u].r之间互相的对应的关系来实现的

Merge操作


int Merge(int x, int y)
{
    if(!x || !y) return x + y; // 如果有一棵树为空只需要返回不为空的下标
    if(tr[x].rnd > tr[y].rnd) // 满足随机堆的性质
    {
        tr[x].r = Merge(tr[x].r, y); //  将x的右子树和y合并,并且把合并后的关系标为x的右儿子, 此刻满足BST的性质, 下面统里
        update(x);
        return x;
    }
    tr[y].l = Merge(x, tr[y].l);
    update(y); // 每次对结点的操作一定要更新的一些这个结点的信息
    return y;
}

下面附上insert   and   remove操作的代码


void insert(int val)
{
    split(root, val, x ,y);
    root = Merge(Merge(x, newnod(val)), y);
}
void remove(int val)
{
    split(root, val, x, z);
    split(x, val - 1, x, y);
    y = Merge(tr[y].l, tr[y].r);
    root = Merge(Merge(x, y), z);
}

普通平衡树AC代码

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define int ll
#define eps 1e-9
#define endl '\n'
#define gcd __gcd
#define pi acos(-1)
#define ll long long
#define LL long long
#define IDX(x) x - 'A'
#define idx(x) x - 'a'
#define idz(x) x - '0'
#define ld long double
#define lowebit(x) x&(-x)
#define rint register int
#define Len(x) (int)(x).size()
#define all(s) (s).begin(), (s).end()
using namespace std;
inline int read()
{
    register int x = 0, f = 1, ch = getchar();
    while( !isdigit(ch) ){if(ch == '-') f = -1; ch = getchar();}
    while( isdigit(ch) ){x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
const int maxn = 1e5 + 5;
struct fhq
{
    int l, r, val, sie, rnd;
}tr[maxn];
mt19937 rnd(11655);
int root, tot;
int newnod(int val)
{
    int now = ++ tot;
    tr[now].val = val;
    tr[now].sie = 1;
    tr[now].rnd = rnd();
    return now;
}
void update(int pos)
{
    tr[pos].sie = tr[tr[pos].l].sie + tr[tr[pos].r].sie + 1;
}

void split(int u, int val, int& x,int& y)
{
    if(!u) x = y = 0;
    else
    {
        if(tr[u].val <= val){x = u;split(tr[u].r, val, tr[u].r, y);}
        else{y = u;split(tr[u].l, val, x, tr[u].l);}
        update(u);
    }
}
int Merge(int x, int y)
{
    if(!x || !y) return x + y;
    if(tr[x].rnd > tr[y].rnd)
    {
        tr[x].r = Merge(tr[x].r, y);
        update(x);
        return x;
    }
    tr[y].l = Merge(x, tr[y].l);
    update(y);
    return y;
}
int x, y, z;
void insert(int val)
{
    split(root, val, x ,y);
    root = Merge(Merge(x, newnod(val)), y);
}
void remove(int val)
{
    split(root, val, x, z);
    split(x, val - 1, x, y);
    y = Merge(tr[y].l, tr[y].r);
    root = Merge(Merge(x, y), z);
}
void ranks(int val)
{
    split(root, val - 1, x, y);
    cout << tr[x].sie + 1 << endl;
    root = Merge(x, y);
}
void num(int val)
{
    int now = root;
    while(now)
    {
        if(tr[tr[now].l].sie + 1 == val) break;
        if(tr[tr[now].l].sie >= val) now = tr[now].l;
        else {val -= tr[tr[now].l].sie + 1; now = tr[now].r;}
    }
    cout << tr[now].val << endl;
}
void pre(int val)
{
    split(root, val - 1, x, y);
    int now = x;
    while(tr[now].r) now = tr[now].r;
    cout << tr[now].val << endl;
    root = Merge(x, y);
}
void nex(int val)
{
    split(root, val, x, y);
    int now = y;
    while(tr[now].l) now = tr[now].l;
    cout << tr[now].val << endl;
    root = Merge(x, y);
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    clock_t c1ockck = clock();
    // .....................................
    int n = read();
    for(int i = 1 ; i<= n ; i ++)
    {
        int opt =read(), x = read();
        if(opt == 1) insert(x);
        if(opt == 2) remove(x);
        if(opt == 3) ranks(x);
        if(opt == 4) num(x);
        if(opt == 5) pre(x);
        if(opt == 6) nex(x);
    }
    // .....................................
    cerr << endl << "Time:" << clock() - c1ockck << "ms" <<endl;
    return 0;
}

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注