平衡樹

建議在清楚二元搜尋樹的所有操作之後食用本文。本文將略過部分基礎知識

本文主要會講到4中較常用的平衡樹：

• Treap

• FHQ-Treap（無旋Treap）

• Splay

• WBLT

其實WBLT不怎麼常用，但是我個人最喜歡用

我將會在另一篇文章中講述其他的平衡樹，如AVL，紅黑樹，替罪羊樹等。

可持久化我還會放在另一篇文章中講述，敬請期待。

Treap

Treap也就是 Tree + Heap，在滿足二元搜尋樹的前提下，通過維護二元堆積的性質來保證其複雜度不會太大，一般我們認為是 \(O(\log n)\) 的單次操作複雜度。但是畢竟是隨機的，還是可能會炸，此乃後話。

先宣告一點名詞：

• 權值：也就是資料，每一個結點儲存的資料。

• 優先度：用於維護二元堆積性質，是新建結點的時候隨機生成的。

圖中我會以二元組的形式給出，格式為 權值，優先度

我一般習慣用大根堆，且優先度為非負數，這樣要方便一點

這是一顆很簡單的樹，我們現在來考慮各種操作。

不過，我還是給出樹的宣告：

其他的樹定義類似！

typedef unsigned int uint;
template<int N = 1e5 + 3>
class Treap {
private:
    int lc[N], rc[N]; // 左右節點
    uint pri[N]; // 優先度，定義為非負整數！
    int val[N]; // 權值
    int cnt[N]; // 計數器
    int siz[N]; // 以當前結點為根的子樹的結點個數（用於查詢kth和rank）
    int root, usage; // 根節點和使用的結點個數
    // int fa[N]; // 記錄父親結點，如果需要的話
public:
    // ...
}

旋轉

這裡我們記住一張圖即可：

從左到右是右旋，從右到左是左旋。

可以發現，這種旋轉並不會改變中序遍歷的結果（不會影響二元搜尋樹的性質）。但是可以影響二元堆積的性質。所以我們可以以此維護二元堆積的性質。

由於我們需要改變 q 或者 p 父節點對其的指向，我們採用參照的方式修改父節點。

後面的Splay也會有旋轉的操作，但是兩者需要的旋轉方式不一樣。

這裡是將子節點旋轉到當前結點 p 上，而splay中的旋轉在實現的時候是把當前節點 p 轉到父結點上，別混淆了！

void leftRotate(int &p) { // 定義左旋操作
    int q = rc[p];
    rc[p] = lc[q], lc[q] = p;
    p = q; // 更新父節點對此結點的資訊
    update(lc[p]), update(p); // 更新結點資訊。p已經改變過了！
}

void rightRotate(int &p) { // 定義右旋操作，與上面類似，只是變化了一下lc和rc！
    int q = lc[p];
    lc[p] = rc[q], rc[q] = p, p = q;
    update(rc[p]), update(p);
}

是不是該說一下 update 是個啥？

直接看程式碼吧：

void update(p) {
    siz[p] = siz[lc[p]] + siz[rc[p]] + cnt[p];
}

插入

與二元搜尋樹的插入類似。如果遇到已經插入過的結點可以選擇新建結點，或者增加標記（++cnt[p]），這裡選擇後者。

我們先來看新建結點的過程：

int newNode(int x, uint prio = 0) {
    ++usage;
    lc[usage] = rc[usage] = 0;
    pri[usage] = prio ? prio : rand();
    val[usage] = x;
    cnt[usage] = siz[usage] = 1;
    return usage;
}

這只是新建一個空結點的操作而已……接下來我們才涉及到插入部分。

新建結點的操作每一種樹都很類似，注意靈活修改！

首先我們還是正常的插入，例如我們在剛開始的例子的基礎上插入了 (6, 8)

那麼根據二元搜尋樹的插入方式，插入後應該如下：

很明顯，此時不滿足二元堆積的性質，我們需要通過旋轉的方法來維護。

不難得知，我們需要對 (7, 7) 做一次右旋操作，以使 (6, 8) 成為 (7, 7) 的父節點，從而滿足二元堆積的性質。

結果如下：

接著，由於我們一定是在最底部插入的結點，所以我們只需要在回溯的時候一路向上維護二元堆積的性質即可。

程式碼如下：

