面試官問我：什麼是樹堆（Treap）？

說起二叉查找樹的平衡調整，大家最先想到的一定是紅黑樹或者 AVL 樹。

其實，能夠進行平衡調整的二叉樹還有很多種，**樹堆（Treap）**就是其中一種。

Treap 是什麼？

顧名思義，Treap=Tree+Heap，樹堆 = 樹 + 堆

所以，Treap 就一定是樹和堆的結合體咯！

恭喜你，你已經掌握 Treap 的精髓了

那麼 Treap 是怎樣把樹和堆的優點結合起來的呢？

Treap 的特性

Treap 與 AVL、紅黑樹等平衡樹本質相同，都是一個二叉查找樹（BST）。但是作爲一個平衡樹，它必須要有一個維護樹平衡的功能（避免變成一條鏈）。它的每個節點還有一個隨機生成的優先級，這些優先級要滿足堆的性質，以保證這個樹相對較平衡。

比如說這個

就是一個 Treap 樹（本質上跟 BST 沒區別）

問題是，在調整（插入、刪除元素）Treap 樹時可能會使得每個節點的優先級不滿足堆的性質，所以我們要對樹進行調整

Treap 的建模

我們考慮用指針的方式建樹，一個節點的模型如下：

typedef struct Node {
    Node(int v) {
        val = v, cnt = size = 1, fac = rand();
        lson = rson = NULL;
    }
    //  值  個數  子樹大小 優先級
    int val, cnt, size, fac;
    // 元素有可能重複，所以用cnt記有多少個
    //     左兒子 右兒子
    Node *lson, *rson;
    // 每次更改後更新以這個節點的爲根的字數大小
    inline void push_up() {
        size = cnt;
        if (lson != NULL) size += lson->size;
        if (rson != NULL) size += rson->size;
    }
}* Tree;
inline int size(Tree t) { return t == NULL ? 0 : t->size; }
inline Tree init() {
    Tree rt = new Node(Inf);
    rt->lson = new Node(-Inf);
    rt->fac = -Inf, rt->lson->fac = -Inf;
    rt->push_up();
    return rt;
}

Treap 的操作

我們爲了保證 Treap 樹在改變後優先級依然能夠滿足堆的性質，我們需要在它滿足二叉查找樹的前提下進行旋轉使得它的優先級形成一個堆。Treap 的好處就在於它只有 2 種旋轉。

右旋

我們假設這個樹已經滿足二叉查找樹的特性，即 D<B<E<A<C，我們可以這樣旋轉

第一步：把 A-C 邊掛到 B 下面

第二步：把點 E 掛到 A 下面

這樣旋轉，依然保證這個子樹滿足 D<B<E<A<C，還調整了樹形。我們把右旋總結爲：

樞紐（B）拎上來，父（A）兄（C）掛下面，右孩（E）給父親（A）

注意：D、C、E 都可以表示一個子樹而不僅僅是一個節點

代碼如下：

inline void right_rotate(Tree &a) {
    Tree b = a->lson;
    a->lson = b->rson, b->rson = a, a = b;
    a->rson->push_up(), a->push_up();
}

左旋

左旋跟右旋差不多一樣，把右旋的整個過程反過來就是左旋。也是分兩步走：

第一步：

第二步：

代碼如下：

inline void right_rotate(Tree &a) {
    Tree b = a->lson;
    a->lson = b->rson, b->rson = a, a = b;
    a->rson->push_up(), a->push_up();
}

網上也有博文將lson和rson寫成一個數組son，然後將左旋和右旋寫成一個函數：

inline void rotate(Tree &a, int f) {
    Tree b = a->son[f^1];
    a->son[f^1] = b->son[f], b->son[f] = a, a = b;
    a->rson->push_up(), b->push_up();
}

注意左旋、右旋中的代碼傳的參數a需要傳引用，因爲最後a也要更新

插入節點

Treap 也是一類 BST，所以插入的時候我們首先要遵循 BST 的插入規則，插入之後再根據優先級判斷是否需要旋轉。我們以這個樹爲例（綠色小字是該節點的優先級），我們要在這個樹中插入一個 8。

當前的目標是在以值爲 2 的節點爲根的子樹上，插入一個值爲 8 的節點。

而我們發現，8>2，8 一定在根的右子樹上。

因此，這個問題就變成了在以值爲 6 的節點爲根的子樹上插入一個值爲 8 的節點。

而我們發現，8>6，8 一定在根的右子樹上。

這個問題就變成了在以值爲 9 的節點爲根的子樹上，插入一個值爲 8 的節點。

而我們發現，8<9，8 一定在根的左子樹上，而 9 已經是葉子了，可以直接往進塞。

假設這個節點的優先級是 5（隨機出來的）：

很明顯，兩個標紅的優先級不滿足大頂堆的特性（即兒子的優先級大於父親的了），而且這兩個節點是向左斜的，那麼我們就要對這個節點進行右旋。因爲兩個節點都沒有額外的兒子，所以一步完成：

