數(shù)據(jù)結(jié)構(gòu)8——無(wú)旋Treap-創(chuàng)新互聯(lián)

題目鏈接：洛谷 P3369 【模板】普通平衡樹(shù).
這只是一篇用來(lái)存代碼的博客。平衡樹(shù)使用無(wú)旋Treap實(shí)現(xiàn)。
將保存不同語(yǔ)言（偏競(jìng)賽風(fēng)格）的代碼作為對(duì)比。

10多年的臺(tái)州網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。全網(wǎng)整合營(yíng)銷(xiāo)推廣的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整臺(tái)州建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。成都創(chuàng)新互聯(lián)公司從事“臺(tái)州網(wǎng)站設(shè)計(jì)”,“臺(tái)州網(wǎng)站推廣”以來(lái)，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(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)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)8——無(wú)旋Treap-創(chuàng)新互聯(lián)
當(dāng)前鏈接：http://muchs.cn/article24/dspice.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開(kāi)發(fā)、自適應(yīng)網(wǎng)站、動(dòng)態(tài)網(wǎng)站、面包屑導(dǎo)航、網(wǎng)站內(nèi)鏈、網(wǎng)頁(yè)設(shè)計(jì)公司

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

猜你還喜歡下面的內(nèi)容