帶旋Treap

• 二叉查找樹BST(Binary Search Tree)定義
• Treap定義
• 模板合集（均為$O(logn)$）
• • push_up模板
  • 旋轉模板
  • 插入模板
  • 刪除模板
  • 查找前驅模板
  • 查找后驅模板
  • 查找鍵值key模板
  • 查找節點的修正值rank模板
• PS：rd的比較問題
• 例題：普通平衡樹
• • 題目
  • 代碼實現

真的太難了，剛開始是直接用模板不斷A題，其實自己根本不是很理解，于是今天放棄了刷題時間，理解并背誦了這個模板，寫了這篇blog

二叉查找樹BST(Binary Search Tree)定義

二叉查找樹(Binary Search Tree)是基于插入思想的一種在線的排序數據結構，它又叫二叉搜索樹(Binary Search Tree)、二叉排序樹(Binary Sort Tree)，簡稱BST

這種數據結構的基本思想是在二叉樹的基礎上，規定一定的順序，使數據可以有序地存儲

二叉查找樹運用了像二分查找一樣的查找方式，并且基于鏈式結構存儲，從而實現了高效的查找效率和完美的插入時間

---

二叉查找樹(Binary Search Tree)或者是一棵空樹，或者是具有下列性質的二叉
樹：

若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

它的左、右子樹也分別為二叉查找樹

我只是為了讓大家理解下面Treap的定義罷了

Treap定義

Treap是一種平衡樹。這個單詞的構造選取了Tree(樹)的前兩個字符和Heap(堆)的后三個字符，
Treap = Tree + Heap。
顧名思義，Treap把BST和Heap結合了起來。
它和BST一樣滿足許多優美的性質，而引入堆目的就是為了維護平衡。

---

Treap在BST的基礎上，添加了一個修正值。在滿足BST性質的基礎上，Treap節點的修正值還滿足最小堆性質 。最小堆性質可以被描述為每個子樹根節點都小于等于其子節點。

---

Treap的定義
Treap可以定義為有以下性質的二叉樹：

若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值，而且它
的根節點的修正值小于等于左子樹根節點的修正值；

若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值，而且它
的根節點的修正值小于等于右子樹根節點的修正值；

它的左、右子樹也分別為Treap。

修正值是節點在插入到Treap中時隨機生成的一個值，它與節點的值無關。

---

Treap維護平衡的原理
我們發現，BST會遇到不平衡的原因是因為有序的數據會使查找的路徑退化成鏈，
而隨機的數據使BST退化的概率是非常小的

在Treap中，修正值的引入恰恰是使樹的結構不僅僅取決于節點的值，還取決于修正值的值然而修正值的值是隨機生成的，出現有序的隨機序列是小概率事件，所以Treap的結構是趨向于隨機平衡的

---

模板合集（均為$O(logn)$）

先給明要用到的數組含義：
Size：表示節點數量也可作最后一個點編號
cnt[p]：表示編號為p，值為x在treap中插入的次數
key[p]：表示該點p的值為x
rd[p]：就是我們自己搞的修正值，用rand函數隨機生成
siz[p]：編號為p的子樹包括本身在內的節點數量即大小
son[p][2]：son[p][0]表示p的左兒子，son[p][1]表示p的右兒子

---

push_up模板

就是更新x的子樹大小，一定要多次更新，因為后面的操作總是要用到
一句話：不用白不用，能多用就多用

void push_up ( int x ) {siz[x] = siz[son[x][0]] + siz[son[x][1]] + cnt[x]; }

---

旋轉模板

為了使Treap中的節點同時滿足BST性質和小根堆性質，不可避免地要對其結構進行調整，調整方式被稱為旋轉(Rotate)
在維護Treap的過程中，只有兩種旋轉 ，分別是左旋和右旋。旋轉是相對于子樹而言的，左旋和右旋的命名體現了旋轉的一條性質1：
左旋一個子樹，會把它的根節點旋轉到根的左子樹位置，同時根節點的右子節點成為子樹的根；
右旋一個子樹，會把它的根節點旋轉到根的右子樹位置，同時根節點的左子節點成為子樹的根

如圖：

性質2：旋轉后的子樹仍然滿足BST性質

---

