模板傳送
FHQ-Treap顧名思義就是范浩強大佬設計的一種二叉平衡樹
下面我們來講一下它的原理和代碼

結構體

對于一個節點，我們需要記錄的是

對應的值
子樹節點數
左右孩子編號
對應的隨機值

struct str{
	int val,size,l,r,key;
}fhq[100005];

看到這里有人疑惑了，這個對應的隨機值是怎么回事啊？
這里就涉及到了一個FHQ-Treap里優化的一個小技巧
我們知道，樹在最壞的情況下，會退化成一條鏈
但很顯然，出于時間復雜度上來講，我們并不希望它成為一條鏈，因為我們的遍歷是按照一層一層來遍歷的，如果退化成一條鏈就會從最優O（log n）的復雜度直接降到O( n )，所以我們就用這個隨機的值去讓這個二叉樹變得平衡，具體怎么去使用這個隨機值的請看函式merge

函式

首先，先給大家把主要使用的函式列出來，然后我們再一個一個講

void update(int x)
void split(int now,int dat,int &x,int &y)
int merge(int x,int y)
int add(int dat)
void ins(int dat)
void del(int dat)
int get_rk(int dat)
int get_num(int dat)
void get_pre(int dat)
void get_next(int dat)

看起來是不是很讓人頭暈眼花？
我們把函式要具體實作什么注釋一下：

void update(int x)//更新資料
void split(int now,int dat,int &x,int &y)//分裂
int merge(int x,int y)//合并
int add(int dat)//在樹里添加節點（實際的操作）
void ins(int dat)//節點進樹（與上一個要區分開，這個只是一個輸入的對接）
void del(int dat)//節點出樹
int get_rk(int dat)//求dat數的排名
int get_num(int dat)//求排dat名的數
void get_pre(int dat)//求前驅
void get_next(int dat)//求后繼

鋪墊的差不多了，是時候開始講了

update

update函式十分簡單，主要要求實作的是更新該節點的子樹長度，因為我們會在樹上進行其他的修改操作，長度很可能會隨之變化，所以這個函式一定是要放在第一位寫的

void update(int x){//要更新x節點
	fhq[x].size=fhq[fhq[x].l].size+fhq[fhq[x].r].size+1;
        //子樹節點數=左子樹節點數+右子樹節點數+本身；
	return ;
}

split

這個函式是FHQ-Treap的重點之一，主要實作的是把一棵樹拆成兩棵樹方便后續操作，我們先解釋一下這里的引數都是什么意思

void split(int now,int dat,int &x,int &y)
//now表示現在遍歷到了哪個節點，dat是要從哪里拆開這棵樹，x和y是拆后兩顆樹的根節點

因為x和y的值在函式里會被不停地更新，所以我們這里的&x，&y就尤為重要
第一步，根據二叉搜索樹，找到從哪里分成兩半

if(dat<fhq[now].val)//如果小，那就在now的左子樹里
	{
		y=now;//把y的值更新，縮小范圍
		split(fhq[now].l,dat,x,fhq[now].l);
	}else{//如果不小，那就在now的右子樹里
		x=now;//把x的值更新，縮小范圍
		split(fhq[now].r,dat,fhq[now].r,y);
	}

（如果看不懂的話可以自己畫個圖理解一下，本人能力有限，不會做動圖）
最后，我們就會把分裂出來的兩棵樹的根節點求出來
你以為這樣就完了嗎？還要注意幾個細節：
遞回跳出：

if(now==0){
	x=y=0;
	return ;
}

還有！你已經修改了這棵樹了，別忘了更新！！！

update(now);

merge

來到第二個重點，也是有很多人包括剛學的我非常不理解的地方————合并函式
還是先解釋引數

int merge(int x,int y)//將以x為根的樹和以y為根的樹合并

它到底是怎么用這些隨機值來保持平衡的呢？
我們來看一個問題：現在你有兩棵二叉搜索樹，并且告訴你一棵樹的根節點x一定比另一顆樹的根節點y要小，請問你能怎么組合？
聰明的你肯定會想到兩種情況：

第一種是把x插進y的左子樹里，第二種是把y插進x的右子樹里

