treap.cpp

treap的c++实现。有良好的可读性。并且多次验证了可行性

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef struct node{
	long data,rp,ln,rn;
	struct node *lc,*rc;
}ptr;

void left_rotate(ptr *&bst){
	ptr *t;
	t=bst->rc;
	if (t->lc!=NULL) bst->rn=(t->lc->ln)+(t->lc->rn)+1;
	else bst->rn=0;
	bst->rc=t->lc;
	t->lc=bst;
	t->ln=(bst->ln)+(bst->rn)+1;
	bst=t;
}

void right_rotate(ptr *&bst){
	ptr *t;
	t=bst->lc;
	if (t->rc!=NULL) bst->ln=(t->rc->ln)+(t->rc->rn)+1;
	else bst->ln=0;
	bst->lc=t->rc;
	t->rc=bst;
	t->rn=(bst->ln)+(bst->rn)+1;
	bst=t;
}


void insert(ptr *&bst,long x){
	if (bst==NULL){
		bst=new ptr;
		bst->lc=NULL; bst->rc=NULL;
		bst->data=x; bst->rp=rand();
		bst->ln=0; bst->rn=0;
		return;
	}
	if (x<=bst->data){
		insert(bst->lc,x);
		if ((bst->lc->rp)<(bst->rp)) right_rotate(bst);
	}
	else {
		insert(bst->rc,x);
		if ((bst->rc->rp)<(bst->rp)) left_rotate(bst);
	}
}

void delete_(ptr *&bst,long x){
	if (bst==NULL) return;
	if (x<bst->data){
		bst->ln--;
		delete_(bst->lc,x);
		return;
	}
	if (x>bst->data){
		bst->rn--;
		delete_(bst->rc,x);
		return;
	}
	if (bst->lc==NULL && bst->rc==NULL){
		free(bst);
		bst=NULL;
		return;
	}
	if (bst->lc!=NULL && bst->rc!=NULL){
		if ((bst->lc->rp)<(bst->rc->rp)){
			right_rotate(bst);
			bst->rn--;
			delete_(bst->rc,x);
		}
		else {
			left_rotate(bst);
			bst->ln--;
			delete_(bst->lc,x);		
		}
		return;
	}
	if (bst->lc!=NULL){
		right_rotate(bst);
		bst->rn--;
		delete_(bst->rc,x);
		return;
	}
	if (bst->rc!=NULL){
		left_rotate(bst);
		bst->ln--;
		delete_(bst->lc,x);
		return;
	}
}

void search(ptr *bst){
	if (bst==NULL) return;
	search(bst->lc);
	cout<<bst->data<<" ";
	search(bst->rc);
}

int main(){
	freopen("output.txt","w",stdout);
	ptr *bst;
	long i;
	bst=NULL; srand(time(NULL));
	for (i=1;i<=100000;i++) insert(bst,i);
	for (i=1;i<=1000;i++) delete_(bst,i);
	search(bst);
	return 0;
}