跳转至

替罪羊樹

引入

替罪羊樹 是一種依靠重構操作維持平衡的重量平衡樹。替罪羊樹會在插入、刪除操作時，檢測途經的節點，若發現失衡，則將以該節點為根的子樹重構。

我們在此實現一個可重的權值平衡樹。

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int cnt,                 // 樹中元素總數
    rt,                  // 根節點，初值為 0 代表空樹
    w[MAXN],             // 點中的數據 / 權值
    lc[MAXN], rc[MAXN],  // 左右子樹
    wn[MAXN],            // 本數據出現次數（為 0 代表已刪除）
    s[MAXN],  // 以本節點為根的子樹大小（每個節點記 1 次）
    sz[MAXN],  // 以本節點為根的子樹大小（每個節點記 wn[k] 次）
    sd[MAXN];  // 已刪除節點不計的子樹大小（每個節點記 1 次）

void Calc(int k) {
  // 重新計算以 k 為根的子樹大小
  s[k] = s[lc[k]] + s[rc[k]] + 1;
  sz[k] = sz[lc[k]] + sz[rc[k]] + wn[k];
  sd[k] = sd[lc[k]] + sd[rc[k]] + (wn[k] != 0);
}

重構

過程

首先，如前所述，我們需要判定一個節點是否應重構。為此我們引入一個比例常數 \(\alpha\)（取值在 \((0.5,1)\)，一般採用 \(0.7\) 或 \(0.8\)），若某節點的子節點大小佔它本身大小的比例超過 \(\alpha\)，則重構。

另外由於我們採用惰性刪除（刪除只使用 wn[k]--），已刪除節點過多也影響效率。因此若未被刪除的子樹大小佔總大小的比例低於 \(\alpha\)，則亦重構。

實現

1
2
3
4
5
bool CanRbu(int k) {
  // 判斷節點 k 是否需要重構
  return wn[k] && (alpha * s[k] <= (double)std::max(s[lc[k]], s[rc[k]]) ||
                   (double)sd[k] <= alpha * s[k]);
}

重構分為兩個步驟——先中序遍歷展開存入數組，再二分重建成樹。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void Rbu_Flatten(int& ldc, int k) {
  // 中序遍歷展開以 k 節點為根子樹
  if (!k) return;
  Rbu_Flatten(ldc, lc[k]);
  if (wn[k]) ldr[ldc++] = k;
  // 若當前節點已刪除則不保留
  Rbu_Flatten(ldc, rc[k]);
}

int Rbu_Build(int l, int r) {
  // 將 ldr[] 數組內 [l, r) 區間重建成樹，返回根節點
  int mid = l + r >> 1;  // 選取中間為根使其平衡
  if (l >= r) return 0;
  lc[ldr[mid]] = Rbu_Build(l, mid);
  rc[ldr[mid]] = Rbu_Build(mid + 1, r);  // 建左右子樹
  Calc(ldr[mid]);
  return ldr[mid];
}

void Rbu(int& k) {
  // 重構節點 k 的全過程
  int ldc = 0;
  Rbu_Flatten(ldc, k);
  k = Rbu_Build(0, ldc);
}

實現

幾種操作的處理方式較為類似，都規定了 到達空結點 與 找到對應結點 的行為，之後按 小於向左、大於向右 的方式向下遞歸。

插入

插入時，到達空結點則新建節點，找到對應結點則 wn[k]++。遞歸結束後，途經的節點可重構的要重構。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
void Ins(int& k, int p) {
  // 在以 k 為根的子樹內添加權值為 p 節點
  if (!k) {
    k = ++cnt;
    if (!rt) rt = 1;
    w[k] = p;
    lc[k] = rc[k] = 0;
    wn[k] = s[k] = sz[k] = sd[k] = 1;
  } else {
    if (w[k] == p)
      wn[k]++;
    else if (w[k] < p)
      Ins(rc[k], p);
    else
      Ins(lc[k], p);
    Calc(k);
    if (CanRbu(k)) Rbu(k);
  }
}

刪除

惰性刪除，到達空結點則忽略，找到對應結點則 wn[k]--。遞歸結束後，可重構節點要重構。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
void Del(int& k, int p) {
  // 從以 k 為根子樹移除權值為 p 節點
  if (!k)
    return;
  else {
    if (w[k] == p) {
      if (wn[k]) wn[k]--;
    } else {
      if (w[k] < p)
        Del(rc[k], p);
      else
        Del(lc[k], p);
    }
    Calc(k);
    if (CanRbu(k)) Rbu(k);
  }
}

upper_bound

返回權值嚴格大於某值的最小名次。

到達空結點則返回 1，因為只有該子樹左邊的數均小於查找數才會遞歸至此。找到對應結點，則返回該節點所佔據的最後一個名次 + 1。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int MyUprBd(int k, int p) {
  // 在以 k 為根子樹中，大於 p 的最小數的名次
  if (!k)
    return 1;
  else if (w[k] == p && wn[k])
    return sz[lc[k]] + 1 + wn[k];
  else if (p < w[k])
    return MyUprBd(lc[k], p);
  else
    return sz[lc[k]] + wn[k] + MyUprBd(rc[k], p);
}

以下是反義函數，相當於採用 std::greater<> 比較，即返回權值嚴格小於某值的最大名次。查詢一個數的排名可以用 MyUprGrt(rt, x) + 1。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int MyUprGrt(int k, int p) {
  if (!k)
    return 0;
  else if (w[k] == p && wn[k])
    return sz[lc[k]];
  else if (w[k] < p)
    return sz[lc[k]] + wn[k] + MyUprGrt(rc[k], p);
  else
    return MyUprGrt(lc[k], p);
}

at

給定名次，返回該名次上的權值。到達空結點説明無此名次，找到對應結點則返回其權值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int MyAt(int k, int p) {
  // 以 k 為根的子樹中，名次為 p 的權值
  if (!k)
    return 0;
  else if (sz[lc[k]] < p && p <= sz[lc[k]] + wn[k])
    return w[k];
  else if (sz[lc[k]] + wn[k] < p)
    return MyAt(rc[k], p - sz[lc[k]] - wn[k]);
  else
    return MyAt(lc[k], p);
}

前驅後繼

以上兩種功能結合即可。

1
2
3
int MyPre(int k, int p) { return MyAt(k, MyUprGrt(k, p)); }

int MyPost(int k, int p) { return MyAt(k, MyUprBd(k, p)); }
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, 0xis-cn
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用