普通 FHQ_Treap從入門到精通(注釋比代碼多系列)

前提說明,作者寫注釋太累了,文章里的部分講解來源于Oi-wiki，并根據代碼，有部分增改，本文僅僅發布于博客園與知乎風的彷徨，其他地方出現本文，均是未經許可的盜竊，

芝士前置

芝士引入

節點定義

struct FHQ_Node
{
    int sze, val, pri;
    int lc, rc;
    FHQ_Node()
    {
        sze = 1; //注意0號節點不能這樣
        pri = rand();
    }
} FHQ_Tree[N];

基本操作

FHQ_Treap不同于傳統Treap，FHQ_Treap是基于以下兩個基本操作分裂，合并，而不是旋轉，所以也有叫無旋Treap，

基本思路很簡單

操作解釋

分裂

分裂操作是基于遞回實作的，

分裂程序接受兩個引數：根指標\(u\)? 、關鍵值\(key\)? ，結果為將根指標指向的 treap 分裂為兩個 treap，第一個 treap 所有結點的關鍵值小于$key \(?，第二個 treap 所有結點的關鍵值大于等于\)key \(?，該程序首先判斷\)key$? 是否大于 \(u\)?的關鍵值，若大于，則說明 \(u\)?及其左子樹全部屬于第一個 treap(當然也有一部分右子樹屬于,一部分不屬于,所以需要遞回進去)，否則說明\(u\)?及其右子樹全部屬于第二個 treap(同理,也需要遞回進去)，根據此判斷決定應向左子樹遞回還是應向右子樹遞回，繼續分裂子樹，待子樹分裂完成后按剛剛的判斷情況連接 的左子樹或右子樹到遞回分裂所得的子樹中，

pair<int, int> split(int u, int _key)
{
    if (u == 0)
        return make_pair(0, 0); //如果我是個空節點，那我就算分割后的節點也是空的
    if (FHQ_Tree[u].val < _key) //當前節點小于臨界key，右兒子比我大，說不定有比key大（或者等于）的，左兒子比我小，一定不可能大于等于key了
    {
        pair<int, int> ret = split(FHQ_Tree[u].rc, _key); //但是右兒子里可能有比我大的（甚至是大于key）
        FHQ_Tree[u].rc = ret.first;                       //沒有key的那作為的的新右兒子，隨我一起被切出去
        updata(u);                                        //我被切了，需要維護一下大小資訊
        return make_pair(u, ret.second);                  //我屬于小于key的部分，而被切除了小于key節點的右兒子當然就完全都是大于等于key了
    }
    else //當前節點大于等于臨界key，右兒子比我還大，肯定是也大于key的，不用管，
    {
        pair<int, int> ret = split(FHQ_Tree[u].lc, _key); //同理左兒子也有可能小于我的（甚至是小于key）
        FHQ_Tree[u].lc = ret.second;                      //比大于等于key的作為我的新左兒子，和我一起走
        updata(u);                                        //我被切了，需要維護一下大小資訊
        return make_pair(ret.first, u);                   //我清除掉了小于key的子樹，這部分小于key，而和我在一起的都要比key大
    }
}

合并

合并操作也是基于遞回的

合并程序接受兩個引數：左 treap 的根指標\(x\) 、右 treap \(y\)的根指標 ，必須滿足\(u\)中所有結點的關鍵值小于\(y\)中所有結點的關鍵值，因為兩個 treap 已經有序，我們只需要考慮\(pri\)?來決定哪個 treap 應與另一個 treap 的兒子合并，若\(x\)的根結點的\(pri\)大于\(y\)的，那么 即為新根結點，\(y\)應與\(x\)的右子樹合并；反之，則\(y\)作為新根結點，然后讓\(x\)與\(y\)的左子樹合并，不難發現，這樣合并所得的樹依然滿足\(pri\)的大根堆性質，

int merge(int x, int y) //把x和y拼在一起(前提是x里所有節點都要比y所有節點小)
{
    if (!x || !y) //如果其中有一個節點是空的，那就別合并了，直接回傳非空的那個就好了
        return x + y;
    if (FHQ_Tree[x].pri > FHQ_Tree[y].pri) //采用大根堆，x現在應該在y上面
    {
        //由于x都比y小，那么y只能掛在x的右兒子上
        //                      x全部小于y,這里順序別搞錯了
        FHQ_Tree[x].rc = merge(FHQ_Tree[x].rc, y); //考慮到x原本可能就有右兒子，先把x的右兒子和y拼在一起再說
        updata(x);                                 //y掛在了我身上，我肯定變大了，需要維護一些大小資訊
        return x;                                  //y在我下面，我才是這棵樹的老大
    }
    else //現在x應該在y下面了
    {
        //由于x都比y小，那么y只能考慮掛在y的左兒子上
        //                      x全部小于y,這里順序別搞錯了
        FHQ_Tree[y].lc = merge(x, FHQ_Tree[y].lc); //考慮到y原本可能就有左兒子，先把x和y的左兒子拼在一起再說
        updata(y);                                 //x掛在了我身上，我肯定變大了，需要維護一些大小資訊
        return y;                                  //x在我下面，我才是這棵樹的老大
    }
}

功能操作

插入

先在待插入的關鍵值處將整棵 treap 分裂，判斷關鍵值是否已插入過之后新建一個結點，包含待插入的關鍵值，然后進行兩次合并操作即可，

