JZTXT

平衡树

发布时间 2023-10-11 19:16:54作者: JiCanDuck

平衡树真的恶心死了！！！！！！好烦啊，又臭又长。

有很多种平衡树，替罪羊, treap，fhq, slpay。这里就说 splay， 和 bst 和 替罪羊 了，因为其他我都不会（悲

先说二叉排序树（二叉搜索树）， 他的关系就是 左子树所有节点 < 根节点 < 右子树所有节点。也就是说，按照中序遍历可以找到有序序列。

这个时候我们就可以增删改（删了再加入）查了！

查找 通过搜索，发现如果这个节点等于自己，cnt++, 小于自己往左搜索，大于自己往右边搜索

比如说我们要增加，搜索，如果发现没有，就新增节点。

删除， 找到位置（同上）cnt--。

这个时候就发现一个很严重的问题，它的复杂度是树高，就有可能变成一条链，复杂度瞬间变成 \(O(n)\) (泰裤辣)。

平衡树要来了！

平衡树还有几个功能

  1. 要求排名
  2. 按照排名查数
  3. 前驱后继

替罪羊的思路就此诞生。 如果发现不平衡，就重构。

平衡的定义是非0节点占全部的 M% 以内，且左节点的个数在 右节点的 M% 一内。

发现不平衡后就把它变成线性的，再按照贪心思路，每次折半重构。

M 在 70 ~ 75 为最佳

代码就不贴了，因为很丑。

接下来就是 splay 了

splay的主要思路就是操作的数都要旋转到树顶端

这个时候就要提到左旋和右旋了。其实就是传统的左旋和右旋，还是讲一下吧。

如图是左旋，右旋就是反过来，将x往上面旋，只需要看x是左儿子，还是右儿子就可以了。

然而，无脑的旋转会被善良的出题人卡掉。

所以，我们就要牵扯到祖宗——爸爸的爸爸叫什么（

两种情况，第一种，如下图

先旋转自己，再旋转自己。

第二种，如下图

先转父亲，再转自己。

然后就是紧张刺激的写代码环节了！

bool check(int x) {
  return a[a[x].fa].ch[0] != x;
}

写一个函数判断是做儿子(0)还是右儿子(1)。

void push_up(int rt) {
  a[rt].size = a[a[rt].ch[0]].size + a[a[rt].ch[1]].size + a[rt].cnt;
}

更新自己，记得加上自己的个数。

void Add(int x, int y, bool f) { 
  a[y].ch[f] = x;
  a[x].fa = y;
}

x接在y的（f ？ "右儿子" : "左儿子"）上。

正片，开始。

如果x是左儿子，就左旋，否则就是右旋，这样就可以简单轻松的完成自动的完成旋转了(dig, zig害人啊)

void rotate(int x) {
  int y = a[x].fa, z = a[y].fa, d = check(x), w = a[x].ch[d ^ 1];
  Add(w, y, d);
  Add(x, z, check(y));
  Add(y, x, d ^ 1);
  push_up(y), push_up(x);
}

单次旋转函数，将x向上旋转。

void splay(int x, int p = 0) {
  for (int f = a[x].fa; f = a[x].fa, f != p; rotate(x)) {
    if (a[f].fa != p) {
      if (check(f) == check(x)) {
        rotate(f);
      } else {
        rotate(x);
      }
    }
  }
  if (p == 0) Rt = x;
}

多次旋转函数，将 x 旋顶。

void find(int x) {
  int p = Rt;
  while (a[p].ch[x > a[p].v] && x != a[p].v) {
    p = a[p].ch[x > a[p].v];
  }
  splay(p);
}

查找并旋转到顶。

void insert(int x) {
  int p = Rt, fa = 0;
  while (p && x != a[p].v) {
    fa = p;
    p = a[p].ch[x > a[p].v];
  }
  if (p)
    a[p].cnt++;
  else {
    p = ++cnt;
    if (fa) a[fa].ch[x > a[fa].v] = p;
    a[p] = MakeSplay(x, fa);
  }
  splay(p);
}

找到，如果已经有了就cnt++，否则添加。

int pre_suc(int x, int f) {
  find(x);
  if (!f && a[Rt].v < x || f && a[Rt].v > x) return Rt;
  int p = a[Rt].ch[f];
  while (a[p].ch[f ^ 1]) {
    p = a[p].ch[f ^ 1];
  }
  return p;
}

前驱0， 后驱1。先旋转到顶，然后查找。

注意了，删除不一样

