Scapegoat Tree: A Brief Tutorial

重量平衡树:BST

重量平衡树首先是平衡树,其次保证形态的同时优先保证了子树的重量(size)是期望优的。
除了替罪羊树一个例子是Treap。
相关概念可参考[1]。

重量平衡树:The Satisfying Case

Not only what general BST satisifying, but also

  1. maintaining the value set of subtrees
  2. maintaining (almost every) union sets of the info sets of the subtrees on a node
  3. ...

In general BSTs, when we rotate the tree, we need to recalculate the union sets, which costs $ O(n) $ time.

Scapegoat Tree: The Definition

Balanced Factor: $ \alpha $

我们定义一个常量 $ \alpha \in (0,1) $ ,$ size(o) $指以$ o $ 为根子树有效结点个数,则称满足 $ size(lc(o)) > size(o) \cdot \alpha \lor size(rc(o)) > size(o) \cdot \alpha $ 的节点是不平衡的
实现中一般选取alpha = 0.75

Keeping Balance: Reconstruction

由于我们不使用旋转操作保证整棵树的平衡,所以我们考虑对所有不平衡的节点,我们暴力重构以其为根的子树。容易发现,当所有节点均为平衡的时,整棵树满足 BST 的定义,也即期望深度为 $ O(\lg n) $。

Erasing Node: Lazy-tagging

对于每次删除节点的操作,我们不直接从原树中删除,而是使用(bool)exist进行标记。当一个点 $ size < total \cdot \alpha $时,也认为其不平衡的,暴力重构。

The Complexity: Time/Space

树的期望深度是 $ \log_{1/\alpha} n $的。所以仍然保证其他操作复杂度仍为对数级别。
使用内存回收的话,空间也是 $ O(n) $ 级别的。

Scapegoat Tree: The Code (Template)

BZOJ 3224(3948 kb 304 ms)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}

const double alpha = 0.75;
const int maxn = 1e5 + 100;
struct Node
{
    int ch[2];
    int v, size, total;
    bool exist;
} pool[maxn];
int pcnt = 1, tag, root = 0;
int sta[maxn], st = 0;
#define lc(o) (pool[o].ch[0])
#define rc(o) (pool[o].ch[1])
#define v(o) (pool[o].v)
#define size(o) (pool[o].size)
#define total(o) (pool[o].total)
#define exist(o) (pool[o].exist)
inline void maintain(int o)
{
    size(o) = size(lc(o)) + size(rc(o)) + exist(o);
    total(o) = total(lc(o)) + total(rc(o)) + 1;
}
inline bool check(int o)
{
    return (double)total(o) * alpha < (double)total(lc(o)) || (double)total(o) * alpha < (double)total(rc(o));
}
void ins(int &o, int x)
{
    if(!o)
    { 
        if(st) o = sta[--st];
        else o = pcnt++;
        pool[o] = (Node){{0, 0}, x, 1, 1, true};
    }
    else
    {
        if(x <= pool[o].v) ins(lc(o), x);
        else ins(rc(o), x);
        maintain(o); if(check(o)) tag = o;
    }
}
int a[maxn], ac = 0;
void deconstruct(int o, bool first = true)
{
    if(!o) return;
    deconstruct(lc(o), false);
    if(exist(o)) a[ac++] = pool[o].v;
    deconstruct(rc(o), false);
    if(!first) sta[st++] = o;
}
void construct(int &o, int L = 1, int R = ac - 1)
{
    if(L > R) return;
    int M = (L + R) >> 1;
    if(!o && st) o = sta[--st];
    else if(!o) o = pcnt++;
    pool[o] = (Node){{0, 0}, a[M], 1, 1, true};
    construct(lc(o), L, M - 1), construct(rc(o), M + 1, R), maintain(o);
}
void reconstruct(int &o)
{
    ac = 1;
    deconstruct(o);
    construct(o);
}
inline void insert(int x){tag = 0; ins(root, x); if(tag) reconstruct(tag);}
void del(int o, int x)
{
    if(!o) return;
    if(exist(o) && size(lc(o)) + exist(o) == x)
    {
        exist(o) = false, maintain(o);
        return;
    }
    if(size(lc(o)) + exist(o) < x)
    {
        del(rc(o), x - size(lc(o)) - exist(o));
    }
    else
    {
        del(lc(o), x);
    }
    maintain(o);
}
int Rank(int x)
{
    int o = root, ans = 1;
    while(o)
    {
        if(v(o) >= x) o = lc(o);
        else ans += size(lc(o)) + exist(o), o = rc(o);
    }
    return ans;
}
int kth(int x)
{
    int o = root;
    while(o)
    {
        if(size(lc(o)) + exist(o) == x && exist(o)) return v(o);
        if(size(lc(o)) + exist(o) >= x) o = lc(o);
        else x -= size(lc(o)) + exist(o), o = rc(o);
    }
}
inline void del(int x)
{
    del(root, Rank(x));
    if((double)size(root) < alpha * (double)total(root)) reconstruct(root);
}
int main()
{
    int n; read(n);
    while(n--)
    {
        int opt, x; read(opt, x);
        if(opt == 1) insert(x);
        else if(opt == 2) del(x);
        else if(opt == 3) printf("%d\n", Rank(x));
        else if(opt == 4) printf("%d\n", kth(x));
        else if(opt == 5) printf("%d\n", kth(Rank(x) - 1));
        else printf("%d\n", kth(Rank(x + 1)));
    }
    return 0;
}

The Advantages

对于一类在线添加节点,而树的形态相对固定,且子树信息难以高效统计(合并,但可以高效添加),替罪羊是一个很好的选择。
例子:后缀平衡树和动态点分治的“重心树”。

The Disadvantages

对于连续序列的操作,替罪羊树显得不在行。
它不支持抽取一段连续的区间并对其进行统计/修改/翻转等旋转平衡树常见操作。

参考 References

[1] 陈立杰.重量平衡树和后缀平衡树在信息学奥赛中的运用.2013年信息学奥林匹克中国国家队候选队员论文.2013

标签: none

添加新评论