前置知識：二叉排序樹，堆，
應用場景：平衡樹，
〇、匯入
1. 二叉排序樹
我們都知道，二叉排序樹就是滿足“\(lch<now<rch\)”（左兒子小于根節點，右兒子大于根節點）的二叉樹，一般情況下插入、洗掉和搜索的時間復雜度都為 \(\Theta(\log n)\) ，非常快，但在特殊情況下，二叉排序樹可能會退化成鏈，時間復雜度也會變為 \(\Theta(n)\) ，只有當二叉排序樹平衡時速度最優，
2. 堆
堆也很簡單，就是根節點大于子節點的完全二叉樹，
3. 平衡樹
當二叉排序樹退化成鏈時速度會大打折扣，因此很多毒瘤出題者都喜歡卡它，但是既然能有這種題目，那么肯定就有能解決的方法，當然也不排除出題者自己都沒有做出來，二叉排序樹平衡時時間復雜度為 \(\Theta(\log n)\) ，所以，若要保證二叉排序樹的最大時間復雜度為 \(\Theta(\log n)\) ，就要保證該二叉排序樹平衡，這就是是平衡樹，
平衡樹有很多種，本文就不再贅述，僅討論 Treap，
4. Treap
二叉排序樹和堆都是二叉樹，既然堆就是完全二叉樹，何不利用它這個性質來保證二叉排序樹平衡呢？
于是 Tree(二叉排序樹)+Heap(堆)=Treap ，Treap 橫空出世！
一、操作&實作
1. 存盤
這里我定義了一個結構體 Treap 來封裝，然后再 Treap 內又定義了結構體 node ，表示節點，
struct Treap
{
struct node
{
int val,size,times;
unsigned rd;
node *ch[2];
}e[100005],*root,*cnt;
};
解讀：
Treap：表示Treap，node：表示節點，val：表示該節點所儲存的數值，size：表示以該節點為根的子樹的大小（節點總數），times：表示該節點的數值的存在數量，rd：隨機優先值，ch：指向子節點的指標，ch[0]：指向左兒子的指標，ch[1]：指向右兒子的指標，
e：儲存所有節點，root：指向根節點的指標，cnt：指向最后一個插入的節點的指標，
如果沒能看懂各變數的作用也沒有關系，在后面的操作中會為您一一解答，
2. 操作
2-0 node 的操作
2-0-1 建構式
node(){}
// 插入節點時用
node(const int &x){val=x,size=times=1,rd=rand(),ch[0]=ch[1]=NULL;}
優化
C++ 自帶的 rand 函式速度較慢，我們可以自己寫一個 mrand 函式來取代：
inline unsigned mrand()
{
static unsigned long long tr=431322;
return unsigned(tr=(tr*76717)%0x100000000);
}
大家可能 static 用得較少，這里就不闡述原理了，感興趣的可以自行百度，
然后建構式如下：
node(){}
// 插入節點時用
node(const int &x){val=x,size=times=1,rd=mrand(),ch[0]=ch[1]=NULL;}
2-0-2 更新節點資訊
不解釋：
inline void pushup()
{
size=times;
if(ch[0]) size+=ch[0]->size;
if(ch[1]) size+=ch[1]->size;
}
現在 node 實作如下：
struct node
{
int val,size,times;
unsigned rd;
node *ch[2];
node(){}
node(const int &x){val=x,size=times=1,rd=mrand(),ch[0]=ch[1]=NULL;}
inline void pushup()
{
size=times;
if(ch[0]) size+=ch[0]->size;
if(ch[1]) size+=ch[1]->size;
}
};
下面實作操作的函式均為 Treap 的成員函式，
附：除錯函式，輸出當前樹的詳細資訊：
// now 表示所操作子樹的根節點指標參考，indent 表示當前縮進長度
void output(node *&now,const int &indent)
{
putchar('>'),putchar(' ');
for(int i=0;i<indent;++i) putchar('|'),putchar(' ');
if(!now)
{
puts("NULL");
return;
}
// 輸出當前節點的詳細資訊，可以更改
printf("%ld:%d %d,%d %u\n",now-e,now->val,now->size,now->times,now->rd);
output(now->ch[0],indent+1);
output(now->ch[1],indent+1);
}
// 初始函式（方便呼叫）
inline void output(){output(root,0);}
2-1 旋轉
旋轉是很多平衡樹常見的操作，分為左旋和右旋，
左旋的操作如下：
右旋的操作與此類似，僅方向不同，事實上，右圖中的樹右旋后即可得到左圖，
實作的代碼也很簡單：
// now 表示所操作子樹的根節點指標參考，d 表示旋轉方向（0 表示右旋，1 表示左旋）
// 這里 now 為參考型別，便于更改，
inline void rotate(node *&now,const bool &d)
{
node *tmp=now->ch[d]; // tmp 指向將成為新的根節點的節點
now->ch[d]=tmp->ch[!d];
tmp->ch[!d]=now;
tmp->pushup(),now->pushup(); // 更新節點資訊
now=tmp; // tmp 指向的節點成為新的根節點
}
那么為什么要旋轉呢？因為每個節點都會有一個隨機優先值，而 Treap 的每個節點的優先值都比其子節點的大，利用堆的思想，使得 Treap 相對平衡，
2-2 插入值為 \(x\) 的節點
Treap 的插入其實就是在二叉排序樹的插入的基礎上通過旋轉保證 Treap 堆的性質，
// now 表示指向當前節點的指標的參考，x 表示要插入的值
// 這里 now 為參考型別，便于更改，
void insert(node *&now,const int &x)
{
// 如果為空指標
if(!now)
{
*(now=++cnt)=x; // 插入新節點
return;
}
++(now->size); // 因為新節點在以 now 指向的節點為根節點的子樹內，所以當前子樹的節點數+1
// 如果當前節點的數值不等于 x
if(now->val!=x)
{
bool d=now->val<x; // d 為插入的方向（0 為左，1 為右）
insert(now->ch[d],x);
// 如果當前節點的子節點的優先值大于當前節點的優先值（即不符合堆的性質）
if(now->ch[d]->rd>now->rd) rotate(now,d); // 旋轉以維護堆的性質
}
// 否則說明當前節點的數值等于 x
else ++(now->times); // 當前節點的數值的存在數量+1
now->pushup(); // 更新當前節點（之前我沒有加上，導致我調了好久的 BUG）
}
// 初始函式（方便呼叫）
inline void insert(const int &x){insert(root,x);}
2-3 洗掉值為 \(x\) 的節點
首先找到要洗掉的節點，然后通過旋轉將其下移，直到其沒有子節點時之間再將其直接洗掉，
// now 表示指向當前節點的指標的參考，x 表示要洗掉的值
// 這里 now 為參考型別，便于更改，
void remove(node *&now,const int &x)
{
// 如果當前節點不為要洗掉的節點
if(now->val!=x) remove(now->ch[now->val<x],x); // 繼續向下尋找
// 否則說明要洗掉當前節點
// 如果當前節點有左兒子并且左兒子的優先值大于右兒子的優先值
// 則右旋使左兒子代替被洗掉的節點的位置
else if(now->ch[0] && (!now->ch[1] || now->ch[0]->rd>now->ch[1]->rd)) rotate(now,0),remove(now->ch[1],x);
// 否則如果當前節點有右兒子
// 則左旋使右兒子代替被洗掉的節點的位置
else if(now->ch[1]) rotate(now,1),remove(now->ch[0],x);
// 否則說明當前節點沒有子節點
else
{
--(now->size);
// 如果該節點的存在數量清零了
if(!--(now->times)) now=NULL; // 直接洗掉
return;
}
now->pushup();// 更新當前節點
}
// 初始函式（方便呼叫）
inline void remove(const int &x){remove(root,x);}
2-4 查詢數值為 \(x\) 的節點的排名
這個與二叉排序樹的操作一樣，
// now 表示指向當前節點的指標的參考，x 表示要查詢的值
int getrank(node *&now,const int &x)
{
// 如果為空指標，說明改數不存在于樹中
if(!now) return 0; // 直接回傳 0
// 如果當前節點的值大于 x
if(now->val>x) return getrank(now->ch[0],x); // 繼續搜索左子樹
// 如果當前節點的值小于 x
// 繼續搜索右子樹，回傳值增加左子樹節點數+當前節點存在數量
if(now->val<x) return getrank(now->ch[1],x)+(now->ch[0]?now->ch[0]->size:0)+now->times;
// 否則說明當前節點的值等于 x
return (now->ch[0]?now->ch[0]->size:0)+1; // 回傳左子樹節點數+1
}
// 初始函式（方便呼叫）
inline int getrank(const int &x){return getrank(root,x);}
2-5 查詢排名為 \(x\) 的節點的數值
// now 表示指向當前節點的指標的參考，x 表示要查詢的排名
int getval(node *&now,const int x)
{
static int tmp; // 臨時變數，用于儲存左子樹的節點數+當前節點存在數量，為了節省空間就使用靜態變數了
// 如果當前節點有左兒子且左子樹的節點數不小于 x
// 繼續搜索左子樹
if(now->ch[0] && now->ch[0]->size>=x) return getval(now->ch[0],x);
// 否則如果當前節點有右兒子且左子樹的節點數+當前節點存在數量小于 x
// 繼續搜索右子樹中排名為 x-tmp 的節點
if(now->ch[1] && ((tmp=(now->ch[0]?now->ch[0]->size:0)+now->times)<x)) return getval(now->ch[1],x-tmp);
// 否則說明當前節點即要查詢的節點
return now->val;// 回傳當前節點的數值
}
// 初始函式（方便呼叫）
inline int getval(const int &x){return getval(root,x);}
2-6 查詢數值為 \(x\) 的節點的前驅
// now 表示指向當前節點的指標的參考，x 表示要查詢的數值
int getprev(node *&now,const int &x)
{
// 如果為空指標
if(!now) return -0x80000000; // 回傳負無窮
// 如果當前節點的數值不小于 x
// 說明前驅在左子樹內
if(now->val>=x) return getprev(now->ch[0],x); // 搜索左子樹
// 否則說明前驅為當前節點或在右子樹內
else return max(now->val,getprev(now->ch[1],x)); // 搜索右子樹
}
// 初始函式（方便呼叫）
inline int getprev(const int &x){return getprev(root,x);}
2-7 查詢數值為 \(x\) 的節點的后繼
與查詢前驅思路相同，
// now 表示指向當前節點的指標的參考，x 表示要查詢的數值
int getnext(node *&now,const int &x)
{
// 如果為空指標
if(!now) return 0x7fffffff; // 回傳負無窮
// 如果當前節點的數值不大于 x
// 說明后繼在左子樹內
if(now->val<=x) return getnext(now->ch[1],x); // 搜索左子樹
// 否則說明后繼為當前節點或在右子樹內
else return min(now->val,getnext(now->ch[0],x)); // 搜索右子樹
}
// 初始函式（方便呼叫）
inline int getnext(const int &x){return getnext(root,x);}
二、例題
1. 洛谷 P3369 【模板】普通平衡樹
題目鏈接：https://www.luogu.com.cn/problem/P3369 ，
這是一道模板題，沒什么好說的，直接上代碼：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/73573.html
標籤：其他
上一篇：小白求解opencv的StereoBM和StereoSGBM不能使用的問題。
下一篇：跳表