void insert(int &p, int x) { // 由於旋轉操作需要來自父節點的參照，新建節點也是！
    if (!p) {
        p = newNode(x); // 新建結點
        return;
    }

    if (val[p] == x) { // 有相同結點，增加參照即可
        ++cnt[p], ++siz[p];
        return;
    } else if (val[p] > x) { // 進入左樹
        insert(lc[p], x);
        if (pri[p] < pri[lc[p]]) rightRotate(p); // 維護二元堆積性質
    } else { // 進入右樹
        insert(rc[p], x);
        if (pri[p] < pri[rp[p]]) leftRotate(p);
    }
    update(p); // 更新資訊
}

刪除

首先我們先找到需要修改的結點：

void remove(int &p, int x) {
    if (!p) return; // 沒有找到要刪除的結點
    if (x != val[p]) {
        remove(x < val[p] ? lc[p] : rc[p], x), update(p);
        return;
    }

    // TODO
}

然後我們考慮兩種情況：

• 如果計數大於1，那麼我們減少計數，結束即可：

  if (cnt[p] > 1) {
      --cnt[p], --siz[p];
      return;
  }
  

• 如果計數等於1，那麼我們不斷再保證二元堆積的性質的情況下不斷向下旋轉。直到沒有子節點，那麼我們可以直接 p = 0，刪除即可。

  if (lc[p] || rc[p]) {
      if (rc[p] == 0 || pri[lc[p]] > pri[rc[p]]) {
          rightRotate(p), remove(rp[p], val);
      } else {
          leftRotate(p), remove(lc[p], val);
      }
  } else {
      p = 0;
  }
  

依據邏輯把三個部分合起來即可。

其他操作

例如查詢第k大，獲取某個數的排名，獲取前驅或者後驅。

和二元搜尋樹的方法一致，這裡就不過多講述了。

程式碼連結

此處採用的是另一種寫法！注意甄別！ Link

FHQ-Treap

首先我們瞭解一下這個東西和普通的Treap有啥不同：

• FHQ-Treap基於分裂和合並的操作，代替了旋轉，使得可持久化更為容易

• 操作相對簡單，時間複雜度的階沒有變化，還是 \(O(\log n)\)，但是常數要大一點

我們先來看最重要的分裂部分

分裂

分裂有兩種形式

• 按權值 v 分裂：將小於等於 v 的所有節點分裂為一棵樹，大於 v 的放在一棵樹

• 按排名 k 分裂：將前 k 個數放在一棵樹，其他的放在另一顆樹。

兩者十分類似，程式碼幾乎一模一樣，所以這裡只細述按權值分裂。

我們還是拿最初的那張圖為例子來講：

假如我們要按權值 4 分裂，也就相當於分成如下兩棵樹：

按權值 3 分裂，也就相當於分成如下兩棵樹：

藍色的表示新建的邊，紅色的表示斷開的邊

似乎有點感覺了？我們來細談分裂的全過程

約定此處紅色為左樹（權值小於等於 v），藍色為右樹（權值大於 v），綠色為下一步進入的結點

x 結點指新入的結點需要拼接到的位置，y 同樣

這裡以按權值 3 分裂為例子：

肯定是從根節點開始，明顯，根節點的權值 \(\gt 3\)，所以根節點及其右子樹的所有結點都應該放到藍色樹上：

接下來我們判斷結點 (3, 8)，明顯，節點的權值 \(\le 3\)，所以此節點及其左子樹都應該放在紅色樹上，下一步進入結點 (4, 6)

同樣的判斷，將 (4, 6) 放置在藍樹

下一步的結點為空，結束分裂。

通過觀察，我們可以發現分裂後樹的相對形態沒有改變，所以我們可以嘗試著直接在原樹上直接分裂，避免複製結點的操作。

在我的程式碼中，sync 和其他人寫的 pushdown 是一樣的，只是我不習慣如此寫……所以使用 sync 代替 pushdown，使用 update 代替 pushup……

程式碼如下：

void splitByVal(int p, int v, int &x, int &y) {
    if (!p) return (void)(x = y = 0);
    // sync(p); // 如果需要，下傳標記！！
    if (val[p] <= x)
        x = p, splitByVal(rc[p], v, rc[p], y);
    else
        y = p, splitByVal(lc[p], v, x, lc[p]);
    update(p);
}

而按照排名分裂十分類似，這裡直接給出程式碼：

