<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 管理

精品久久人人妻人人做精品| 伊人久久五月天| 久久亚洲精品视频| 亚洲欧美精品伊人久久| 久久青青草原精品国产软件| 思思久久99热只有频精品66| 久久w5ww成w人免费| 欧美精品一区二区久久| 久久久久亚洲av无码专区喷水 | 久久九九久精品国产免费直播| 久久久久久青草大香综合精品| 久久精品国产乱子伦| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 久久亚洲av无码精品浪潮| 亚洲精品乱码久久久久久| 久久精品成人影院| 狠狠88综合久久久久综合网| 久久影院亚洲一区| 久久亚洲国产中v天仙www| 日韩精品无码久久久久久| 久久久WWW成人| 日本免费一区二区久久人人澡| 久久久久免费精品国产| 国产亚州精品女人久久久久久 | 久久人人爽爽爽人久久久| 亚洲国产精品成人AV无码久久综合影院| 久久综合国产乱子伦精品免费| 久久夜色撩人精品国产| 国产精品丝袜久久久久久不卡| 漂亮人妻被黑人久久精品| 久久热这里只有精品在线观看| 久久久WWW成人免费精品| 久久93精品国产91久久综合| 91精品国产91久久久久久蜜臀| 国产人久久人人人人爽| 国产精品久久久天天影视| 1000部精品久久久久久久久| MM131亚洲国产美女久久| 国产精品一久久香蕉产线看| 久久精品国产清高在天天线| 欧美黑人又粗又大久久久|