平衡樹 Treap（樹堆）學習筆記

2022 年 1 月 29 日
筆記
學習筆記, 數據結構

調了好幾個月的 Treap 今天終於調通了，特意寫篇博客來紀念一下。

0. Treap 的含義及用途

在算法競賽中很多題目要使用二叉搜索樹維護信息。然而毒瘤數據可能讓二叉搜索樹退化成鏈，這時就需要讓二叉搜索樹保持*衡，「*衡的」二叉搜索樹自然就是「*衡樹」啦。「Treap」就是*衡樹的一種，由於它易學易寫，所以在算法競賽中很常用。

“Treap” 事英文單詞 “Tree” 和 “Heap” 的合成詞。顧名思義，它同時擁有樹和堆的性質。Treap 每個節點維護兩個權值 lev 和 val ,lev是隨機分配的，滿足堆（本文中指大根堆）性質，val 是 Treap 真正要存儲的信息，滿足二叉搜索樹的性質。像這樣：

即節點的val值大於左兒子的val值小於右兒子的val值， lev值大於它的每個兒子的lev值。

這其實是一棵笛卡爾樹。當笛卡爾樹的兩個權值都確定時，笛卡爾樹的形態是唯一的。~~容易發現，~~二叉搜索樹在數據隨機時就是趨*於*衡的，而由於 Treap 的 lev 權值隨機，也就是說 Treap 的形態隨機，所以 Treap 的*衡也就有了保證。 ~~好不靠譜啊（小聲~~

下面博主將結合代碼講解 Treap。

1. 操作

1.-1. Treap 需要維護的信息

treap_node pool[MAXN+5];//內存池
struct treap_node{
    int ls,rs;//記錄左右兒子節點編號
    int val;//treap要維護的信息
    int cnt/*treap內有多少個val，也就是val的副本數*/,siz/*當前子樹大小*/,lev/*隨機權值*/;
};
struct treap{
    int root;//存儲樹根
    treap(){
        root=nul;
    }
	void push_up(int p){//維護節點大小信息
        pool[p].siz=pool[pool[p].ls].siz+pool[pool[p].rs].siz+pool[p].cnt;
    }
}；

1.0. 新建節點、刪除節點與垃圾回收

treap_node pool[MAXN+5];//內存池
int treap_tail;
const int nul=0;
queue<int> treap_rubbish;//「垃圾站」
int new_treap_node(){//新建節點
    int res=0;
    if(treap_rubbish.empty()){
        res=++treap_tail;
    }else{
        res=treap_rubbish.front();
        treap_rubbish.pop();
    }
    pool[res].cnt=pool[res].siz=pool[res].ls=pool[res].rs=0;
    pool[res].val=0;
    pool[res].lev=rand();
    return res;
}
void delete_treap_node(int &p){//刪除節點
    treap_rubbish.push(p);//回收
    p=0;
}

博主在這裡使用了一個辣雞版的內存池。當刪除節點時，可以把廢舊的節點編號插入垃圾隊列中，這樣在下次新建節點時可以直接從垃圾隊列里薅一個出來而不用新申請，可以在一定程度上節省空間。

1.1. 旋轉

在 Treap 中，有時會出現 lev 的堆性質被破壞的現象，這時就需要用「旋轉」操作來維護堆性質的同時不破壞二叉搜索樹性質。例如這種情況：

我們可以通過「左旋」來維護它。如圖：

我們驚奇地發現，「左旋」操作在沒有破壞二叉搜索樹性質的前提下顛倒了節點A和節點B的父子關係！

「左旋」操作代碼：

void zag(int &p){//由於此操作可能更改當前子樹的根節點，所以要使用引用來確保p永遠指向當前子樹的根節點
    int tmp=pool[p].rs;
    pool[p].rs=pool[tmp].ls;
    pool[tmp].ls=p;
    push_up(p);push_up(tmp);
    p=tmp;
}

同樣的，也存在一個右旋操作，代碼如下：

void zig(int &p){
    int tmp=pool[p].ls;
    pool[p].ls=pool[tmp].rs;
    pool[tmp].rs=p;
    push_up(p);push_up(tmp);
    p=tmp;
}

~~容易發現，~~左旋和右旋是相反的操作。如圖：

有了旋轉操作，我們就可以在不破壞val的二叉搜索樹性質的條件下維護lev的堆性質了。

有一個細節：由於旋轉後當前子樹的樹根會改變，所以在zig和zag函數中參數p要傳引用以方便修改p。

1.3. 插入與刪除

Treap 的插入操作和普通二叉搜索樹差不多，只不過如果在插入過程中堆性質被破壞要通過旋轉來維護。代碼如下：

