題目鏈接：洛谷 P3369 【模板】普通平衡樹.
這只是一篇用來存代碼的博客。平衡樹使用無旋Treap實現。
將保存不同語言（偏競賽風格）的代碼作為對比。

10多年的臺州網站建設經驗，針對設計、前端、開發(fā)、售后、文案、推廣等六對一服務，響應快，48小時及時工作處理。全網整合營銷推廣的優(yōu)勢是能夠根據用戶設備顯示端的尺寸不同，自動調整臺州建站的顯示方式，使網站能夠適用不同顯示終端，在瀏覽器中調整網站的寬度，無論在任何一種瀏覽器上瀏覽網站，都能展現優(yōu)雅布局與設計，從而大程度地提升瀏覽體驗。成都創(chuàng)新互聯公司從事“臺州網站設計”,“臺州網站推廣”以來，每個客戶項目都認真落實執(zhí)行。文章目錄

• • • C++ 11
    • Python 3.6
    • Java 8

C++ 11

#include#include#include#includestruct node{int val,rk,siz;
	node *ls,*rs;
	node(int val=0):val(val){rk=rand();siz=1;ls=rs=NULL;}
	void upd(){siz=1;
		if(ls!=NULL)
			siz+=ls->siz;
		if(rs!=NULL)
			siz+=rs->siz;
	}
}*rt;

void split(node *o,node *&a,node *&b,const int &v){if(o==NULL){a=b=NULL;
		return;
	}
	if(o->val<=v){a=o;
		split(o->rs,a->rs,b,v);
	}
	else{b=o;
		split(o->ls,a,b->ls,v);
	}
	o->upd();
}
void merge(node *&o,node *a,node *b){if(a==NULL){o=b;
		return;
	}
	if(b==NULL){o=a;
		return;
	}
	if(a->rkrk){o=a;
		merge(o->rs,a->rs,b);
	}
	else{o=b;
		merge(o->ls,a,b->ls);
	}
	o->upd();
}
void insert(node *&o,int v){node *l,*r,*u=new node(v);
	split(o,l,r,v);
	merge(l,l,u);
	merge(o,l,r);
}
void erase(node *&o,int v){node *l,*r,*u;
	split(o,l,r,v);
	split(l,l,u,v-1);
	if(u!=NULL){node *t=u;
		merge(u,u->ls,u->rs);
		delete t;
	}
	merge(l,l,u);
	merge(o,l,r);
}
int find_by_order(const node *o,int k){if(o==NULL)
		return -1;
	int lsiz=0;
	if(o->ls!=NULL)
		lsiz=o->ls->siz;
	if(k==lsiz+1)
		return o->val;
	if(k<=lsiz)
		return find_by_order(o->ls,k);
	else
		return find_by_order(o->rs,k-lsiz-1);
}
int order_of_key(node *&o,int v){node *l,*r;
	split(o,l,r,v-1);
	int res;
	if(l==NULL)
		res=1;
	else
		res=l->siz+1;
	merge(o,l,r);
	return res;
}
int prev_val(node *&o,int v){node *l,*r;
	split(o,l,r,v-1);
	if(l==NULL)
		return -1;
	int res=find_by_order(l,l->siz);
	merge(o,l,r);
	return res;
}
int next_val(node *&o,int v){node *l,*r;
	split(o,l,r,v);
	if(r==NULL)
		return -1;
	int res=find_by_order(r,1);
	merge(o,l,r);
	return res;
}

int main(){srand(100000);
	int T;scanf("%d",&T);
	while(T--){int opt,x;scanf("%d%d",&opt,&x);
		if(opt==1)
			insert(rt,x);
		else if(opt==2)
			erase(rt,x);
		else if(opt==3)
			printf("%d\n",order_of_key(rt,x));
		else if(opt==4)
			printf("%d\n",find_by_order(rt,x));
		else if(opt==5)
			printf("%d\n",prev_val(rt,x));
		else
			printf("%d\n",next_val(rt,x));
	}
	return 0;
}

Python 3.6

from random import random

class treap:
	class node:
		def __init__(self,val=0,ls=None,rs=None)->None:
			self.val=val
			self.key=random()
			self.ls=ls
			self.rs=rs
			self.siz=1
		def upd(self):
			self.siz=1
			if self.ls:
				self.siz+=self.ls.siz
			if self.rs:
				self.siz+=self.rs.siz
	def __init__(self)->None:
		self.root=None
	def __merge(self,l,r)->None:
		if not l:
			return r
		if not r:
			return l
		if l.keyNone:
		if not o:
			return None,None
		if o.val<=v:
			o.rs,tr=self.__split(o.rs,v)
			o.upd()
			return o,tr
		else:
			tr,o.ls=self.__split(o.ls,v)
			o.upd()
			return tr,o
	def insert(self,v)->None:
		u=self.node(val=v)
		l,r=self.__split(self.root,v)
		l=self.__merge(l,u)
		self.root=self.__merge(l,r)
	def erase(self,v)->bool:
		l,r=self.__split(self.root,v)
		l,u=self.__split(l,v-1)
		if u==None:
			self.root=self.__merge(l,r)
			return False
		u=self.__merge(u.ls,u.rs)
		l=self.__merge(l,u)
		self.root=self.__merge(l,r)
		return True
	def __kth(self,o,v):
		if o==None:
			return None
		lsiz=0
		if o.ls:
			lsiz=o.ls.siz
		if v<=lsiz:
			return self.__kth(o.ls,v)
		elif v==lsiz+1:
			return o.val
		else:
			return self.__kth(o.rs,v-lsiz-1)
	def kth(self,v):
		return self.__kth(self.root,v)
	def rank(self,v):
		l,r=self.__split(self.root,v-1)
		res=1
		if l:
			res+=l.siz
		self.root=self.__merge(l,r)
		return res
	def prev(self,v):
		l,r=self.__split(self.root,v-1)
		if l==None:
			return None
		res=self.__kth(l,l.siz)
		self.root=self.__merge(l,r)
		return res
	def next(self,v):
		l,r=self.__split(self.root,v)
		if r==None:
			return None
		res=self.__kth(r,1)
		self.root=self.__merge(l,r)
		return res

if __name__=="__main__":
	T=int(input())
	tr=treap()
	opt=[None,tr.insert,tr.erase,tr.rank,tr.kth,tr.prev,tr.next]
	for i in range(T):
		expr=list(map(int,input().split()))
		if expr[0]>=3:
			print(opt[expr[0]](expr[1]))
		else:
			opt[expr[0]](expr[1])

Java 8

咕咕咕。

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

文章名稱：數據結構8——無旋Treap-創(chuàng)新互聯
當前鏈接：http://www.rwnh.cn/article24/dspice.html

成都網站建設公司_創(chuàng)新互聯，為您提供軟件開發(fā)、自適應網站、動態(tài)網站、面包屑導航、網站內鏈、網頁設計公司

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