• <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)  編輯 收藏 引用  所屬分類: 數據結構與算法 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



欧美精品一区二区久久|
青青草国产97免久久费观看|
久久亚洲精品无码AV红樱桃|
97精品伊人久久大香线蕉app|
国产精品久久久99|
久久久久久精品免费免费自慰|
亚洲精品无码久久一线|
亚洲国产精品久久久久|
中文字幕久久精品无码|
久久久久99精品成人片三人毛片|
亚洲精品无码久久不卡|
一本久久久久久久|
性色欲网站人妻丰满中文久久不卡|
久久福利青草精品资源站|
狠狠色婷婷久久综合频道日韩|
国产精品久久久久久一区二区三区|
亚洲精品97久久中文字幕无码|
99国产欧美精品久久久蜜芽|
亚洲国产精品一区二区三区久久|
久久国产精品99国产精|
久久精品亚洲AV久久久无码|
精品国产青草久久久久福利|
国产精品久久久久无码av|
久久精品国产亚洲AV久
|
亚洲伊人久久成综合人影院
|
国内精品人妻无码久久久影院
|
国产精品久久久久免费a∨|
久久99久久无码毛片一区二区|
99国产欧美久久久精品蜜芽|
久久久一本精品99久久精品66|
精品久久人人爽天天玩人人妻|
亚洲国产成人久久笫一页|
久久久91人妻无码精品蜜桃HD|
久久免费小视频|
91性高湖久久久久|
国产AV影片久久久久久|
观看 国产综合久久久久鬼色 欧美 亚洲 一区二区
|
久久婷婷国产综合精品|
久久精品亚洲日本波多野结衣|
久久精品无码专区免费青青|
国产精品99久久免费观看|