【模板】替罪羊树——SGT

Share

替罪羊树(SGT)，又叫重量平衡树，通过将不平衡的子树拍扁重构来保证整棵树的平衡。

本文已知有一个bug，尚未修改：SGT应有两个size，一个为子树节点个数，用于重构。一个为子树维护的值的个数，用于查询排名。本文将两个size混用，会导致某些数据下复杂度退化。即将更正……

常见的平衡树保证平衡的方式有旋转(Treap，Splay)，分割合并(fhq Treap)，还有暴力重构(SGT)。

本文采用数组模拟指针的方式来实现SGT。

节点

节点有记录父亲和不记录父亲两种方式，我这里为了节省空间使用不记录的，需要用到父亲的位置(rebuild)直接用指针来充当边就好了。

struct Node {
  Node() : key(0), left(NIL), right(NIL), cnt(0), size(0) {  }
  int key;//关键字
  int cnt;//当前节点个数
  int size;//当前子树大小
  int left;//左儿子下标
  int right;//右儿子下标
};

插入

我们先像BST一样在树上走路，找到插入的位置插进去。然后看其他人代码都是往上找不平衡的节点重构，而我推荐从根再走一遍来寻找重构节点，一是常数比较小，二是不用记录父亲。

void insert(int key) {
  //注意一下我的newNode(int)创建出来的节点cnt和size都是0，不可以直接退出。
  if(root == NIL) root = newNode(key);
  int now = root;
  while(true) {
    //在树上走路
    ++node[now].size;
    if(key < node[now].key) {
      if(node[now].left == NIL) {
        node[now].left = newNode(key);
      }
      now = node[now].left;
    } else if(node[now].key < key) {
      if(node[now].right == NIL) {
        node[now].right = newNode(key);
      }
      now = node[now].right;
    } else {
      //找到节点，退出
      ++node[now].cnt;
      break;
    }
  }
  int *son = &root;
  //使用指针来记录边，方便修改
  while(node[*son].key != key) {
    if(!balance(*son)) {
      //如果不平衡就重构
      rebuild(son);
      break;
    }
    if(key < node[*son].key) {
      son = &node[*son].left;
    } else if(node[*son].key < key) {
      son = &node[*son].right;
    }
  }
  return;
}

删除

SGT的删除也许是平衡树中的一股清流，不用做什么操作，只要把cnt设成0就行了。然后如果空节点个数大于了整棵树的一半，就把整棵树重构一下，并扔掉所有空节点。

void remove(int key) {
  int now = root;
  while(true) {
    //在树上走路
    --node[now].size;
    if(key < node[now].key) {
      now = node[now].left;
    } else if(node[now].key < key) {
      now = node[now].right;
    } else {
      --node[now].cnt;
      if(node[now].cnt == 0) {
        ++del_num;//记录树中有多少被删除的节点
      }
      break;
    }
  }
  if((del_num << 1) > node[root].size) {
    rebuild(&root);
  }
  return;
}

重构

SGT的精髓就是暴力重构（感觉有点怪），那么我们这就来讲一下怎么暴力重构

平衡

当一个节点不平衡的时候，我们就把这棵子树拍扁重构。

判断一个子树平不平衡的方式，我们选择让根节点的size乘以一个平衡因子alpha，如果比任何一个子树的size小，则认为他是不平衡的。

这个alpha是我们自己定的，在0.6~0.9之间效果较好，在0.5~0.6之间或0.9~1.0之间SGT的复杂度就会明显退化。我推荐你们在0.7~0.8之间选一个，我习惯使用0.75。
——igronemyk

判断平衡代码如下:

bool balance(int key) {
  //平衡返回true，不平衡返回false
  //BALANCE_SIZE即为alpha
  return (node[key].left == NIL ||
          node[key].size * BALANCE_SIZE >= (double)node[node[key].left].size) &&
          (node[key].right == NIL ||
          node[key].size * BALANCE_SIZE >= (double)node[node[key].right].size);
}

重构

重构子树分几步：

  1. 把子树拍扁成一个序列
  2. 按序列重建一棵完全平衡的树
  3. 把指向原来子树根节点的边指向新的子树根

拍扁

void recycle(int now, int &cnt, int *id) {
  //now 当前节点下标
  //cnt 拍扁后数组长度
  //id 拍扁后数组
  if(node[now].left != NIL) {
    recycle(node[now].left, cnt, id);
  }
  if(node[now].cnt > 0) {
    //如果当前节点不是被删除的节点就直接放到数组里
    id[++cnt] = now;
  } else {
    //否则就无视这个节点，并且让空节点个数-1
    --del_num;
  }
  if(node[now].right != NIL) {
    recycle(node[now].right, cnt, id);
  }
  return;
}

重构

int build(const int *arr, int left, int right) {//[left, right]
  const int mid = left + right >> 1;
  //mid就是当前节点的在数组中的位置
  node[arr[mid]].size = node[arr[mid]].cnt;
  if(mid - 1 >= left) {
    node[arr[mid]].left = build(arr, left, mid - 1);
    node[arr[mid]].size += node[node[arr[mid]].left].size;
  } else {
    node[arr[mid]].left = NIL;
  }
  if(mid + 1 <= right) {
    node[arr[mid]].right = build(arr, mid + 1, right);
    node[arr[mid]].size += node[node[arr[mid]].right].size;
  } else {
    node[arr[mid]].right = NIL;
  }
  return arr[mid];
  //返回当前子树的根节点
}

rebuild

void rebuild(int *son) {
  int now = *son;
  int len = 0;
  static int *id = new int[MAX_SGT_NODE_NUM];
  recycle(now, len, id);
  *son = build(id, 1, len);
  return;
}

其实SGT还是很简单的，把主要思想告诉大家其实大家都能自己写出来。

上一份完整的普通平衡树代码，加上主函数只有200行左右，还是很短的：

代码