期望平衡，即弱平衡

背景知识

1. 二叉搜索树BST

BST

2. 堆Heap

Heap

操作

  1. 插入
  2. 删除
  3. 找前驱/后继
  4. 找最大/最小
  5. 求某个值的排名
  6. 求排名是k的数是哪个
  7. 找比某个数小的最大值
  8. 找比某个数大的最小值

结构定义

  1. Node {
  2.      int l, r;
  3.     // key指二叉搜索树中的值，val指堆中的值(随机值)，两个同时满足要求
  4.     int key, val;
  5. }

这样就能唯一确定一个二叉搜索树。

插入

  1. 直接插入至叶节点，赋随机值val
  2. 旋转操作(左旋zag/右旋zig)，类似于堆的pushup

删除

  1. 找到目标节点
  2. 通过不断左旋或右旋降低节点高度直至叶节点
  3. 删除目标节点

模板

AcWing 253. 普通平衡树

  1. // 省略IO
  2. public class Main {
  3.     static IntReader in;
  4.     static FastWriter out;
  5.     static String INPUT = "";
  7.     static class Node {
  8.         int l, r;
  9.         int key, val;
  10.         int cnt, size;
  11.     }
  12.     static final int INF = (int)(1e8), N = 100010;
  13.     static Node[] tr = new Node[N];
  14.     static int n, idx;
  15.     static Random random = new Random();
  16.     static void solve() {
  17.         n = ni();
  18.         int root = build();
  19.         for (int i = 1; i <= n; i++) {
  20.             int op = ni(), x = ni();
  21.             if (op == 1)
  22.                 root = insert(root, x);
  23.             else if (op == 2) 
  24.                 root = delete(root, x);
  25.             else if (op == 3)
  26.                 out.println(getRank(root, x) - 1);
  27.             else if (op == 4)
  28.                 out.println(getKey(root, x + 1));
  29.             else if (op == 5)
  30.                 out.println(getPrev(root, x));
  31.             else if (op == 6)
  32.                 out.println(getNext(root, x));
  33.         }
  34.     }
  36.     static int getNext(int u, int x) {
  37.         if (u == 0) return INF;
  38.         if (tr[u].key <= x)
  39.             return getNext(tr[u].r, x);
  40.         else
  41.             return Math.min(tr[u].key, getNext(tr[u].l, x));
  42.     }
  44.     static int getPrev(int u, int x) {
  45.         if (u == 0) return -INF;
  46.         if (tr[u].key >= x)
  47.             return getPrev(tr[u].l, x);
  48.         else
  49.             return Math.max(tr[u].key, getPrev(tr[u].r, x));
  50.     }
  52.     static int getKey(int u, int rank) {
  53.         if (u == 0) return 0;
  55.         if (tr[tr[u].l].size >= rank)
  56.             return getKey(tr[u].l, rank);
  57.         else if (tr[tr[u].l].size + tr[u].cnt >= rank)
  58.             return tr[u].key;
  59.         else
  60.             return getKey(tr[u].r, rank - tr[u].cnt - tr[tr[u].l].size);
  61.     }
  63.     static int getRank(int u, int key) {
  64.         if (u == 0) return 0;
  65.         if (tr[u].key == key) {
  66.             return tr[tr[u].l].size + 1;
  67.         } else if (tr[u].key > key) {
  68.             return getRank(tr[u].l, key);
  69.         } else {
  70.             return tr[tr[u].l].size + tr[u].cnt + getRank(tr[u].r, key);
  71.         }
  72.     }
  74.     static int delete(int u, int key) {
  75.         if (u == 0) {
  76.             return 0;
  77.         }
  79.         if (tr[u].key == key) {
  80.             if (tr[u].cnt > 1)
  81.                 tr[u].cnt--;
  82.             else if (tr[u].l != 0 || tr[u].r != 0) {
  83.                 if (tr[u].r == 0 || tr[u].l != 0 && tr[tr[u].l].val > tr[tr[u].r].val) {
  84.                     u = zig(u);
  85.                     tr[u].r = delete(tr[u].r, key);
  86.                 } else {
  87.                     u = zag(u);
  88.                     tr[u].l = delete(tr[u].l, key);
  89.                 }
  90.             } else return 0;
  91.         } else if (tr[u].key > key) {
  92.             tr[u].l = delete(tr[u].l, key);
  93.         } else {
  94.             tr[u].r = delete(tr[u].r, key);
  95.         }
  96.         pushup(u);
  97.         return u;
  98.     }
  100.     static int insert(int u, int key) {
  101.         if (u == 0) {
  102.             int p = createNode(key);
  103.             return p;
  104.         }
  106.         if (tr[u].key == key) {
  107.             tr[u].cnt++;
  108.         } else if (tr[u].key > key) {
  109.             tr[u].l = insert(tr[u].l, key);
  110.             if (tr[u].val < tr[tr[u].l].val)
  111.                 u = zig(u);
  112.         } else {
  113.             tr[u].r = insert(tr[u].r, key);
  114.             if (tr[u].val < tr[tr[u].r].val)
  115.                 u = zag(u);
  116.         }
  117.         pushup(u);
  118.         return u;
  119.     }
  122.     static void pushup(int u) {
  123.         tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
  124.     }
  126.     static int zag(int u) {
  127.         int right = tr[u].r;
  128.         tr[u].r = tr[right].l;
  129.         tr[right].l = u;
  130.         pushup(u);
  131.         pushup(right);
  132.         return right;
  133.     }
  134.     static int zig(int u) {
  135.         int left = tr[u].l;
  136.         tr[u].l = tr[left].r;
  137.         tr[left].r = u;
  138.         pushup(u);
  139.         pushup(left);
  140.         return left;
  141.     }
  143.     static int build() {
  144.         tr[0] = new Node();
  145.         int root = createNode(-INF), right = createNode(INF);
  146.         tr[root].r = right;
  147.         pushup(root);
  148.         if (tr[root].val < tr[right].val)
  149.             root = zag(root);
  150.         return root;
  151.     }
  153.     static int createNode(int x) {
  154.             ++idx;
  155.             tr[idx] = new Node();
  156.             tr[idx].key = x;
  157.             tr[idx].val = random.nextInt(2 * INF) + 1;
  158.             tr[idx].size = tr[idx].cnt = 1;
  159.             return idx;
  160.     }
  162.     public static void main(String[] args) throws Exception {
  163.         in = INPUT.isEmpty() ? new IntReader(System.in) : new IntReader(new ByteArrayInputStream(INPUT.getBytes()));
  164.         out = new FastWriter(System.out);
  165.         solve();
  166.         out.flush();
  167.     }
  168. }