void insert(int &p,int x){//插入
    if(p==nul){//如果沒有值為x節點就新建一個
        p=new_treap_node();
        pool[p].val=x;
        pool[p].siz=pool[p].cnt=1;
    }else if(x==pool[p].val){//如果找到值為x節點就讓副本數++
        pool[p].cnt++;
        push_up(p);
    }else if(x<pool[p].val){//遞歸
        insert(pool[p].ls,x);
        push_up(p);
        if(pool[pool[p].ls].lev>pool[p].lev)zig(p);//通過旋轉維護lev的堆性質
    }else{//x>pool[p].val
        insert(pool[p].rs,x);
        push_up(p);
        if(pool[pool[p].rs].lev>pool[p].lev)zag(p);
    }
}

Treap 的刪除操作稍微複雜億點。由於 Treap 噁心的堆性質，所以在刪除節點時要採取把節點旋轉成葉子再直接刪除的方式刪除節點。

void erase(int &p,int x){
    if(p==nul){//沒有值為x的節點就沒有刪除的必要了
    }else if(x==pool[p].val){//如果要刪除當前節點
        if(pool[p].cnt>1){//如果有多個副本就副本數--
            pool[p].cnt--;push_up(p);
        }else{//如果只有1個副本就必須刪除當前節點
            pool[p].cnt=0;
            if(!(pool[p].ls||pool[p].rs)){//如果當前節點是葉子就直接刪除
                delete_treap_node(p);
            }else{//否則往下轉
                //為滿足堆性質要判斷應該讓左兒子還是右兒子「當爹」
                if(pool[p].rs==0||//只有左兒子
                (pool[p].ls&&pool[pool[p].ls].lev>pool[pool[p].rs].lev)){//左兒子大於右兒子
                    zig(p);//讓左兒子「當爹」
                    erase(pool[p].rs,x);//當前節點轉到了右兒子上，繼續「追殺」
                }else{//同理
                    zag(p);
                    erase(pool[p].ls,x);
                }
            }
        }
    }else if(x<pool[p].val){//遞歸
        erase(pool[p].ls,x);
        push_up(p);
        if(pool[p].ls&&pool[pool[p].ls].lev>pool[p].lev)zig(p);
    }else{//x>pool[p].val
        erase(pool[p].rs,x);
        push_up(p);
        if(pool[p].rs&&pool[pool[p].rs].lev>pool[p].lev)zag(p);
    }
}

1.4. 其他查找操作

Treap 的查找操作跟普通的二叉搜索樹相同，這裡不再贅述，直接放代碼：

int rank(int p,int x){//查詢比x小的數的個數+1
    if(p==nul){
        return 1;
    }else if(x==pool[p].val){
        return pool[pool[p].ls].siz+1;
    }else if(x<pool[p].val){
        return rank(pool[p].ls,x);
    }else{
        return pool[pool[p].ls].siz+pool[p].cnt+rank(pool[p].rs,x);
    }
}
int kth(int p,int x){//查詢第x小的樹
    if(p==nul){
        return INF;
    }else if(pool[pool[p].ls].siz>=x){
        return kth(pool[p].ls,x);
    }else if(pool[pool[p].ls].siz+pool[p].cnt>=x){
        return pool[p].val;
    }else{
        return kth(pool[p].rs,x-pool[pool[p].ls].siz-pool[p].cnt);
    }
}
int count(int p,int x){//查詢x有多少個
    if(p==nul){
        return 0;
    }else if(x==pool[p].val){
        return pool[p].cnt;
    }else if(x<pool[p].val){
        return count(pool[p].ls,x);
    }else{
        return count(pool[p].rs,x);
    }
}

2. Treap 的應用

Treap 可以維護很多信息，還可以擴展到樹套樹、可持久化等神奇科技。總之，Treap 十分實用。

3. 坑點與吐槽

Treap 的旋轉操作十分毒瘤，如果在考場上忘了怎麼寫可以把這張圖畫一畫。
一定要考慮邊界情況！一定要考慮邊界情況！一定要考慮邊界情況！
一定要隨手push_up！
Treap 的模板題博主調了甚至幾個月才調出來（我太菜了QAQ）。如圖：~~我真有毅力（小聲~~

4. 完整代碼

最後，附贈一份能通過模板題洛谷P3369的代碼：

