<ins id="pjuwb"></ins>

<blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

<noscript id="pjuwb"></noscript>

<sup id="pjuwb"><pre id="pjuwb"></pre></sup>

<dd id="pjuwb"></dd>

<abbr id="pjuwb"></abbr>

巢穴

about:blank

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 閱讀(87) 評論(0) 編輯收藏引用所屬分類: 數據結構與算法

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

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

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

国产成人香蕉久久久久| 国产激情久久久久影院| 久久综合鬼色88久久精品综合自在自线噜噜 | 久久精品国产精品国产精品污| 久久人人爽人人爽人人片AV不| 亚洲精品乱码久久久久久蜜桃图片| 久久久久亚洲AV片无码下载蜜桃| 久久se精品一区精品二区| 日韩亚洲国产综合久久久| 国产精品久久久久久久久鸭| 久久噜噜久久久精品66| 日韩人妻无码精品久久免费一| 国产99久久久久久免费看| 蜜臀av性久久久久蜜臀aⅴ麻豆| 国产69精品久久久久99| 国产激情久久久久久熟女老人 | 国产精品久久婷婷六月丁香| 久久精品国产亚洲av高清漫画| 三级片免费观看久久| 女人香蕉久久**毛片精品| 无码AV波多野结衣久久| 色婷婷综合久久久久中文字幕 | 久久受www免费人成_看片中文| 久久99国产精品久久99| 久久精品中文闷骚内射| 久久人人爽人人爽人人片AV高清 | 国产99久久久国产精品～～牛| 亚洲精品国产美女久久久| 久久久久久久久久久| 亚洲国产成人久久一区WWW| 国产精品免费久久久久电影网| 久久精品国产精品亚洲精品| 久久99精品久久只有精品| 久久久久久午夜成人影院 | 一级做a爰片久久毛片看看| 久久久久香蕉视频| 国产亚洲欧美另类久久| 91精品国产综合久久香蕉 | 久久精品人人做人人爽97| 青草国产精品久久久久久| 国产精品一区二区久久不卡|