Treap总结

佚名 6年前 (2020-02-08) 算法 2129人围观抢沙发百度已收录

\(Treap = Tree + Heap\)

树堆（Treap），在数据结构中也称Treap，是指有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为O(logn)。相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。
                                                                                   ----百度百科

要了解Treap，就先要看看什么是二叉搜索树

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
                                                                                   ----百度百科

Treap既有BST的性质，也有堆的性质，Treap的每个结点额外附加一个随机值（优先级），让他们按照关键码构成BST的同时也满足堆的性质（父节点优先级高于或低于子节点优先级），因为优先级是随机的，这样在绝大多数情况下我们得到的树都是平衡的，不容易被卡成链，单次操作期望时间复杂度为O(logn)。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

操作：

1.定义

struct Treap {
    int dat, val; 
    int cnt, size, l, r;
} e[N];

dat 随机优先级； val BST关键码； cnt 当前结点数量； size 子树结点数量； l，r 左右儿子。
2.更新

void update(int p) {
    e[p].size = e[e[p].l].size + e[e[p].r].size + e[p].cnt;
}

更新结点size值。
3.新建结点

int newpoint(int val) {
    e[++tot].val = val;
    e[tot].dat = rand();
    e[tot].cnt = e[tot].size = 1;
    return tot;
}

4.建树

void build() {
    newpoint(-inf); newpoint(inf);
    root = 1; e[root].r = 2; update(root);
}

初始化两个结点，设置为无限大和无限小。
5.左右旋转
左右旋转是在保证BST性质前提下（中序遍历不变）将一个结点向上或者向下转，实质上是父节点变成了子节点，子节点变成了父节点。
左旋和右旋分别对应着将左儿子翻上来和将右儿子翻上来。

具体操作

void zig(int &p) {//左旋
    int q = e[p].l;
    e[p].l = e[q].r; e[q].r = p; p = q;
    update(e[p].r); update(p);
}
void zag(int &p) {//右旋
    int q = e[p].r;
    e[p].r = e[q].l; e[q].l = p; p = q;
    update(e[p].l); update(p);
}
//p引用的是旋转前的根结点

6.插入
插入一个值为val的结点，若存在关键码为val的结点，将此结点数量 + 1，若不存在，根据val大小和当前结点val大小向左右两边找，最后新建结点，返回时要维护堆性质。

void insert(int &p, int val) {
    if(p == 0) {
        p = newpoint(val); return ;
    }
    if(e[p].val == val) {
        e[p].cnt++; update(p);
        return ;
    }
    if(val < e[p].val) {
        insert(e[p].l, val);
        if(e[p].dat < e[e[p].l].dat) zig(p);
    } else {
        insert(e[p].r, val);
        if(e[p].dat < e[e[p].r].dat) zag(p);
    }
    update(p);
}

7.删除结点
删除一个值为法val的结点，先在树中查找值为val的结点：
1.若结点cnt(数量) 大于1，则可以直接减1，返回；
2.若结点数量为1，将其向下旋转，转到叶结点时直接删除；
注意：在向下旋转时应维护堆的性质，若是大根堆，选取子节点中dat大的结点与其交换。

void delet(int &p, int val) {
    if(p == 0) return ;
    if(val == e[p].val) {
        if(e[p].cnt > 1) {
            e[p].cnt--; update(p); return ;
        } else {
            if(e[p].l || e[p].r) {//不为叶结点
                if(e[e[p].l].dat > e[e[p].r].dat || !e[p].r) 
                    zig(p), delet(e[p].r, val);
                else 
                    zag(p), delet(e[p].l, val);
                update(p);
            } else p = 0;
        }//else
        return ;
    }
    if(val < e[p].val) delet(e[p].l, val);  
    else delet(e[p].r, val);
    update(p);
}

8.排名
包括根据值查排名和根据排名查值。
1.根据值查排名(rankk();)我们只需要从根节点往下找，如果当前结点值较大，递归查询左儿子；如果当前结点值较小，递归查询右儿子，返回时要加上左子树结点数和当前节点的数量。
2.根据排名查值(arcrank();)，同样，如果当前结点值较大，递归查询左儿子；如果当前结点值较小，递归查询右儿子，注意查询右儿子时应将排名减去左子树和当前结点的数量。

int rankk(int p, int val) {
    if(p == 0) return 0;
    if(val == e[p].val) return e[e[p].l].size + 1;
    if(val < e[p].val) return rankk(e[p].l, val);
    return rankk(e[p].r, val) + e[e[p].l].size + e[p].cnt;
}
int arcrank(int p, int k) {
    if(p == 0) return inf;
    if(k <= e[e[p].l].size) return arcrank(e[p].l, k);
        if(k <= e[p].cnt + e[e[p].l].size) return e[p].val;
    return arcrank(e[p].r, k - e[p].cnt - e[e[p].l].size);
}

9.查询前驱和后继
拿前驱来说，若查询v的前驱，分两种情况：
1.找到了值为v的结点，那么v的前驱就是v的左子树中值最大的点的值，找到直接返回。
2.没有找到结点为v的值，需要不断比较，若当前结点值比v小且比找到的答案大，就更新答案。
后继与前驱类似。

