首页 > 代码库 > POJ 3481

POJ 3481

2024-07-22 03:27:22   219人阅读

这是利用treap写的二叉排序树，只要理解其中旋转能够改变树的左右子树平衡度，即高度之差，差不多就能掌握treap树的要领了。

相对于其他高级BST，treap树实现应该算最简单了，利用的是随机树产生的理论的二叉排序树时间复杂度为O（nlgn）来实现，具体证明 算法导论 中有。

推荐NOCOW中的讲解，关于二叉排序树相当完整！

treap动画展示：http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/Treap-Example.html

 

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#include <ctime>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define INF 0x3f3f3f3f#define MAXN 100005using namespace std;int cnt=1, rt=0;struct Tree{    int key, num, pri, son[2];    void set(int _x, int _y, int _z){        key=_x;        num=_y;        pri=_z;        son[0]=son[1]=0;    }}T[MAXN];void rotate(int &x, int p) //1 右旋 0 左旋{    int y=T[x].son[!p];    T[x].son[!p]=T[y].son[p];    T[y].son[p]=x;    x=y;}void ins(int &x, int key, int num){    if(x == 0)        T[x=cnt++].set(key, num, rand());    else    {        int p=key < T[x].key;        ins(T[x].son[!p], key, num);        if(T[x].pri < T[T[x].son[!p]].pri) rotate(x, p);    }}void del(int &x, int key){    if(T[x].key == key)    {        if(T[x].son[0] && T[x].son[1])        {            int p=T[T[x].son[0]].pri > T[T[x].son[1]].pri;            rotate(x, p);            del(T[x].son[p], key);        }        else        {            if(!T[x].son[0]) x=T[x].son[1];            else x=T[x].son[0];        }    }    else    {        int p=T[x].key > key;        del(T[x].son[!p], key);    }}int get(int x, int p){    while(T[x].son[p])        x=T[x].son[p];    return x;}int main (){    srand(time(NULL));    int p, key, num, x;    while(scanf("%d", &p) && p)    {        switch (p)        {            case 1:                scanf("%d%d", &num, &key);                ins(rt, key, num);                break;            case 2:                x=get(rt, 1);                if(x)                {                    printf("%d\n",T[x].num);                    del(rt, T[x].key);                }                else                    printf("0\n");                break;            case 3:                x=get(rt, 0);                if(x)                {                    printf("%d\n",T[x].num);                    del(rt, T[x].key);                }                else                    printf("0\n");        }    }    return 0;}

 

POJ 3481


联系
我们