void splitByRand(int p, int k, int &x, int &y) {
    if (!p) return (void)(x = y = 0);
    // sync(p); // 如果需要，下傳標記！！
    if (siz[lc[p]] < k)
        x = p, splitByRank(rc[p], k - siz[lc[p]] - cnt[p], rc[p], y);
    else
        y = p, splitByRand(lc[p], k, x, lc[p]);
    update(p);
}

合併

由於我們保證了左樹的最大值一定不大於右樹的最大值，所以我們只需要考慮優先度即可。

那麼我們來演示上面分裂後的兩棵樹合併的過程。

此時 x, y 為左樹和右樹的當前結點。返回的是合併後的結點編號。

首先，y 的優先度較大，那麼此時 y 作為父節點，轉而合併 x 和 y 的左子樹，作為 y 的左子樹：

此時 x 的優先度較大，所以此時 x 作為父節點，合併 x 的右子樹和 y，作為 x 的右子樹。

此時 x 為空，直接接上即可。

至此，合併完成。

合併會遇到的兩種情況這裡都涉及到了，那麼我們來看程式碼：

int merge(int x, int y) {
    if (!x | !y) return x | y;
    // sync(x), sync(y); // if need
    if (pri[x] > pri[y]) {
        rc[x] = merge(rc[x], y);
        return update(x), x;
    } else {
        lc[y] = merge(x, lc[y]);
        return update(y), y;
    }
    return -1; // NEVER REACH!
}

其他操作

其他操作很容易通過分裂和合並的操作完成，這裡講述思路即可。

• 插入：新建一個結點作為單獨的一棵樹，將原樹按權值分裂，三者合併即可。

  void insert(int &root, int v) {
      int p = newNode(v);
      int x(0), y(0);
      splitByVal(root, v, x, y);
      root = merge(merge(x, p), y);
  }
  

• 刪除：分裂成三棵樹，中間的樹結點的權值全部為 v，分別合併即可。

  void remove(int &root, int v) {
      int x(0), y(0), z(0), tmp(0);
      splitByVal(root, v - 1, x, tmp); // 分裂為 < v 和 >= v 的兩棵樹
      splitByVal(tmp, v, y, z); // 再分裂為 = v 和 > v 的兩棵樹
      // 以此避免判斷沒有v的情況
      root = merge(merge(x, lc[y]), merge(rc[y], z));
  }
  

• 第 k 大：按排名分裂即可。

• 查詢排名：按權值分裂（為 \(\lt x\) 和 \(\ge x\) 的兩棵樹），使用左樹的大小即可。

• 前驅或者後驅：分裂即可……

整體程式碼我就不給了，核心就這些了。

Splay

伸展樹，由Tarjan（對，就是他）在1985年發明。它與正常的平衡樹不同，不能保證每一次的操作在 \(O(\log n)\) 的複雜度內，只能均攤下來 \(O(\log n)\)。所以說，儘量少用。

Splay最大的特點是每次對一個結點進行操作（讀取，或者修改）之後，都會把他轉到根節點上。

旋轉

我們先來看旋轉操作。

還是要記住上面給出的旋轉的圖，這樣方便於理解。這裡就不細講了。

注意和Treap的旋轉操作區分開來，這裡的旋轉是將當前結點旋轉到其父節點的位置！

// 0 表示是父節點的左子節點，1表示為右子節點
#define side(x) ((x) == rc[fa[(x)]])
// 利用 side 獲取對應的子節點
#define ch(x, k) ((k) ? rc[x] : lc[x])
// rotate x to it's fathers position!
void rotate(int x) {
    int y = fa[x], z = fa[y], k = side(x);
    ch(y, k) = ch(x, k ^ 1);
    if (ch(x, k ^ 1)) fa[ch(x, k ^ 1)] = y;
    ch(x, k ^ 1) = y, fa[y] = x, fa[x] = z;
    if (z) ch(z, y == rc[z]) = x;
    update(y), update(x);
}

在Splay的實現中，update 操作沒有變化，還是 siz[p] = siz[lc[p]] + siz[rc[p]] + cnt[p]

伸展

伸展是Splay最最核心的操作，也就是把一個結點旋轉到根節點（或者其他地方）。

但是僅僅是一路把當前結點向上旋轉就可以了嗎？並不是的。

如果僅僅是一路向上，那麼會有上圖的結果，此時我們只需要來回不斷地操作，就可以卡成單次 \(O(n)\) 的複雜度，因此我們不能這麼做，所以天才的Tarjan想到了另一種旋轉的方法，用以保證其複雜度均攤在 \(O(\log n)\)。