int getper(int val) {
    int p = root, ans = 1;//初始化为无限小
    while(p) {
        if(val == e[p].val) {
            if(e[p].l) {
                p = e[p].l;
                while(e[p].r) p = e[p].r;
                ans = p;
            }
            break;
        }
        if(e[p].val < val && e[ans].val < e[p].val) ans = p;//比较，更新答案
        if(val < e[p].val) p = e[p].l;
        else p = e[p].r;
    }
    return e[ans].val;
}
int getnext(int val) {
    int p = root, ans = 2;//初始化为无限大
    while(p) {
        if(val == e[p].val) {
            if(e[p].r) {
                p = e[p].r;
                while(e[p].l) p = e[p].l;
                ans = p;
            }
            break;
        }
        if(e[p].val > val && e[ans].val > e[p].val) ans = p;
        if(val < e[p].val) p = e[p].l;
        else p = e[p].r;
    }
    return e[ans].val;
}

完整代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 100005;
const int inf = (1 << 31) - 1;
int n, root, tot = 0;
struct Treap {
    int dat, val;
    int cnt, size, l, r;
} e[N];
void update(int p) {
    e[p].size = e[e[p].l].size + e[e[p].r].size + e[p].cnt;
}
int newpoint(int val) {
    e[++tot].val = val;
    e[tot].dat = rand();
    e[tot].cnt = e[tot].size = 1;
    return tot;
}
void build() {
    newpoint(-inf); newpoint(inf);
    root = 1; e[root].r = 2; update(root);
}
void zig(int &p) {
    int q = e[p].l;
    e[p].l = e[q].r; e[q].r = p; p = q;
    update(e[p].r); update(p);
}
void zag(int &p) {
    int q = e[p].r;
    e[p].r = e[q].l; e[q].l = p; p = q;
    update(e[p].l); update(p);
}
void insert(int &p, int val) {
    if(p == 0) {
        p = newpoint(val); return ;
    }
    if(e[p].val == val) {
        e[p].cnt++; update(p);
        return ;
    }
    if(val < e[p].val) {
        insert(e[p].l, val);
        if(e[p].dat < e[e[p].l].dat) zig(p);
    } else {
        insert(e[p].r, val);
        if(e[p].dat < e[e[p].r].dat) zag(p);
    }
    update(p);
}
void delet(int &p, int val) {
    if(p == 0) return ;
    if(val == e[p].val) {
        if(e[p].cnt > 1) {
            e[p].cnt--; update(p); return ;
        } else {
            if(e[p].l || e[p].r) {
                if(e[e[p].l].dat > e[e[p].r].dat || !e[p].r) 
                    zig(p), delet(e[p].r, val);
                else 
                    zag(p), delet(e[p].l, val);
                update(p);
            } else p = 0;
        }
        return ;
    }
    if(val < e[p].val) delet(e[p].l, val);  
    else delet(e[p].r, val);
    update(p);
}
int rankk(int p, int val) {
    if(p == 0) return 0;
    if(val == e[p].val) return e[e[p].l].size + 1;
    if(val < e[p].val) return rankk(e[p].l, val);
    return rankk(e[p].r, val) + e[e[p].l].size + e[p].cnt;
}
int arcrank(int p, int k) {
    if(p == 0) return inf;
    if(k <= e[e[p].l].size) return arcrank(e[p].l, k);
    else if(k <= e[p].cnt + e[e[p].l].size) return e[p].val;
    return arcrank(e[p].r, k - e[p].cnt - e[e[p].l].size);
}
int getper(int val) {
    int p = root, ans = 1;
    while(p) {
        if(val == e[p].val) {
            if(e[p].l) {
                p = e[p].l;
                while(e[p].r) p = e[p].r;
                ans = p;
            }
            break;
        }
        if(e[p].val < val && e[ans].val < e[p].val) ans = p;
        if(val < e[p].val) p = e[p].l;
        else p = e[p].r;
    }
    return e[ans].val;
}
int getnext(int val) {
    int p = root, ans = 2;
    while(p) {
        if(val == e[p].val) {
            if(e[p].r) {
                p = e[p].r;
                while(e[p].l) p = e[p].l;
                ans = p;
            }
            break;
        }
        if(e[p].val > val && e[ans].val > e[p].val) ans = p;
        if(val < e[p].val) p = e[p].l;
        else p = e[p].r;
    }
    return e[ans].val;
}
int main() {
//  freopen("data.in", "r", stdin);
    scanf("%d", &n); build();
    while(n--) {
        int opt, x; scanf("%d%d", &opt, &x);
        switch(opt) {
            case 1:
                insert(root, x);
                break;
            case 2:
                delet(root, x);
                break;
            case 3:
                printf("%d\n", rankk(root, x) - 1);
                break;
            case 4:
                printf("%d\n", arcrank(root, x + 1));
                break;
            case 5:
                printf("%d\n", getper(x));
                break;
            case 6:
                printf("%d\n", getnext(x));
                break;
        }
    }
    return 0;
}