my code stock.com

Try To Treap Short

Snippet options

Download: Download snippet as treap.c.
Copy snippet: For this you need a free my code stock.com account.
Embed code : You will find the embed code for this snippet at the end of the page, if you want to embed it into a website or a blog!

#include<cstdio>
#include<cstdlib>
using namespace std;
struct Treap_Node {
	Treap_Node *ch[2];
	int value,fix,weight,size;
	inline int lsize(){ return ch[0]?ch[0]->size:0; }
    inline int rsize(){ return ch[1]?ch[1]->size:0; }
};
typedef Treap_Node *Treap;
Treap Root;

void Rotate(Treap &x, int t) {    // t=0=left else right
	Treap y=x->ch[!t];
	x->ch[!t] = y->ch[t] , y->ch[t] = x;
	x=y , y=x->ch[t];
	y->size = y->lsize() + y->rsize() + y->weight , x->size = x->lsize() + x->rsize() + x->weight;
}


void Insert(Treap P, int x){
    if (!P){
        P = new Treap_Node;
        P->value = x;
        P->fix = rand();
        P->weight = P->size = 1;
    }
    else if (P->value == x) P->weight++;
        else{
            int wy=P->value < x;
            Insert(P->ch[wy], x);
            if (P->ch[wy] < P->value) Rotate(P, !wy);
        }
}

void Delete(Treap &P, int x) {
    int wy;
	if (P->value ==x) {
		if (P->weight>1) P->weight--; 
		else if (!P->ch[0] || !P->ch[1]) {
			Treap t=P;
			if (!P->ch[0]) P = P->ch[1]; else P = P->ch[0];
			delete t;
		}
		else wy = P->ch[0]->fix  < P->ch[1]->fix , Rotate(P, wy);	
	}
	else wy=P->value < x , Delete(P->ch[wy], x);
}

Treap FindKth(Treap P, int k) {
	if (k <= P->lsize()) return FindKth(P->ch[0], k);
	 else if (k > P->lsize() + P->weight) 
     return FindKth(P->ch[1], k - P->lsize() - P->weight);
	  else return P;
}

void DeleteKth(Treap P, int k) { delete FindKth(P, k); }

int main() {
	srand(12345);
}

Create a free my code stock.com account now.

my code stok.com is a free service, which allows you to save and manage code snippes of any kind and programming language. We provide many advantages for your daily work with code-snippets, also for your teamwork. Give it a try!

Find out more and register now

You can customize the height of iFrame-Codes as needed! You can find more infos in our API Reference for iframe Embeds.