對於每一次旋轉我們分類討論：

• 旋轉一次可以到達目的地：直接旋轉即可。

• 至少需要兩次旋轉：

  • 當前結點與其父節點為同側：先轉父節點，再轉子節點。

  • 不同側，直接兩次向上轉即可。

那麼通過這個規則，我們就可以得到這樣一張圖：

是不是矮了一點 ^_

我們可以理解為通過這種規則旋轉，每次至多可以減少二分之一的高度，最終下來，高度可以保證在 \(O(\log n)\) 的樣子。

所以，伸展的核心程式碼就可以寫出來了：

target指的是向上不停轉之後的最終父節點是什麼，注意！

void splay(int x, int target) {
    // sync if need!
    // for (int i = x; i; i = fa[i]) stack[++top] = i;
    // while (top) sync(stack[top--]);

    while (fa[x] != target) {
        int y = fa[x], z = fa[y];
        if (z != target) rotate(side(x) == side(y) ? y : x);
        rotate(x);
    }
    if (!target) root = x;
}

其他操作

刪除操作非常特殊，後文裡會講，還有，記得每一次無論是查詢還是修改什麼的，記得把目標節點Splay到根！！！

大部分和二元搜尋樹一樣。這裡不細講了。

不過這裡建議一下Splay的寫法細節：

• 寫兩個輔助函數，一個用於尋找對於排名的結點，一個用於尋找對於值的結點，都是返回的結點編號。

  int _findVal(int v) {
      int cur = root;
      while (cur) {
          // sync(cur); // if need
          if (val[cur] == v) return cur;
          else if (v < val[cur]) cur = lc[cur];
          else cur = rc[cur];
      }
      return cur; // 0 for not found!
  }
  // return the node index of the kth element
  int _findKth(int k) {
      int cur = root;
      while (cur) {
          // sync(cur); // if need
          if (siz[lc[cur]] >= k) cur = lc[cur];
          else if (siz[lc[cur]] + 1 == k) return cur;
          else k -= siz[lc[cur]] + 1, cur = rc[cur];
      }
      return cur;
  }
  

• 其他的操作都一定程度上可以基於這兩個操作（或者這兩個操作的變換）。例如 remove。具體操作看註釋

  void remove(int v) {
      int p = _findVal(v);
      if (!p) return;
      splay(p, 0); // 轉到根節點
      if (--cnt[p]) return update(p), (void)0; // 減少計數即可
  
      // 如果只有一個子節點，直接作為根節點即可。
      if (!(lc[p] && rc[p])) {
          root = lc[p] | rc[p];
          fa[root] = 0; // 不需要更新！
          return;
      }
  
      // 否則尋找後驅
      int nxt = rc[p]; // sync(nxt); // if need
      while (lc[nxt]) nxt = lc[nxt]/*, sync(nxt) */;
      // 將後驅轉到p的右節點的位置
      splay(nxt, p);
      // 此時 lc[nxt] 一定為空，考慮二元搜尋樹的性質
      // 所以我們直接把nxt作為根節點，連線原本p的左子樹即可。
      lc[nxt] = lc[p];
      update(root = fa[lc[p]] = nxt); // 更新資訊
  }
  

其實主要是一些奇怪的操作需要……可惡。

WBLT

這是我最喜歡用的一種平衡樹，而且借鑑FHQ-Treap的思路，可以實現類似的操作，這類似的操作這裡不細講。本文只講述基本。

定義：

• 葉節點：沒有子節點的節點。

• 內節點：有子節點的節點。

WBLT全稱是 Weight Balanced Tree，有一點類似於 Size Balanced Tree，只是WBLT是一種 Leafy Tree，只有葉節點（沒有子節點的結點）儲存有資訊。而其他的內節點都是用於輔助搜尋的。

而且WBLT的每一個節點要麼是滿的，要麼是空的。或者說要麼左右兒子都有，要麼都沒有。再或者說內節點既有左節點也有右節點。這使得操作非常方便……

那麼內節點如何輔助搜尋？在WBLT中，內節點儲存的是右節點的值。

語言描述太羅嗦，我們還是直接上圖：

結構還是挺一目瞭然的。

真正儲存著資訊的其實只有紅色圈起來的節點。

