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

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

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

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

亚洲人成网站999久久久综合| 奇米综合四色77777久久| 久久精品视频网| 精品久久久久久久久久久久久久久 | 亚洲精品tv久久久久| 亚洲国产成人久久综合一区77| 久久久久亚洲AV成人网人人网站| 亚洲AV无码一区东京热久久 | 久久精品女人天堂AV麻| 久久久无码精品亚洲日韩蜜臀浪潮| 99久久成人国产精品免费| 国产视频久久| 久久AV高清无码| 狠狠色丁香久久婷婷综合_中| 国内精品久久久久影院日本| 无码精品久久一区二区三区 | 91精品国产高清久久久久久io| 亚洲国产精品狼友中文久久久 | 久久久WWW成人免费毛片| 久久亚洲精品人成综合网| 欧美亚洲另类久久综合婷婷| 久久精品免费观看| 精品免费久久久久久久| 久久国产免费直播| 漂亮人妻被中出中文字幕久久| 国产巨作麻豆欧美亚洲综合久久 | 久久人人爽人人爽人人AV | 国产精品gz久久久| 成人a毛片久久免费播放| 2022年国产精品久久久久 | 99热成人精品免费久久| 精品久久久久久成人AV| 无码日韩人妻精品久久蜜桃| 97精品伊人久久久大香线蕉 | 国产三级久久久精品麻豆三级 | 久久久国产精品网站| 1000部精品久久久久久久久| 国产午夜免费高清久久影院| 久久精品国产一区二区三区日韩| 国产精品美女久久久久| 亚洲国产精品久久久久婷婷软件|