POJ 3481 treap
生活随笔
收集整理的這篇文章主要介紹了
POJ 3481 treap
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
這是利用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 100005 using namespace std; int cnt=, rt=; struct Tree{
int key, num, pri, son[];
void set(int _x, int _y, int _z){
key=_x;
num=_y;
pri=_z;
son[]=son[]=;
}
}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 == )
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[] && T[x].son[])
{
int p=T[T[x].son[]].pri > T[T[x].son[]].pri;
rotate(x, p);
del(T[x].son[p], key);
}
else
{
if(!T[x].son[]) x=T[x].son[];
else x=T[x].son[];
}
}
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 :
scanf("%d%d", &num, &key);
ins(rt, key, num);
break;
case :
x=get(rt, );
if(x)
{
printf("%d\n",T[x].num);
del(rt, T[x].key);
}
else
printf("0\n");
break;
case :
x=get(rt, );
if(x)
{
printf("%d\n",T[x].num);
del(rt, T[x].key);
}
else
printf("0\n");
}
}
return ;
}
總結
以上是生活随笔為你收集整理的POJ 3481 treap的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 爱女房间挂别人女儿照片好吗
- 下一篇： 结婚在农村办理婚礼 在农村座福 市区有