1. treap

• 堆的性質(zhì)
  treap = tree + heap
  也就是 treap 是具有堆性質(zhì)的平衡二叉樹(shù)(BST), 而堆性質(zhì)的維護(hù)就靠一個(gè)隨機(jī)值和旋轉(zhuǎn)操作. 可以是小根堆也可以是大根堆.
  用 r 數(shù)組(random)保存隨機(jī)值, 那么在插入結(jié)點(diǎn)時(shí)需要維護(hù)堆性質(zhì)(這里是大根堆)
  ch[o][0] 、ch[o][1] 分別表示 結(jié)點(diǎn)o 的左兒子和右兒子.
  自己定義宏 :
  #define lc ch[o][0]
  #define rc ch[o][1]
  if(r[ch[o][d]] > r[o]) rotate(o, d^1); // rotate見(jiàn)下方

---

• 左旋和右旋 有太多的相似處, 可以用一個(gè)帶旋轉(zhuǎn)方向參數(shù)的 rotate 操作來(lái)完成
  d = 0 表示左旋, d = 1 表示右旋.
  void rotate(int& o, int d) { int k = ch[o][d^1]; ch[o][d^1] = ch[k][d]; ch[k][d] = o; update(o); update(k); o = k; }

---

• 刪除

  • 首先得找到要?jiǎng)h除的結(jié)點(diǎn)

  • 如果該結(jié)點(diǎn)只有一個(gè)左兒子或只有一個(gè)右兒子, 直接將它把要?jiǎng)h除的結(jié)點(diǎn)取代.

    if(lc * rc == 0) o = lc + rc;

  • 否則就考慮堆性質(zhì)的維護(hù)

    int d2 = tr[t.ch[0]].r < tr[t.ch[1]].r ? 1 : 0;rotate(o, d2); remove(o, x);

---

• 查詢(xún)
  
  • 查詢(xún)第 k 大
    如果要查詢(xún)的結(jié)點(diǎn)在當(dāng)前結(jié)點(diǎn)的右兒子上, 那么繼續(xù)查詢(xún)右兒子的第k-s[lc]-1大.
  • 查詢(xún)某結(jié)點(diǎn)排名
    如果要查詢(xún)的結(jié)點(diǎn)在當(dāng)前結(jié)點(diǎn)的右兒子上, 那么排名應(yīng)該增加s[lc]+1.

---

---

2. splay

• 和 treap 比較起來(lái), splay 多的就是伸展(splay)操作.

---

• 關(guān)于伸展操作

  • 兩種實(shí)現(xiàn)方式 : 自頂向下和自底向上.
    自底向上的 splay 我是參考的 HZWER, 需要使用fa數(shù)組記錄當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn). 比較方便的是可以直接通過(guò)這個(gè)fa數(shù)組發(fā)現(xiàn)從一個(gè)結(jié)點(diǎn)走到任意已知結(jié)點(diǎn)的路徑. 于是就誕生了自底向上的splay. 正因?yàn)檫@種特性, 這種伸展方式可以適應(yīng)任何題目.

    void rotate(int& px, int& x, int d) {int t = ch[x][d]; ch[x][d] = px; ch[px][d^1] = t; p[x] = p[px]; p[px] = x; p[t] = px; update(px); update(x); px = x; } void splay(int x, int& k) {while(x != k) {int y = p[x], z = p[y];int d = ch[y][0] == x ? 0 : 1;int d2 = ch[z][0] == y ? 0 : 1;if(y != k) rotate(ch[z][d2], x, d^1); else rotate(k, x, d^1);} }

  • 自頂向下的 splay 可以看《訓(xùn)練指南》, 劉汝佳的代碼. 比較簡(jiǎn)潔高效. 我是把指針改成了數(shù)組, 不習(xí)慣指針的寫(xiě)法, 主要是不知道怎么調(diào)試.

    void splay(int& o, int k) {int d = cmp(o, k);if(d == -1) return;if(d == 1) k -= s[lc] + 1;int p = ch[o][d];int d2 = cmp(p, k);int k2 = (d2 == 0) ? k : k-s[ch[p][0]]-1;if(d2 != -1) {splay(ch[p][d2], k2);if(d == d2) rotate(o, d^1); else rotate(ch[o][d], d);}rotate(o, d^1); }

  • 自頂向下就需要知道你想 splay 的結(jié)點(diǎn)的排名. 那么有的題目比如 書(shū)架 那個(gè)題, 直接告訴你哪個(gè)結(jié)點(diǎn)編號(hào), 但它是第幾個(gè)結(jié)點(diǎn)不知道, 這樣就只能用第一種自底向上的splay了.

  • 另外splay可以一次旋轉(zhuǎn)兩回也可以旋轉(zhuǎn)一回, 即單旋和雙旋. 單旋的方法比較簡(jiǎn)單, 整個(gè)過(guò)程相當(dāng)于先找到第 k 個(gè)結(jié)點(diǎn), 再遞歸自底向上旋轉(zhuǎn)到目標(biāo)結(jié)點(diǎn). 不過(guò)在有些情況會(huì)退化成一條鏈O(n). 轉(zhuǎn)兩回的參考《訓(xùn)練指南》.
    void splay(int& o, int k) {int d = cmp(o, k);if(d == -1) return;if(d == 1) k -= s[lc] + 1;splay(ch[o][d], k); rotate(o, d^1); }

---

• 其他操作和 treap 差不多, 但 splay 支持很多區(qū)間操作

  • 得到一段區(qū)間, 把它移動(dòng)到一個(gè)固定結(jié)點(diǎn).
    都采用自頂向下的splay
    注意這里在首部和末尾都添加一個(gè)虛擬結(jié)點(diǎn)防止溢出.
  // 移動(dòng)到根結(jié)點(diǎn)右兒子的左兒子 void getInterval(int o, int L, int R) {splay(o, L);splay(rc, R - s[lc] - 1); } // 移動(dòng)到根結(jié)點(diǎn)左兒子的右兒子 void getInterval(int o, int L, int R) {splay(o, L);splay(o, R + 2); }
  • 第二種方法只適用于單旋splay
  • 有了這個(gè)獲取區(qū)間的題目, 就可以完成很多區(qū)間的題目, 比如區(qū)間修改、區(qū)間翻轉(zhuǎn)、區(qū)間標(biāo)記之類(lèi)的.

---

---

總結(jié)

以上是生活随笔為你收集整理的[总结] 平衡树总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。