#include <iostream>
#include <queue>
using namespace std;
#define MAXN 100000
#define INF 0x3fffffff
struct treap_node{
    int ls,rs;
    int val;
    int cnt,siz,lev;
};
treap_node pool[MAXN+5];
int treap_tail;
const int nul=0;
queue<int> treap_rubbish;
int new_treap_node(){
    int res=0;
    if(treap_rubbish.empty()){
        res=++treap_tail;
    }else{
        res=treap_rubbish.front();
        treap_rubbish.pop();
    }
    pool[res].cnt=pool[res].siz=pool[res].ls=pool[res].rs=0;
    pool[res].val=0;
    pool[res].lev=rand();
    return res;
}
void delete_treap_node(int &p){
    treap_rubbish.push(p);
    p=0;
}
struct treap{
    int root;
    treap(){
        root=nul;
    }
    void zig(int &p){
        int tmp=pool[p].ls;
        pool[p].ls=pool[tmp].rs;
        pool[tmp].rs=p;
        push_up(p);push_up(tmp);
        p=tmp;
    }
    void zag(int &p){
        int tmp=pool[p].rs;
        pool[p].rs=pool[tmp].ls;
        pool[tmp].ls=p;
        push_up(p);push_up(tmp);
        p=tmp;
    }
    void push_up(int p){
        pool[p].siz=pool[pool[p].ls].siz+pool[pool[p].rs].siz+pool[p].cnt;
    }
    void insert(int &p,int x){
        if(p==nul){
            p=new_treap_node();
            pool[p].val=x;
            pool[p].siz=pool[p].cnt=1;
        }else if(x==pool[p].val){
            pool[p].cnt++;
            push_up(p);
        }else if(x<pool[p].val){
            insert(pool[p].ls,x);
            push_up(p);
            if(pool[pool[p].ls].lev>pool[p].lev)zig(p);
        }else{//x>pool[p].val
            insert(pool[p].rs,x);
            push_up(p);
            if(pool[pool[p].rs].lev>pool[p].lev)zag(p);
        }
    }
    void erase(int &p,int x){
        if(p==nul){
        }else if(x==pool[p].val){
            if(pool[p].cnt>1){
                pool[p].cnt--;push_up(p);
            }else{
                pool[p].cnt=0;
                if(!(pool[p].ls||pool[p].rs)){
                    delete_treap_node(p);
                }else{
                    if(pool[p].rs==0||
                    (pool[p].ls&&pool[pool[p].ls].lev>pool[pool[p].rs].lev)){
                        zig(p);
                        erase(pool[p].rs,x);
                    }else{
                        zag(p);
                        erase(pool[p].ls,x);
                    }
                }
            }
        }else if(x<pool[p].val){
            erase(pool[p].ls,x);
            push_up(p);
            if(pool[p].ls&&pool[pool[p].ls].lev>pool[p].lev)zig(p);
        }else{//x>pool[p].val
            erase(pool[p].rs,x);
            push_up(p);
            if(pool[p].rs&&pool[pool[p].rs].lev>pool[p].lev)zag(p);
        }
    }
    int rank(int p,int x){
        if(p==nul){
            return 1;
        }else if(x==pool[p].val){
            return pool[pool[p].ls].siz+1;
        }else if(x<pool[p].val){
            return rank(pool[p].ls,x);
        }else{
            return pool[pool[p].ls].siz+pool[p].cnt+rank(pool[p].rs,x);
        }
    }
    int kth(int p,int x){
        if(p==nul){
            return INF;
        }else if(pool[pool[p].ls].siz>=x){
            return kth(pool[p].ls,x);
        }else if(pool[pool[p].ls].siz+pool[p].cnt>=x){
            return pool[p].val;
        }else{
            return kth(pool[p].rs,x-pool[pool[p].ls].siz-pool[p].cnt);
        }
    }
    int count(int p,int x){
        if(p==nul){
            return 0;
        }else if(x==pool[p].val){
            return pool[p].cnt;
        }else if(x<pool[p].val){
            return count(pool[p].ls,x);
        }else{
            return count(pool[p].rs,x);
        }
    }
};
int main(){
    srand(19260817);
    treap a;
    int n;cin>>n;
    while(n--){
        int op,x;cin>>op>>x;
        if(op==1){
            a.insert(a.root,x);
        }else if(op==2){
            a.erase(a.root,x);
        }else if(op==3){
            cout<<a.rank(a.root,x)<<endl;
        }else if(op==4){
            cout<<a.kth(a.root,x)<<endl;
        }else if(op==5){
            cout<<a.kth(a.root,a.rank(a.root,x)-1)<<endl;
        }else if(op==6){
            cout<<a.kth(a.root,a.rank(a.root,x)+a.count(a.root,x))<<endl;
        }
    }
    return 0;
}

5.點一個贊！

Tags: 學習筆記數據結構

平衡樹 Treap（樹堆）學習筆記

0. Treap 的含義及用途

1. 操作

1.-1. Treap 需要維護的信息

1.0. 新建節點、刪除節點與垃圾回收

1.1. 旋轉

1.3. 插入與刪除

1.4. 其他查找操作

2. Treap 的應用

3. 坑點與吐槽

4. 完整代碼

5.點一個贊！

VirMach 便宜 VPS

QNews

平衡樹 Treap（樹堆） 學習筆記

0. Treap 的含義及用途

1. 操作

1.-1. Treap 需要維護的信息

1.0. 新建節點、刪除節點與垃圾回收

1.1. 旋轉

1.3. 插入與刪除

1.4. 其他查找操作

2. Treap 的應用

3. 坑點與吐槽

4. 完整代碼

5.點一個贊！

分享此文：

Related Posts

是時候學習python了

python獲取微信公眾號文章里的網頁圖片

Hexo博客（Snail主題）搭建回顧概覽

顧客銀行辦業務時一隻貓從窗口爬出 網友：原來有公務在身

VirMach 便宜 VPS

QNews

熱門搜尋

平衡樹 Treap（樹堆）學習筆記

顧客銀行辦業務時一隻貓從窗口爬出網友：原來有公務在身