不難看出，總共有9個節點，總而言之，如果有 \(n\) 個資料，那麼將會有 \(2n - 1\) 個節點。那麼我們認為其空間複雜度為 \(O(n)\)，只是常數為普通平衡樹的兩倍而已。

搜尋

這或許是唯一一個需要從搜尋開始講述的平衡樹了

例如我們需要搜尋值 3，那麼搜尋路徑應該是這樣的。

由於WBLT內節點儲存資訊的特性，我們進入下一個節點可以分如下情況討論：

• 到達葉子節點：如果當前節點的值等於所需節點的值，那麼搜尋成功，否則，沒有搜到。

• 在內節點上：如果左子節點的值大於等於目標值，則進入左子樹，否則進入右子樹。

  其實看圖不難發現，當前節點的值就是當前子樹中的最大值，所以可以進行上述操作。

這個規則同樣適用於其他的操作！請務必畫下來試一下！

維護平衡

當然還是需要用到旋轉的操作。

別忘了那張圖！！！

但是在WBLT中旋轉的實現又不一樣了。

因為內節點並沒有儲存實際的資訊，所以我們只需要 swap 三次，update 兩次即可。

對了，我好像還沒有講過 update。

在WBLT中，有所變化：

void update(int p) {
    if (lc[p]) { // 防止更新葉節點
        // sync(p) // if need
        siz[p] = siz[lc[p]] + siz[rc[p]];
        val[p] = val[rc[p]];
    }
}

為了減少程式碼，採用了一點奇技淫巧：

#define ch(p, k) (k ? rc[p] : lc[p])
// k 0 left to here, k 1 right to her
// k是0則將左子節點旋轉到此處，否則右節點旋轉到此處。
// 但是這裡沒有旋轉，只是交換節點而已，簡化操作。
void rotate(int p, int k) {
    int q = ch(p, k); // sync(q); // sync if need
    if (!p || !q) return;
    swap(lc[q], rc[q]), swap(lc[p], rc[p]);
    swap(ch(q, k ^ 1), ch(p, k));
    fa[ch(p, k)] = p, fa[ch(q, k ^ 1)] = q;
    update(q), update(p);
}

那麼我們考慮如何維護平衡：

其實一般來說，WBLT 常數本來就小，所以不需要那麼嚴謹的旋轉也可以很好的通過很多題。

// 非嚴謹寫法！！！
void fix(int p) {
    const int ratio = 2;
    if (siz[lc[p]] * ratio < siz[rc[p]]) rotate(p, 1); // 左子樹太大
    if (siz[rc[p]] * ratio < siz[lc[p]]) rotate(p, 0); // 右子樹太大
}

但是為了嚴謹，肯定不能就這麼水過去，萬一有人卡WBLT的常呢？？

所以我們還是要稍微嚴謹一點。

這一部分感謝大佬的文章：拋棄隨機，保持理性——Leafy Tree 到 WBLT - 聽風響，聞蟲鳴。 - 洛谷部落格

在WBLT中，平衡是加權的（並不是嚴格平衡的），一般來說，我們令平衡因子為 \(\alpha\)。

那麼節點 x 平衡意味著 \(\alpha \cdot siz[x] \lt \min\{siz[lc_x], siz[rc_x]\}\)

不難發現，\(\alpha\) 應該 \(\le 0.5\)。

如果所有節點都滿足加權平衡，則這棵樹是加權平衡的，並且其高度滿足  \(h \le \log_{\frac 1{1-\alpha}}n = O(\log n)\)。而樹高正保證了複雜度。

那麼應該如何旋轉？很明顯，在非嚴謹寫法中已經體現出了雛形了：哪一棵子樹大就把那一棵子樹轉上來。

但是觀察上圖可以知道 b 所在的子樹相對位置是不會變的，也就是說如果 \(siz_a \lt \alpha \cdot (siz_a + siz_b + siz_c)\)，並且 \(siz_c < \alpha \cdot (siz_a + siz_b + siz_c)\)，旋轉之後任然不滿足加權平衡。

所以此時我們應該把 b 向上轉一下，然後再進行類似的維護。

這裡講的相對感性，更嚴謹的證明請參考上面給出的文章

操作類似於：

相當於把 b 閹割成倆，然後分別和 a, c 在一起……

所以我們可以得出如下程式碼：

