巢穴

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 阅读(108) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理