void remove(int x) {
  int last = pre_suc(x, 0), next = pre_suc(x, 1);
  splay(last), splay(next, last);
  int p = a[next].ch[0];
  if (a[p].cnt > 1) {
    a[p].cnt--;
    splay(p);
  } else {
    a[next].ch[0] = 0;
    push_up(next), push_up(last);
  }
}

先把x的前驱旋转到顶，再将后继旋到前驱的后面。那么后继的左儿子就是 x，而且 x 没有儿子。

int rank1(int x) {
  int p = Rt;
  while (1) {
    if (a[p].ch[0] && a[a[p].ch[0]].size >= x) {
      p = a[p].ch[0];
    } else if (x > a[a[p].ch[0]].size + a[p].cnt) {
      x -= a[a[p].ch[0]].size + a[p].cnt;
      p = a[p].ch[1];
    } else {
      return p;
    }
  }
}

查排名为x的数，不多解释。

总代码来咯。

等等等等，还要加入最大值和最小值哦，不然有可能会没有前驱和后继哦（亲身

#include <iostream>

using namespace std;

const int kMaxN = 1e5 + 5;

int Rt, cnt;

struct Splay {
  int v, fa, cnt, size, ch[2];
} a[kMaxN];

Splay MakeSplay(int v, int fa) {
  Splay P;
  P.v = v, P.fa = fa, P.cnt = P.size = 1, P.ch[0] = P.ch[1] = 0;
  return P;
}

bool check(int x) {
  return a[a[x].fa].ch[0] != x;
}

void push_up(int rt) {
  a[rt].size = a[a[rt].ch[0]].size + a[a[rt].ch[1]].size + a[rt].cnt;
}

void Add(int x, int y, bool f) {
  a[y].ch[f] = x;
  a[x].fa = y;
}

void rotate(int x) {
  int y = a[x].fa, z = a[y].fa, d = check(x), w = a[x].ch[d ^ 1];
  Add(w, y, d);
  Add(x, z, check(y));
  Add(y, x, d ^ 1);
  push_up(y), push_up(x);
}

void splay(int x, int p = 0) {
  for (int f = a[x].fa; f = a[x].fa, f != p; rotate(x)) {
    if (a[f].fa != p) {
      if (check(f) == check(x)) {
        rotate(f);
      } else {
        rotate(x);
      }
    }
  }
  if (p == 0) Rt = x;
}

void find(int x) {
  int p = Rt;
  while (a[p].ch[x > a[p].v] && x != a[p].v) {
    p = a[p].ch[x > a[p].v];
  }
  splay(p);
}

void insert(int x) {
  int p = Rt, fa = 0;
  while (p && x != a[p].v) {
    fa = p;
    p = a[p].ch[x > a[p].v];
  }
  if (p)
    a[p].cnt++;
  else {
    p = ++cnt;
    if (fa) a[fa].ch[x > a[fa].v] = p;
    a[p] = MakeSplay(x, fa);
  }
  splay(p);
}

int pre_suc(int x, int f) {
  find(x);
  if (!f && a[Rt].v < x || f && a[Rt].v > x) return Rt;
  int p = a[Rt].ch[f];
  while (a[p].ch[f ^ 1]) {
    p = a[p].ch[f ^ 1];
  }
  return p;
}

void remove(int x) {
  int last = pre_suc(x, 0), next = pre_suc(x, 1);
  splay(last), splay(next, last);
  int p = a[next].ch[0];
  if (a[p].cnt > 1) {
    a[p].cnt--;
    splay(p);
  } else {
    a[next].ch[0] = 0;
    push_up(next), push_up(last);
  }
}

int rank1(int x) {
  int p = Rt;
  while (1) {
    if (a[p].ch[0] && a[a[p].ch[0]].size >= x) {
      p = a[p].ch[0];
    } else if (x > a[a[p].ch[0]].size + a[p].cnt) {
      x -= a[a[p].ch[0]].size + a[p].cnt;
      p = a[p].ch[1];
    } else {
      return p;
    }
  }
}

int main() {
  insert(0x3f3f3f3f);
  insert(-0x3f3f3f3f);
  int n, op, x;
  for (cin >> n; n; n--) {
    cin >> op >> x;
    switch (op) {
      case 1:
        insert(x);
        break;
      case 2:
        remove(x);
        break;
      case 3:
        find(x), cout << a[a[Rt].ch[0]].size << '\n';
        break;
      case 4:
        cout << a[rank1(x + 1)].v << '\n';
        break;
      case 5:
        cout << a[pre_suc(x, 0)].v << '\n';
        break;
      case 6:
        cout << a[pre_suc(x, 1)].v << '\n';
        break;
    }
  }
  return 0;
}