如果把這個問題交給聰明的你的話，你一定會選擇盡可能平衡的一種做法來合并，但很可惜，計算機并沒有你那么聰明的腦子，它只會機械的執行一種操作，而這種操作執行下去就會逐漸變成一條鏈，怎么辦呢？
這時候我們的隨機值就發揮出用場了，當面對于這樣的兩難抉擇中，它就不會再去考慮x和y的值，不會去考慮這棵二叉平衡樹（因為很顯然，前者沒必要，給你的時候就知道x小y大，后者不用管，因為怎樣操作都是一棵二叉平衡樹），而是去維護堆

注意！我在這里是維護的小根堆！

如果我們x的key要小于y的key的話，根據小根堆我們就要把它合并到y的左子樹中

如果我們y的key要小于x的key的話，根據小根堆我們就要把它合并到x的右子樹中

（強迫癥滿意地笑了）
這樣，我們就通過這些小小的隨機值完美的解決了這個難題，維護了二叉搜索樹的平衡
代碼如下

if(fhq[x].key<=fhq[y].key){
		fhq[x].r=merge(fhq[x].r,y);//y插進x的右子樹
		update(x);//別忘更新！我愛更新！警鐘長鳴！這個代碼第一次的bug就是忘更新了
		return x;//回傳的是合并后的根節點
	}else{
		fhq[y].l=merge(x,fhq[y].l);//x插進y的左子樹
		update(y);//別忘更新！我愛更新！
		return y;
	}

別忘了遞回的跳出~

if(x==0||y==0) return x+y;

add

這個函式相較于上兩個來說就簡單了
還是引數

int add(int dat)//添加一個值為dat的節點，回傳該節點下標

我們只需要給它進行以下操作

fhq[++cnt].size=1;//cnt是這棵樹的總節點數
fhq[cnt].key=rand(); //取隨機值
fhq[cnt].val=dat;
return cnt;

OK力~

ins

解釋引數

void ins(int dat)//插入一個dat進樹

這里就很好玩了，我們的操作是這樣
先通過dat值把這棵樹劈成兩半，此時一半<=dat，一半>dat

split(root,dat,x,y);//root是這棵樹的根

傳回來了兩棵樹的根節點后，我們把這個節點先悄悄的加進樹里，此時相當于有三棵樹存在

z=add(dat);

然后呢，我們要當老六，把這三棵樹再組成一棵樹

root=merge(merge(x,z),y);

這樣，我們的添加節點操作就不可思議而且妙不可言的完成了！

del

與上一個函式相反，這個函式是洗掉操作

void del(int dat)//洗掉值為dat的一個節點

這個操作也很妙，集中注意力
我們先通過dat值把這棵樹劈成兩半，此時一半<=dat，一半>dat

split(root,dat,x,y);

然后和上面的思想差不多，我們再從<=dat的左樹中再劈成兩半，一半是=dat的節點，一半是其他節點

split(x,dat-1,x,z);//從左樹根節點開始通過dat-1把左樹劈成一半<=dat-1,一半=dat

然后呢，我們再把這個左樹中的其他節點與右樹一合并，一個dat就自然而然的被排擠出去了！

z=merge(fhq[z].l,fhq[z].r);//這里是重點！！！我們只需要洗掉一個dat而剩下的dat還是要再加回樹里的！
root=merge(merge(x,z),y);//三塊合并

這樣這個操作也完成啦~

get_rk

這個函式是用來求值為dat的數的排名的
操作比上兩個還要簡單，我們通過dat值把這棵樹劈成兩半，此時一半<=dat，一半>dat，然后我們直接把左子樹的節點數+1就是dat數的排名了~

split(root,dat-1,x,y);
int ans=fhq[x].size+1;
merge(x,y);//分裂完別忘了合并！
return ans;

get_num

這個函式的作用是求排名為dat的數值是多少
還是分類討論的思想，我們發現這個排dat名的數要么在當前節點的左子樹上，要么在當前節點的右子樹上，要么就是當前節點，然后我們就可以寫一個遞回或回圈來解決問題了（本人懶得寫遞回了，如果有遞回強迫癥可以自己寫一下）

int now=root;//當前遍歷到了哪個節點
while(now){
    if(fhq[fhq[now].l].size+1==dat){//就是當前節點
	    break;
	}
	else if(fhq[fhq[now].l].size>=dat)now=fhq[now].l;//在左子樹里
	else{//在右子樹里
		dat-=fhq[fhq[now].l].size+1;//注意！右子樹比左子樹都要大！所以求的時候一定要把左子樹節點數減掉！
		now=fhq[now].r;
	}
}
return fhq[now].val;//華麗回傳~

這樣就又ok了

get_pre

