treap_b.cpp

一些重要的数据结构

#include<stdio.h>
#include<stdlib.h>
#include<time.h> 

typedef	struct	node{
		int ky,rp;
		struct node *lc,*rc;
}		Node;
void	lc_rolate(Node *&r){
		Node *t;
		t = r->rc;
		r->rc = t->lc;
		t->lc = r;
		r = t;
}
void	rc_rolate(Node *&r){
		Node *t;
		t = r->lc;
		r->lc = t->rc;
		t->rc = r;
		r = t;
}
void	ins(Node *&r,int d){
		if (r==NULL){
			r = new Node; 
			r->lc = NULL; r->rc = NULL;
			r->ky = d;  r->rp = rand();
			return;
		}
		if (d < r->ky){
			ins(r->lc,d);
			if (r->lc->rp < r->rp) rc_rolate(r);
		} else {
			ins(r->rc,d);
			if (r->rc->rp < r->rp) lc_rolate(r);
		}
}
void	del(Node *&r,int d){
		if (r==NULL) return;
		if (d<r->ky){ del(r->lc,d); return; }
		if (d>r->ky){ del(r->rc,d); return; }
		if (r->lc!=NULL && r->rc!=NULL){
			if (r->lc->rp < r->rc->rp){
				rc_rolate(r); del(r->rc,d);
			} else {
				lc_rolate(r); del(r->lc,d);
			}
			return;
		} 
		if (r->lc!=NULL){
			rc_rolate(r); del(r->rc,d); return; 
		}
		if (r->rc!=NULL){
			lc_rolate(r); del(r->lc,d); return;
		}
		delete r;  r = NULL;
}