void rotate ( int &x, int d ) {//0左旋，1右旋 int p = son[x][!d];son[x][!d] = son[p][d];son[p][d] = x;push_up ( x );push_up ( p );x = p; }

---

插入模板

在Treap中插入元素，與在BST中插入方法相似。首先找到合適的插入位置，然后建立新的節點，存儲元素。但是要注意建立新的節點的過程中，會隨機地生成一個修正值，這個值可能會破壞堆序，因此我們要根據需要進行恰當的旋轉。具體方法如下：

從根節點開始插入；

如果要插入的值小于等于當前節點的值，在當前節點的左子樹中插入，插入后
如果左子節點的修正值小于當前節點的修正值，對當前節點進行右旋；

如果要插入的值大于當前節點的值，在當前節點的右子樹中插入，插入后如果
右子節點的修正值小于當前節點的修正值，對當前節點進行左旋；

如果當前節點為空節點，在此建立新的節點，該節點的值為要插入的值，左右
子樹為空，插入成功

void insert ( int &rt, int x ) {if ( ! rt ) {rt = ++ Size;siz[rt] = cnt[rt] = 1;key[rt] = x;rd[rt] = rand();return;}if ( key[rt] == x ) {cnt[rt] ++;siz[rt] ++;return;}int d = x > key[rt];insert ( son[rt][d], x );if ( rd[rt] < rd[son[rt][d]] )//說明是新插入的點，往另外一邊旋轉 rotate ( rt, !d );push_up ( rt ); /*如果旋轉了就白做了，因為旋轉中就已經更新了， 但是如果沒旋轉，這個就有用了，因為插入了以前的size就是錯的*/ }

---

刪除模板

Treap的刪除因為要維護堆序，比較好的方法是利用旋轉的方法把要刪除的結點旋轉到葉結點位置，再做刪除操作。

情況一，該節點為葉節點，則該節點是可以直接刪除的節點。若該節點有非空子節點，用非空子節點代替該節點的，否則用空節點代替該節點，然后刪除該節點。

情況二，該節點有兩個非空子節點。我們的策略是通過旋轉，使該節點變為可以直接刪除的節點。如果該節點的左子節點的修正值小于右子節點的修正值，右旋該節點，使該節點降為右子樹的根節點，然后訪問右子樹的根節點，繼續討論；反之，左旋該節點，使該節點降為左子樹的根節點，然后訪問左子樹的根節點，繼續討論，直到變成可以直接刪除的節點

---

例如：要刪除節點6，找到節點6，發現6有兩個兒子，但是右兒子的修正值小于左兒子，選擇左旋

接著發現6只剩下一個兒子了，就直接右旋讓左兒子代替它的位置隨后刪掉

void delet ( int &rt, int x ) {if ( ! rt )return;if ( x != key[rt] )delet ( son[rt][x > key[rt]], x );else {if ( ! son[rt][0] && ! son[rt][1] ) {cnt[rt] --;siz[rt] --;if ( ! cnt[rt] )rt = 0;}else if ( son[rt][0] && ! son[rt][1] ) {rotate ( rt, 1 );delet ( son[rt][1], x );}else if ( ! son[rt][0] && son[rt][1] ) {rotate ( rt, 0 );delet ( son[rt][0], x );}else {int d = rd[son[rt][0]] > rd[son[rt][1]];rotate ( rt, d );delet ( son[rt][d], x );}}push_up ( rt ); }

---

接下來就比較輕松了，好理解了

查找前驅模板

找前驅我們發現，其實就是一直往左兒子找，如果節點p與查找值x大小比較后要查找p的右兒子，這個右兒子就是x的一個前驅但不一定是最接近的，所以需要比較并繼續往下找，掘地三尺

int pre ( int rt, int x ) {if ( ! rt )return -INF;if ( key[rt] >= x )return pre ( son[rt][0], x );elsereturn max ( key[rt], pre ( son[rt][1], x ) ); }

---

查找后驅模板

找后驅我們發現與前驅相似，其實就是一直往右兒子找，如果節點p與查找值x大小比較后要查找p的左兒子，這個左兒子就是x的一個前驅但不一定是最接近的，所以需要比較

int suf ( int rt, int x ) {if ( ! rt )return INF;if ( key[rt] <= x )return suf ( son[rt][1], x );elsereturn min ( key[rt], suf ( son[rt][0], x ) ); }

---

查找鍵值key模板

就是與siz子樹個數比較，看屬于哪個部分

int find ( int rt, int x ) {if ( ! rt )return 0;if ( siz[son[rt][0]] >= x )return find ( son[rt][0], x );else if ( siz[son[rt][0]] + cnt[rt] < x )return find ( son[rt][1], x - cnt[rt] - siz[son[rt][0]] );elsereturn key[rt]; }

---

查找節點的修正值rank模板

和find差不多的思想，應該很好理解的

int search_rank ( int rt, int x ) {if ( ! rt )return 0;if ( key[rt] == x )return siz[son[rt][0]] + 1;if ( key[rt] < x )return siz[son[rt][0]] + cnt[rt] + search_rank ( son[rt][1], x );return search_rank ( son[rt][0], x ); }

PS：rd的比較問題

認真的同學會發現，我在寫講解博客的時候是維護的rd從小到大，而代碼卻是寫的從大到小，其實這rd本來就是我們自己強加的修正值，所以本質是沒有太大的區別的，只需要注意對應insert和delet維護好自己鎖定的rd順序就行了

1：

insert：if ( rd[p] < rd[son[p][d]] ) delet：int d = rd[son[p][0]] > rd[son[p][1]];

2：

insert：if ( rd[p] > rd[son[p][d]] ) delet：int d = rd[son[p][0]] < rd[son[p][1]];

---

例題：普通平衡樹

題目

點擊查看題目

代碼實現

既然是入門模板題，自然是把所有的模板拼接上再加上輸入輸出即可AC，不再多說！！

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define MAXN 100005 #define INF 0x7f7f7f7f int n, Size; int siz[MAXN], cnt[MAXN], key[MAXN], rd[MAXN]; int son[MAXN][2];void push_up ( int x ) {siz[x] = siz[son[x][0]] + siz[son[x][1]] + cnt[x]; }void rotate ( int &x, int d ) {int p = son[x][!d];son[x][!d] = son[p][d];son[p][d] = x;push_up ( x );push_up ( p );x = p; }void insert ( int &rt, int x ) {if ( ! rt ) {rt = ++ Size;siz[rt] = cnt[rt] = 1;key[rt] = x;rd[rt] = rand();return;}if ( key[rt] == x ) {cnt[rt] ++;siz[rt] ++;return;}int d = x > key[rt];insert ( son[rt][d], x );if ( rd[rt] < rd[son[rt][d]] )rotate ( rt, !d );push_up ( rt ); }void delet ( int &rt, int x ) {if ( ! rt )return;if ( x != key[rt] )delet ( son[rt][x > key[rt]], x );else {if ( ! son[rt][0] && ! son[rt][1] ) {cnt[rt] --;siz[rt] --;if ( ! cnt[rt] )rt = 0;}else if ( son[rt][0] && ! son[rt][1] ) {rotate ( rt, 1 );delet ( son[rt][1], x );}else if ( ! son[rt][0] && son[rt][1] ) {rotate ( rt, 0 );delet ( son[rt][0], x );}else {int d = rd[son[rt][0]] > rd[son[rt][1]];rotate ( rt, d );delet ( son[rt][d], x );}}push_up ( rt ); }int search_rank ( int rt, int x ) {if ( ! rt )return 0;if ( key[rt] == x )return siz[son[rt][0]] + 1;if ( key[rt] < x )return siz[son[rt][0]] + cnt[rt] + search_rank ( son[rt][1], x );return search_rank ( son[rt][0], x ); }int find ( int rt, int x ) {if ( ! rt )return 0;if ( siz[son[rt][0]] >= x )return find ( son[rt][0], x );else if ( siz[son[rt][0]] + cnt[rt] < x )return find ( son[rt][1], x - cnt[rt] - siz[son[rt][0]] );elsereturn key[rt]; }int pre ( int rt, int x ) {if ( ! rt )return -INF;if ( key[rt] >= x )return pre ( son[rt][0], x );elsereturn max ( key[rt], pre ( son[rt][1], x ) ); }int suf ( int rt, int x ) {if ( ! rt )return INF;if ( key[rt] <= x )return suf ( son[rt][1], x );elsereturn min ( key[rt], suf ( son[rt][0], x ) ); }int main() {scanf ( "%d", &n );int root = 0;while ( n -- ) {int opt, x;scanf ( "%d %d", &opt, &x );switch ( opt ) {case 1 : insert ( root, x );break;case 2 : delet ( root, x );break;case 3 : printf ( "%d\n", search_rank ( root, x ) );break;case 4 : printf ( "%d\n", find ( root, x ) );break;case 5 : printf ( "%d\n", pre ( root, x ) );break;case 6 : printf ( "%d\n", suf ( root, x ) );break;}}return 0; }

如果有任何問題歡迎提出，bye，讓我們與非旋treap不見不散

總結

以上是生活随笔為你收集整理的带旋treap概念及模板，带例题：普通平衡树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。