巢穴

about:blank

My Links

Blog Stats

Posts - 74
Stories - 1
Comments - 16
Trackbacks - 0

News

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

文章檔案

2010年12月 (1)

Link

lxr
zh
北極天南星
我的豆瓣

搜索

閱讀排行榜

評論排行榜

P3481

裸treap...
學會了刪除..
orz..

#include <iostream>

//#include <fstream>

using namespace std;

//ifstream fin("t3481.in");

const int MAXN=100000;

const int INF=0x7fffffff;

int len=0;

struct node

{

node *left,*right;

int key,r_key,value;

}*root,tree[MAXN];

/*

a

/ \

c b

/ \ / \

g fd e

*/

void RotateLeft(node *&x)

{

node *z=x->right;

x->right=z->left;

z->left=x;

x=z;

}

void RotateRight(node *&x)

{

node *z=x->left;

x->left=z->right;

z->right=x;

x=z;

}

void insert(node *&x,int value,int key)

{

if (NULL==x)

{

node *p=&tree[len++];

p->left=NULL;

p->right=NULL;

p->key=key;

p->value=value;

p->r_key=rand();

x=p;

return;

}

if (x->key<=key)

{

insert(x->right,value,key);

if (x->r_key>x->right->r_key) RotateLeft(x);

}

else

{

insert(x->left,value,key);

if (x->r_key>x->left->r_key) RotateRight(x);

}

void _delete(node *&x,int key)

{

if (x==NULL) return;

if (x->key>key) _delete(x->left,key);

else

if (x->key<key) _delete(x->right,key);

else

{

if (x->left==NULL&&x->right==NULL)

{

x=NULL;

return;

}

else

{

int ll,rr;

ll=x->left==NULL?INF:x->left->r_key;

rr=x->right==NULL?INF:x->right->r_key;

if (ll<rr)

{

RotateRight(x);

}

else

{

RotateLeft(x);

}

_delete(x,key);

}

void find_max(node *x)

{

if (NULL==x) {cout<<0<<endl;return;}

if (x->right!=NULL)

{

find_max(x->right);

}

else

{

cout<<x->value<<endl;

_delete(root,x->key);

return;

}

void find_min(node *x)

{

if (NULL==x) {cout<<0<<endl;return;}

if (x->left!=NULL)

{

find_min(x->left);

}

else

{

cout<<x->value<<endl;

_delete(root,x->key);

return;

}

int edit;

int main()

{

root=NULL;

while(1)

{

int x,y;

cin>>edit;

if (0==edit) break;

switch(edit)

{

case 1:cin>>x>>y;insert(root,x,y);break;

case 2:find_max(root);break;

case 3:find_min(root);break;

default:break;

}

//system("pause");

return 0;

}

posted on 2009-10-13 16:23 Vincent 閱讀(93) 評論(0) 編輯收藏引用所屬分類: 數據結構與算法

只有注冊用戶登錄后才能發表評論。


相關文章: P3368 P2352 dinic P3273 P2104 ctsc2000 丘比特的煩惱 usaco 4.3 lgame P3267 P1276 P1837

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

巢穴

My Links

Blog Stats

News

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

文章檔案

Link

搜索

最新評論

閱讀排行榜

評論排行榜

P3481