void ins(int _val) //插入一個點
{
    FHQ_Tree[++p].val = _val;               //先是創建一個這個樣的節點
    pair<int, int> ret = split(root, _val); //以val為分界線,把這棵樹分裂成兩部分
    //現在我們嘗試把這個新節點插入到樹里
    int _new = merge(ret.first, p); //上文說道，split回傳的第一個樹的每個節點一定比val小,這個時候就可以把這個比val小的樹和新的那個節點合并了
    root = merge(_new, ret.second); //由于新加入的節點的優先級我們是未知的,有可能比原來的根節點大,導致在原來根節點上面,發生換根
}

洗掉

將具有待洗掉的關鍵值的結點從整棵 treap 中孤立出來（進行兩側分裂操作），洗掉中間的一段（具有待洗掉關鍵值），再將左右兩端合并即可，

void del(int _val) //洗掉一個
{
    pair<int, int> ret = split(root, _val);            //按val為分界線,現在含有val的樹一定是ret.second了;
    pair<int, int> ret2 = split(ret.second, _val + 1); //再把ret.second里的節點再分一遍,現在ret2.first里的節點一定全是數為val的點
    //通常情況下,我們只洗掉一個節點
    int _new = merge(FHQ_Tree[ret2.first].lc, FHQ_Tree[ret2.first].rc); //左兒子和右邊兒子合并,其實是其中一個優先級較大的,跑出來當爹,原來的父親就會被孤立
    root = merge(merge(ret.first, _new), ret2.second);                  //同樣的,我們洗掉的有可能就是原來的根,導致發生換根
}

獲取排名

把一個樹按分為小于\(val\)的，和大于等于\(val\)的，\(val\)的排名自然就是小于\(val\)的節點的數量+1了

int getrank(int _val) //獲取排名
{
    pair<int, int> ret = split(root, _val); //以val為分界線,這樣ret.first里的東西都要比val小
    int rank = FHQ_Tree[ret.first].sze + 1; //比val小的樹節點全在里面,val的排名自然就是他們的數量+1了
    root = merge(ret.first, ret.second);    //別忘了把原來拆分的樹合起來
    return rank;
}

通過排名取數字

和二叉搜索樹一樣，不再贅述，

int getnum(int _rank) //通過排名取出這個數來,回傳節點的編號
{
    int now = root; //同平衡二叉樹的方法一樣,從根節點向下找
    while (now)
    {
        //now的左節點全是比now小的,所以比now小的數量加上1(now自己),如果正好是我們要求的點的排名,那么now就是我們要的點了
        if (FHQ_Tree[FHQ_Tree[now].lc].sze + 1 == _rank)
            break;
        else if (FHQ_Tree[FHQ_Tree[now].lc].sze >= _rank) //同理,如果比now小的數的數量大于等于我們的rank,那么排名為rand的數必須要更小,只能在now的左子樹上
            now = FHQ_Tree[now].lc;
        else //rank的位置在now的后面,說明rank的數要比now還大,我們就要去右節點找
        {
            _rank -= FHQ_Tree[FHQ_Tree[now].lc].sze + 1; //由于我們要找到節點在now右節點上,右節點的排名是相對于now的排名,所以我們需要把now的排名減掉
            now = FHQ_Tree[now].rc;
        }
    }
    return now;
}

求前驅

用把原來的二叉樹分裂開，一部分全是小于\(val\)的，另一部分全是大于等于\(val\)，而前驅就是前一個二叉樹里最大的，用二叉搜索樹的性質就能得到，

int pre(int _val) //求前驅,回傳節點的值
{
    pair<int, int> ret = split(root, _val); //以val為分界線分裂
    int now = ret.first;                    //ret.first的數值都比val小
    while (FHQ_Tree[now].rc)                //找比val小的數里最大的,就是前驅了
        now = FHQ_Tree[now].rc;
    int ans = FHQ_Tree[now].val;
    root = merge(ret.first, ret.second); //別忘了把他倆合并了
    return ans;
}

求后繼

用把原來的二叉樹分裂開，一部分全是小于\(val+1\)的，另一部分全是大于等于\(val+1\)，而后繼就是后一個二叉樹里最小的，用二叉搜索樹的性質就能得到，

int nxt(int _val) //求后繼,回傳節點的值
{
    pair<int, int> ret = split(root, _val + 1); //以val+1為分界線分裂,所有比val大的數全在ret.second里
    int now = ret.second;                       //在比val的數里找
    while (FHQ_Tree[now].lc)                    //找比val大的數里最小了的,就是后繼了
        now = FHQ_Tree[now].lc;
    int ans = FHQ_Tree[now].val;
    root = merge(ret.first, ret.second); //別忘了把他倆合并了
    return ans;
}

呼叫方法

洛谷3369

int main()
{
    FHQ_Tree[0].sze = 0; //0號節點作為溢位點,不能有大小

    int n;
    cin >> n;
    while (n--)
    {
        int opt, val;
        cin >> opt >> val;
        switch (opt)
        {
        case 1:
            ins(val);
            break;
        case 2:
            del(val);
            break;
        case 3:
            cout << getrank(val) << endl;
            break;
        case 4:
            cout << FHQ_Tree[getnum(val)].val << endl;
            break;
        case 5:
            cout << pre(val) << endl;
            break;
        case 6:
            cout << nxt(val) << endl;
            break;
        }
    }
    return 0;
}

完整代碼下載地址:https://files.cnblogs.com/files/blogs/694685/FHQ.7z

如果未來有時間我將會出一個支持序列的FHQTreap教程，

標籤：其他

上一篇：Fiddler抓HTTPS介面資料，安裝證書并不復雜，超詳細的圖文解說，不信你看！

下一篇：[資料結構]ODT(珂朵莉樹)實作及其應用，帶圖