<i id="yupd0"></i>
  • <i id="yupd0"></i>
  • <thead id="yupd0"></thead>
    <blockquote id="yupd0"></blockquote>
    <i id="yupd0"></i>
  • 碼迷,www.greeshyz.com
    首頁 > 其他好文 > 詳細

    平衡樹之Treap

    時間:2020-07-21 23:10:24      閱讀:17      評論:0      收藏:0      [點我收藏+]

    標簽:合并   有一個   else   簡單   隨機   這一   root   多個   key   

    二叉搜索樹

    性質:一個節點x左子樹所有點的關鍵字都比x的關鍵字小,右子樹所有點的關鍵字都比x的關鍵字大

    treap

    “樹堆” “Tree+Heap”

    性質:每個點隨機分配一個權值,使treap同時滿足堆性質和二叉搜索樹性質

    復雜度:期望O(logn)

    設每個節點的關鍵字是key,隨機權值是rand

    如果v是u的左兒子,則key[v]<key[u]

    如果v是u的右兒子,則key[v]>key[u]

    如果v是u的子節點,則rand[u]>rand[v]

    treap維護權值的時候一般會把相同的權值放在同一個節點上

    所以一個treap節點需要維護以下信息:

    1.左右兒子

    2.關鍵字

    3.關鍵字出現次數

    4.堆隨機值

    5.節點大小(即子樹大小)

    旋轉

    平衡二叉搜索樹主要通過旋轉來保持樹的平衡,即保證復雜度

    旋轉有單旋和雙旋,treap只需要單旋,這一點比較簡單

    void lturn(int &k)//treap的旋轉 
    {
    	int t=tr[k].r;
    	tr[k].r=tr[t].l;
    	tr[t].l=k;
    	tr[t].size=tr[k].size;
    	update(k);
    	k=t;
    }
    
    void rturn(int &k)
    {
    	int t=tr[k].l;
    	tr[k].l=tr[t].r;
    	tr[t].r=k;
    	tr[t].size=tr[k].size;
    	update(k);
    	k=t;
    }
    

    treap的插入

    先給這個節點分配一個隨機的堆權值

    然后把這個節點按照BST的規則插入到一個葉子上:

    從根節點開始,逐個判斷當前節點的值與插入值的大小關系。如果插入值小于當前節點值,則遞歸至左兒子;大于則遞歸至右兒子;

    然后通過旋轉來調整,使得treap滿足堆性質

    void insert(int &k,int x)//treap的插入 
    {
    	if(!k)
    	{
    		size++;
    		k=size;
    		tr[k].size=tr[k].w=1;
    		tr[k].v=x;
    		tr[k].rnd=rand();
    		return ;
    	}
    	tr[k].size++;
    	if(tr[k].v==x)
    		tr[k].w++;
    	else if(x>tr[k].v)
    	{
    		insert(tr[k].r,x);
    		if(tr[tr[k].r].rnd<tr[k].rnd)
    			lturn(k);
    	}
    	else
    	{
    		insert(tr[k].l,x);
    		if(tr[tr[k].l].rnd<tr[k].rnd)
    			rturn(k);
    	}
    }
    

    treap的刪除

    和普通的BST刪除一樣:

    如果插入值小于當前節點值,則遞歸至左兒子;大于則遞歸至右兒子

    若當前節點數值的出現次數大于1,則減一(通常將同一個權值縮掉)

    若當前節點數值的出現次數等于1:

    若當前節點沒有左兒子與右兒子,則直接刪除該節點(置為0);

    若當前節點沒有左兒子或右兒子,則將左兒子或右兒子替代該節點

    若當前節點有左兒子與右兒子,則不斷旋轉當前節點,并走到當前節點新的對應位置,直到沒有左兒子和右兒子為止。

    void del(int &k,int x)//treap的刪除
    {
    	if(!k)
    		return;
    	if(tr[k]==x)
    	{
    		if(tr[k].w>1)//若不止相同值的個數有多個,刪去一個 
    		{
    			tr[k].w--;
    			tr[k].size--;
    			return ;	
    		}
    		if(tr[k].l*tr[k].r==0)//有一個兒子為空 
    			k=tr[k].l+tr[k].r;
    		else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd)
    			rturn(k),del(k,x);
    		else
    			lturn(k),del(k,x);
    	}
    	else if(x>tr[k].v)
    		tr[k].size--,del(tr[k].r,x);
    	else
    		tr[k].size--,del(tr[k].l,x);	
    } 
    

    treap的查詢

    遞歸到葉子節點,一路維護信息即可

    int query_rank(int k,int x)//treap的查詢
    {
    	if(!k)
    		return 0;
    	if(tr[k].v==x)	
    		return tr[tr[k].l].size+1;
    	else if(x>tr[k].v)
    		return tr[tr[k].l].size+tr[k].w+query_rank(tr[k].r+x);
    	else
    		return query_rank(tr[k].l,x); 
    } 
    
    int query_num(int k,int x)
    {
    	if(!k)
    		return 0;
    	if(x<=tr[tr[k].l].size)
    		return query_num(tr[k].l,x);
    	else if(x>tr[tr[k].l].size+tr[k].w)
    		return query_num(tr[k].r,x-tr[tr[k].l].size-tr[k].w);
    	else
    		return tr[k].v;
    }
    
    

    treap還可以支持維護序列時的分裂合并,這里不詳細講了

    #include<iostream>
    #include<cstdio>
    
    struct data()
    {
    	int l;
    	int r;
    	int v;
    	int size;
    	int rnd;
    	int w;
    }tr[100005];
    
    int n,size,root,ans;
    
    void update(int k)//更新節點信息 
    {
    	tr[k].size=tr[tr[k].l].size+tr[tr[k].r].size+tr[k].w;
    }
    
    void lturn(int &k)//treap的旋轉 
    {
    	int t=tr[k].r;
    	tr[k].r=tr[t].l;
    	tr[t].l=k;
    	tr[t].size=tr[k].size;
    	update(k);
    	k=t;
    }
    
    void rturn(int &k)
    {
    	int t=tr[k].l;
    	tr[k].l=tr[t].r;
    	tr[t].r=k;
    	tr[t].size=tr[k].size;
    	update(k);
    	k=t;
    }
    
    void insert(int &k,int x)//treap的插入 
    {
    	if(!k)
    	{
    		size++;
    		k=size;
    		tr[k].size=tr[k].w=1;
    		tr[k].v=x;
    		tr[k].rnd=rand();
    		return ;
    	}
    	tr[k].size++;
    	if(tr[k].v==x)
    		tr[k].w++;
    	else if(x>tr[k].v)
    	{
    		insert(tr[k].r,x);
    		if(tr[tr[k].r].rnd<tr[k].rnd)
    			lturn(k);
    	}
    	else
    	{
    		insert(tr[k].l,x);
    		if(tr[tr[k].l].rnd<tr[k].rnd)
    			rturn(k);
    	}
    }
    
    void del(int &k,int x)//treap的刪除
    {
    	if(!k)
    		return;
    	if(tr[k]==x)
    	{
    		if(tr[k].w>1)//若不止相同值的個數有多個,刪去一個 
    		{
    			tr[k].w--;
    			tr[k].size--;
    			return ;	
    		}
    		if(tr[k].l*tr[k].r==0)//有一個兒子為空 
    			k=tr[k].l+tr[k].r;
    		else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd)
    			rturn(k),del(k,x);
    		else
    			lturn(k),del(k,x);
    	}
    	else if(x>tr[k].v)
    		tr[k].size--,del(tr[k].r,x);
    	else
    		tr[k].size--,del(tr[k].l,x);	
    } 
    
    int query_rank(int k,int x)//treap的查詢
    {
    	if(!k)
    		return 0;
    	if(tr[k].v==x)	
    		return tr[tr[k].l].size+1;
    	else if(x>tr[k].v)
    		return tr[tr[k].l].size+tr[k].w+query_rank(tr[k].r+x);
    	else
    		return query_rank(tr[k].l,x); 
    } 
    
    int query_num(int k,int x)
    {
    	if(!k)
    		return 0;
    	if(x<=tr[tr[k].l].size)
    		return query_num(tr[k].l,x);
    	else if(x>tr[tr[k].l].size+tr[k].w)
    		return query_num(tr[k].r,x-tr[tr[k].l].size-tr[k].w);
    	else
    		return tr[k].v;
    }

    平衡樹之Treap

    標簽:合并   有一個   else   簡單   隨機   這一   root   多個   key   

    原文地址:https://www.cnblogs.com/liumengliang/p/13357109.html

    (0)
    (0)
       
    舉報
    評論 一句話評論(0
    登錄后才能評論!
    迷上了代碼!
    91色国产论坛,久草99福利资源,青青草在线华人,99热在线视频观看免费,青青草a片免费看,青青草av视频导航,香蕉网站伊人大香蕉 青青碰人青青草免费 国产自拍偷拍在线播放 青青草华人在线av 伊人影院在线大香 无码大香蕉网伊人色 久久大香蕉视频网 青草精品资源在线 伊人大香蕉在线精品 97资源总站久久爱视频 自拍中文字幕 青青草手机在线视频 青青草久久爱大香蕉 国产青青草自拍 伊人大香蕉在线精品 97资源总站久久爱视频 自拍中文字幕 av图片在线看 久草视频福利免费资源站 自拍国产视频在线 www.琪琪色 爱色影爱色搞搞 97资源库 大香萑a久草视频 久草在线福利资站 青青草成人在线免费视频 久久精品国can视频在热 99热国产情侣偷拍 国产自拍 在线 凹凸分类视频97免费 av啪啪中文网站 青青草91自拍视频 奇米影视第四色 国产无限制自拍 大香蕉伊人精品在线 久久手机看片国产免费 无码大香蕉网伊人色 亚洲激情色 久草99福利资源 狼人色终合网站 91色国产色去色 2019奇米777奇米网 久久草妹妹色 米奇影院888奇米色 青青青草成人免费现看 超碰自拍 在线99热这里精品 色琪琪永久无码 伊人大香蕉成人视频综合 国产自拍视频在线 大香蕉伊人久操在线 青青草久草热久久草 偷拍自拍第四色 奇米网电影网 超碰99久久天天拍日日操 天天拍天天拍久草片 激情图片,激情小说 超碰碰av大香蕉伊人 久草97大香蕉伊人 美女伊人色情香蕉网站 青青草华人免费视频在线 大香蕉伊人久草视频 奇米网在线手机在线 青草七次郞视频观看 青青草公开在线观看 狠狠夜夜干大香蕉伊人 777奇米网 日逼视频网站 欧美人和动物XXX 大香蕉色 欧美 国产 奇米影院首页 大香蕉伊人久久爱在线 青青青草免费手机播放 国产青青草 欧美一级黑寡妇夜夜干 啪啪 国产精品 东方aⅴ在线看 手机看A片 777米奇色狠狠俺去啦 香蕉网站伊人中文字幕 久操在线新免费视频 伊人影院在线大香 大香蕉成人伊人在线视频 青青草成人在线视频观看 91国产自拍偷拍视频 青青草色爱久久 精品国产自拍 小色狗 琪琪热热色无码 影音先锋大香蕉久草资源 小明视频看看成人免费 俺去了色网婷婷色 久久色情片 超碰在线青青草 超碰视频起碰视频 国产偷拍自拍影音先锋 小明视频看看成人免费 俺去了色网婷婷色 久久色情片 超碰在线青青草 超碰视频起碰视频 国产偷拍自拍影音先锋 老鸭窝在线视频 www.奇米在线四色 老版本日本怡春院 强奸乱伦在线观看 青青草在观视频 色琪琪在线视频原网 欧美色色大香焦 欧美色热图 亚洲香蕉手机在线观看视频 偷拍偷窥自拍网站 超91在线观看 最新奇米奇色777在线 婷婷网站 微拍秒拍福利视频 自拍在线 精品视频 欧美情色无码在线 久草激情视频 午夜高清影院在线观看 第四色青娱乐奇米影视 青青草在线综合 99热这里有精品 自拍偷拍影音先锋 国产自拍 先锋影音 成人在线视频97 久草在线免费观看大香蕉 99er久久国产精品在线 精品国产在线偷拍 啪啪青青草视频 国内偷拍 亚洲 大香蕉成人手机在线 在线伊人大香蕉手机版 久草伊人久草视频 伊人久久青青草综合网 青青草手机在线视频 青青草久久爱大香蕉 国产青青草自拍 伊人大香蕉在线精品 97资源总站久久爱视频 自拍中文字幕 av图片在线看 久草视频福利免费资源站 自拍国产视频在线 www.琪琪色 爱色影爱色搞搞 97资源库 大香蕉在线视频免费观看 a片直播妹子在线视频 a.v在线视频 开心五月色婷婷免费 香蕉福利视频在线观 青青草成人+激情偷拍 青青草视频大香蕉伊人网 av啪啪中文网站 青青草91自拍视频 奇米影视第四色 国产无限制自拍 大香蕉伊人精品在线 久久手机看片国产免费 无码大香蕉网伊人色 亚洲激情色 久草99福利资源 狼人色终合网站 91色国产色去色 2019奇米777奇米网 久久草妹妹色 米奇影院888奇米色 青青青草成人免费现看 超碰自拍 在线99热这里精品 色琪琪永久无码 伊人大香蕉成人视频综合 国产自拍视频在线 大香蕉伊人久操在线 青青草久草热久久草 偷拍自拍第四色 奇米网电影网 超碰99久久天天拍日日操 天天拍天天拍久草片 激情图片,激情小说 青青草久草热久久草 偷拍自拍第四色 奇米网电影网 超碰99久久天天拍日日操 天天拍天天拍久草片 操好屌色 米奇先锋 久草 偷拍 亚洲,偷拍,自拍,精品 伊人大香蕉综合色 大香蕉久久久 成人色啪啪 大香蕉色看片 欧美自拍在线 久久色综合网站xoxo 久热草大香蕉在线视频 久久大香蕉视频网 肏逼免费视频在线 网友自拍偷拍 欧美 国产 奇米影院首页 大香蕉伊人久久爱在线 青青青草免费手机播放 国产青青草 欧美一级黑寡妇夜夜干 啪啪 国产精品 东方aⅴ在线看 手机看A片 777米奇色狠狠俺去啦 香蕉网站伊人中文字幕 久操在线新免费视频 伊人影院在线大香 大香蕉成人伊人在线视频 青青草成人在线视频观看 91国产自拍偷拍视频 青青草色爱久久 精品国产自拍 小色狗 琪琪热热色无码 影音先锋大香蕉久草资源 小明视频看看成人免费 俺去了色网婷婷色 久久色情片 超碰在线青青草 欧美激情图片 自拍超碰 久草视频在线 天天 综合色伊人网 大香蕉视频成人中文网 大香蕉伊人欧美色 久热在线播放中文字幕 青青草久草福利 欧美色色大香焦 欧美色热图 亚洲香蕉手机在线观看视频 偷拍偷窥自拍网站 超91在线观看 最新奇米奇色777在线 婷婷网站 微拍秒拍福利视频 自拍在线 精品视频 欧美情色无码在线 久草激情视频 午夜高清影院在线观看 第四色青娱乐奇米影视 青青草在线综合 99热这里有精品 自拍偷拍影音先锋 国产自拍 先锋影音 成人在线视频97 久草在线免费观看大香蕉 99er久久国产精品在线
    久久草2019在线观看 99这里有精品 大香蕉免费公开青青草 狠狠色丁香婷婷综合 国产久草福利手机在线 青青草黄色三级网站 大香蕉他也啪 青青草视频大香蕉伊人网 久久爱大香焦在线视频 日本有码视频 成人视屏 国产精品91在线 91国产自拍小视频 伊人狼人香蕉网小说 青青草香蕉草久在线 av青青操 亚洲自拍欧美 91 国产 在线 97超碰资源共享 青青草伊人大香蕉 奇米四色网 国産偷拍91 精品国产在线自拍 伊人大香蕉色琪琪影院 caoprom超碰 青青视频在线视频 开心五月婷婷色婷在线 第四色色 Caoprom超碰视频 亚洲图片欧美图色姐 天天干情色网 操妹妹干妹妹 丁香五月婷婷伊人大香蕉 国产精品自拍偷拍在线 青青青成人社区 成人av在线 碰碰视频在线免费播放 影音先锋 小说色 久久草大香蕉 亚洲情色狼人网 思思久久re热线播放 久久草超碰 播播影院私人影院 大香蕉他也啪 米奇影视 成人国产老鸭窝 伊人大香蕉久久天天啪 男人的天堂 国产精品自偷拍 很很鲁在线97