WBLT

WBLT，全称 Weight Balanced Leafy Tree，一种不常见的平衡树写法，但是具有常数较小，可以当做可并堆使用的优点。

类似于 WBT（weight-balanced trees），WBLT 体现了 leafy 的性质，即节点多，怎么多呢？

对于 n 个数，不同于 treap 等，WBLT 会建立 2n 个节点，每个节点的权值为其右儿子的权值，且右儿子的权值大于等于左儿子

每次插入，类似于堆，逐次向下交换并向上 pushup 更新即可，删除也是同理

当然，如果输入数据递增或递减，WBLT 会退化成链状，于是我们采用旋转来维护平衡。

因为 WBLT 同时满足堆的性质，我们可以用它来实现堆和可并堆。

而在旋转的过程中，会产生很多垃圾节点，我们采用垃圾回收的方式就可以回收废弃节点，将建立节点的操作稍作修改即可。

附上普通平衡树代码：

  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
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
#include <cstdio>
#include <iostream>

using namespace std;

const int maxn = 400005;

const int ratio = 5;
int n, cnt, fa, root;
int size[maxn], ls[maxn], rs[maxn], val[maxn];

void newnode(int &cur, int v) {
  cur = ++cnt;
  size[cur] = 1;
  val[cur] = v;
}
void copynode(int x, int y) {
  size[x] = size[y];
  ls[x] = ls[y];
  rs[x] = rs[y];
  val[x] = val[y];
}
void merge(int l, int r) {
  size[++cnt] = size[l] + size[r];
  val[cnt] = val[r];
  ls[cnt] = l, rs[cnt] = r;
}
void rotate(int cur, bool flag) {
  if (flag) {
    merge(ls[cur], ls[rs[cur]]);
    ls[cur] = cnt;
    rs[cur] = rs[rs[cur]];
  } else {
    merge(rs[ls[cur]], rs[cur]);
    rs[cur] = cnt;
    ls[cur] = ls[ls[cur]];
  }
}
void maintain(int cur) {
  if (size[ls[cur]] > size[rs[cur]] * ratio)
    rotate(cur, 0);
  else if (size[rs[cur]] > size[ls[cur]] * ratio)
    rotate(cur, 1);
  if (size[ls[cur]] > size[rs[cur]] * ratio)
    rotate(ls[cur], 1), rotate(cur, 0);
  else if (size[rs[cur]] > size[ls[cur]] * ratio)
    rotate(rs[cur], 0), rotate(cur, 1);
}
void pushup(int cur) {
  if (!size[ls[cur]]) return;
  size[cur] = size[ls[cur]] + size[rs[cur]];
  val[cur] = val[rs[cur]];
}
void insert(int cur, int x) {
  if (size[cur] == 1) {
    newnode(ls[cur], min(x, val[cur]));
    newnode(rs[cur], max(x, val[cur]));
    pushup(cur);
    return;
  }
  maintain(cur);
  insert(x > val[ls[cur]] ? rs[cur] : ls[cur], x);
  pushup(cur);
}
void erase(int cur, int x) {
  if (size[cur] == 1) {
    cur = ls[fa] == cur ? rs[fa] : ls[fa];
    copynode(fa, cur);
    return;
  }
  maintain(cur);
  fa = cur;
  erase(x > val[ls[cur]] ? rs[cur] : ls[cur], x);
  pushup(cur);
}
int find(int cur, int x) {
  if (size[cur] == x) return val[cur];
  maintain(cur);
  if (x > size[ls[cur]]) return find(rs[cur], x - size[ls[cur]]);
  return find(ls[cur], x);
}
int rnk(int cur, int x) {
  if (size[cur] == 1) return 1;
  maintain(cur);
  if (x > val[ls[cur]]) return rnk(rs[cur], x) + size[ls[cur]];
  return rnk(ls[cur], x);
}
int main() {
  scanf("%d", &n);
  newnode(root, 2147383647);  // 使根不改变
  while (n--) {
    int s, a;
    scanf("%d %d", &s, &a);
    if (s == 1) insert(root, a);
    if (s == 2) erase(root, a);
    if (s == 3) printf("%d\n", rnk(root, a));
    if (s == 4) printf("%d\n", find(root, a));
    if (s == 5) printf("%d\n", find(root, rnk(root, a) - 1));
    if (s == 6) printf("%d\n", find(root, rnk(root, a + 1)));
  }
  return 0;
}
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：hsfzLZH1, cesonic
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论