顯然，旋轉以後這依然滿足 BST 的特性。然而，我們又雙叒叕發現，兩個標紅的優先級不滿足堆的特性了，而且這兩個不滿足的節點是向右斜的，我們可以對這個子樹進行左旋：

一次插入就完成啦！

我們總結一下，一步步往下走找到一個合適的位置滿足 BST，然後再一步步往上走進行旋轉以滿足堆的特性。

顯然，我們可以用遞歸來完成這個過程。往下走的部分藉助遞，向上走的部分藉助歸。

我們來寫一下代碼，這裏可能有點難理解，好好看註釋：

刪除節點

刪除節點與插入節點的順序基本一樣。都是先下後上。

我們還是舉一個例子，我們要刪除值爲 6 的節點：

當前的目標就是在以值爲 2 的節點爲根的子樹中刪除值爲 6 的節點

因爲 6>2，所以目標節點一定在根的右子樹上，這個問題就變爲，

在以值爲 6 的節點爲根的子樹中刪除值爲 6 的節點

很好！我們已經找到目標節點了。皇帝駕崩了，大皇子頂上！

我們可以讓樹旋轉使得優先級較大的兒子替換掉父親（目標節點）

在這裏我們給 6 這個子樹進行左旋

但是我們要刪的節點跑了，我們要繼續追殺！

我們追到左子樹，拿着槍對着它，它還算敬業，要讓自己另一個兒子接班後再陣亡。

作爲一個善良的人，我們只好應允它的請求，再它給轉！

這時候，6 已經沒有拖延時間的藉口了，我們直接祝它清明節快樂，刪掉它吧！

顯然刪完之後，這個樹依然滿足 Treap 樹的特性。

話不多說，直接上代碼：

inline void del(Tree &rt, int val) {
    if (rt == NULL) return; // 沒找到
    if (rt->val == val) {
        // 找到這個節點了
        if (rt->cnt > 1) {rt->cnt--, rt->push_up(); return;}
        // 它有孩子
        if (rt->lson != NULL || rt->rson != NULL) {
            // 重點
            if (rt->rson == NULL || rt->lson != NULL && rt->lson->fac > rt->rson->fac)
                right_rotate(rt), del(rt->rson, val);
            else left_rotate(rt), del(rt->lson, val);
        }
        else {delete rt; rt = NULL; return;} // 手動gc
    }
    else if (rt->val > val) del(rt->lson, val);
    else del(rt->rson, val);
    rt->push_up();
}

查詢

查詢分好幾種，因爲 Treap 跟普通 BST 一樣，所以直接貼代碼了

查詢排名

inline int qry_rank(Tree p, int val) { // 詢問有多少個數小於等於val（也就相當於查詢排名）
    int rank = 0;
    while (p != NULL)
        if (p->val == val) return size(p->lson) + rank;
        else if (p->val > val) p = p->lson;
        else rank += size(p->lson) + p->cnt, p = p->rson;
    return rank;
}

或是

inline int qry_rank(Tree p, int val) {
    if (p->val == val) return size(p->lson);
    if (p->val > val) return qry_rank(p->lson, val);
    return qry_rank(p->rson, val) + size(p->lson) + p->cnt;
}

查詢數值

inline int qry_value(Tree p, int rank) {
    while (p != NULL && rank)
        if (size(p->lson) > rank) p = p->lson;
        else if (size(p->lson)+p->cnt >= rank) return p->val;
        else rank -= size(p->lson)+p->cnt, p = p->rson;
}

或是

inline int qry_value(Tree p, int rank) {
    if (size(p->lson) >= rank) return qry_value(p->rson, rank);
    if (size(p->lson)+p->cnt >= rank) return p->val;
    return qry_value(p->lson, rank-size(p->lson)-p->cnt);
}

查詢前驅

inline int qry_pre(Tree p, int val) {
    int pre = 0;
    while (p != NULL)
        if (p->val < val) pre = p->val, p = p->rson;
        else p = p->lson;
    return pre;
}

或者直接qry_value(qry_rank(p, val)-1)

查詢後繼

inline int qry_suf(Tree p, int val) {
    int suf = 0;
    while (p != NULL)
        if (p->val > val) suf = p->val, p = p->lson;
        else p = p->rson;
    return suf;
}

或者直接qry_value(qry_rank(p, val)+1)

總結

Treap 不算是一個標準的平衡樹。但因爲它完美地結合了樹和堆的特性，使得它常數比 AVL 小，無論是在競賽中還是在開發應用中都有比較好的效果，因此常用來代替 AVL 樹。

同時，我們也可以從中學到一點：兩種不同的算法可以通過巧妙的方法優勢互補，從而達到更好的效果。在實際開發中我們如果能運用這個方法，一定能得到不小的成效。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/xXqV_MT3waiiGknbwrQbQg