一個求dat前驅的函式，操作起來也很妙
我們先通過dat-1把這棵樹劈成兩半，此時一半<dat，一半>=dat
然后我們就會發現，左子樹中最大的那一個，就是dat的前驅
理解了意思，函式就好寫了

split(root,dat-1,x,y);
int now=x;
while(fhq[now].r) now=fhq[now].r;//找左子樹中最大的那一個，一定是最右的節點
cout<<fhq[now].val<<endl;
root = merge(x,y);//分裂完千萬別忘了合并！

get_next

與上面的思想相同，但是這回我們要在右子樹中找這個值：
我們先通過dat把這棵樹劈成兩半，此時一半<=dat，一半>dat
然后我們就會發現，右子樹中最大的那一個，就是dat的后繼

split(root,dat,x,y);
	int now=y;
	while(fhq[now].l) now=fhq[now].l;//找右子樹中最小的那一個，一定是最左的節點
	cout<<fhq[now].val<<endl;
    root=merge(x, y);

實作

這樣，我們就把所有的函式都捋了一遍，主函式也就好寫了，以下是完整的AC代碼

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<random>//這個里面有rand函式，必須寫！

using namespace std;

int n;
int cnt;
int root;

struct str{
	int val,key,size,l,r;
}fhq[100005];

void update(int x){
	fhq[x].size=fhq[fhq[x].l].size+fhq[fhq[x].r].size+1;
	return ;
}

void split(int now,int dat,int &x,int &y){//分裂 
	if(now==0){
		x=y=0;
		return ;
	}
	if(dat<fhq[now].val)
	{
		y=now;
		split(fhq[now].l,dat,x,fhq[now].l);
	}else{
		x=now;
		split(fhq[now].r,dat,fhq[now].r,y);
	}
	update(now);
}

int merge(int x,int y){//合并，回傳合并后的根 
	if(x==0||y==0) return x+y;
	if(fhq[x].key<=fhq[y].key){
		fhq[x].r=merge(fhq[x].r,y);
		update(x);
		return x;
	}else{
		fhq[y].l=merge(x,fhq[y].l);
		update(y);
		return y;
	}
}

int add(int dat){//增加結點 
	fhq[++cnt].size=1;
	fhq[cnt].key=rand();
	fhq[cnt].val=dat;
	return cnt;
}

void ins(int dat){//結點進樹
	int x,y,z;  
	split(root,dat,x,y);
	z=add(dat);
	root=merge(merge(x,z),y);
	return ;
}

void del(int dat){//結點出樹 
	int x,y,z; 
	split(root,dat,x,y);
	split(x,dat-1,x,z);
	z=merge(fhq[z].l,fhq[z].r);
	root=merge(merge(x,z),y);
}
int get_rk(int dat){//求dat數的排名 
	int x,y,z; 
	split(root,dat-1,x,y);
	int ans=fhq[x].size+1;
	merge(x,y);
	return ans;
} 
 
int get_num(int dat){//求排dat名的數
	int now=root;
	while(now){
        if(fhq[fhq[now].l].size+1==dat){
			break;
		}
		else if(fhq[fhq[now].l].size>=dat)now=fhq[now].l;
		else{
			dat-=fhq[fhq[now].l].size+1;
			now=fhq[now].r;
		}
	}
	return fhq[now].val;
}

void get_pre(int dat){//求前驅 
	int x,y,z; 
	split(root,dat-1,x,y);
	int now=x;
	while(fhq[now].r) now=fhq[now].r;
	cout<<fhq[now].val<<endl;
    root = merge(x,y);
}

void get_next(int dat){//求后繼 
	int x,y,z; 
	split(root,dat,x,y);
	int now=y;
	while(fhq[now].l) now=fhq[now].l;
	cout<<fhq[now].val<<endl;
    root=merge(x, y);
}

int main(){
	cin>>n;
	while(n--){
		int opt,x;
		cin>>opt>>x;
		if(opt==1) ins(x);
		else if(opt==2) del(x);
		else if(opt==3) cout<<get_rk(x)<<endl;
		else if(opt==4) cout<<get_num(x)<<endl;
		else if(opt==5) get_pre(x);
		else get_next(x);
	}
	return 0;
}

好了，看到這里，想必你已經掌握了FHQ-Treap了，我們在下一個平衡樹相見吧！

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/554255.html

標籤：其他

上一篇：p1 檔案的基本使用

下一篇：返回列表