#define ch(p, k) (k ? rc[p] : lc[p])
void fix(int p, double ratio = 0.29) {
    int d;
    if (siz[lc[p]] < siz[p] * ratio) d = 1;
    else if (siz[rc[p]] < siz[p] * ratio) d = 0;
    else return;
    int q = ch(p, d);
    if (siz[ch(q, d)] < siz[p] * ratio) rotate(q, d ^ 1);
    rotate(p, d);
}

插入

還是以上圖為例。不妨假設我們需要插入 3，那麼自然我們到了原來 3 所在的節點。那麼我們如何變成兩個呢？

很明顯，將當前節點作為父節點，左右節點分別為當前節點的值和新增的值。

記得保證左節點不大於右節點的值

然後回溯更新即可。

void insert(int x) {
    if (!root) {
        root = newNode(x, 0);
        return;
    }

    int cur = root;
    while (true) {
        // sync(cur); // if needed
        if (!lc[cur]) { // new node down here!
            int y = val[cur];
            if (x > y) swap(x, y); // make sure x < y
            // 第二個引數是將其父節點設為cur！和Treap的newNode宣告不一樣了
            lc[cur] = newNode(x, cur), rc[cur] = newNode(y, cur);
            break;
        }
        cur = (x > val[lc[cur]]) ? rc[cur] : lc[cur];
    }

    while (cur) {
        update(cur), fix(cur);
        cur = fa[cur];
    }
}

刪除

我們還是先找到要刪除的值所對應的節點吧（任意一個）。

那麼我們用其兄弟節點直接替代其父節點即可。

兄弟節點指的是其父節點的另一個子節點

聽著很簡答吧。在紙上畫一下先！！

參考程式碼：

// 這一塊的程式碼未經編譯驗證！！可能會有問題
void copyFrom(int p, int q) {
    lc[p] = lc[q], rc[p] = rc[q];
    fa[lc[p]] = fa[rc[p]] = p;
    val[p] = val[q], siz[p] = siz[q];
}

void remove(int p, int x) {
    if (!p) return;
    if (val[lc[p]] >= x) {
        if (siz(lc[p]) == 1 && val[lc[p]] == val) {
            // _del(rc[p]), _del(lc[p]); 標記回收節點，如果需要的話（記得別清空，copyFrom需要用！）
            copyFrom(p, lc[p]);
        } else {
            remove(lc[p], val), update(p), fix(p);
        } 
    } else {
        if (siz(rp) == 1 && val(rp) == val) {
            // _del(lp), _del(rp);
            copyFrom(p, rc[p]);
        } else {
            remove(rc[p], val), update(p), fix(p);
        }
    }
}

當然，你也可以寫成非遞迴的形式，這裡就不展示了。

其他操作

其實我覺得其他操作都很簡單，不想多說，掌握了二元搜尋樹的演演算法，應該自然就會了。

這裡就直接展示部分基礎操作的程式碼吧。

// 統計所有 < x 的值的個數，也可以用於獲取排名
int count(int x) {
    int cur(root), cnt(0);
    while (cur) {
        if (siz[cur] == 1) return cnt;
        else if (val[lc[cur]] >= val) cur = lc[cur];
        else cnt += siz[lc[cur]], cur = rc[cur];
    }
}

int kth(int k) {
    int cur(root);
    while (cur) {
        if (siz[cur] == 1) return k == 1 ? val[cur] : -1; // -1: not found!
        else if (siz[lc[cur]] >= k) cur = lc[cur];
        else k -= siz[lc[cur]], cur = lc[cur];
    }
}

int getpre(int val) {
    return kth(count(val));
}

int getpost(int val) {
    return kth(count(val + 1) + 1);
}

---

到這裡，你應該學會了四種在OI中較為常用的平衡樹了吧。

那麼模板題肯定可以用四種方法過了吧：

• 【模板】普通平衡樹 - 洛谷

• 【模板】普通平衡樹（資料加強版） - 洛谷

• 【模板】文藝平衡樹 - 洛谷

哦，文藝平衡樹啊，並不是一種平衡樹，它可以通過FHQ-Treap或者Splay實現，拓展的WBLT也可以實現（只是這裡沒有講）。

---

附贈各種樹速度比較（基於正常平衡樹亂資料的操作）：

Splay < FHQ-Treap < Treap < WBLT < Better-Optimized FHQ-Treap

+ ?? 陽壽隨機種子Treap

更加優化的Treap參考：treap怎樣跑得更快 - zx2003 的部落格 - 洛谷部落格