splay(平衡树)

【引入】

先来看一道题:营业额统计

显然,对于每一天的营业额只要找出已有的营业额与其差值最小的就行了。那么便可以用二叉搜索树来实现这样的查找。

如果一棵二叉树如同下图,为一条链,那么每次查找的时间复杂度就和暴力没有什么差了。

我们可以发现,下图的二叉树与上图的二叉树是等价的,但下图的深度比上图的深度少了2,这样查找的时间复杂度也就减少了,那如何将上图的二叉树转化成下图的呢?splay便可以实现。

【思想】

【rotate】

这是原来的树。为了减小深度,我们把B结点旋转到根结点,那么A结点就成了B结点的儿子。由二叉树的性质我们可以知道B<E<A<C,那么可以得到如下的一棵新树。

rotate代码如下:


1
2
3
4
5
6
7
8
9
10
11
void Rotate(int x)
{
    int fa = tree[x].fat, s = (x == tree[fa].son[1]), s1 = (fa == tree[tree[fa].fat].son[1]);
    tree[tree[x].son[s^1]].fat = fa;
    tree[fa].son[s] = tree[x].son[s^1];
    if (tree[fa].fat)
        tree[tree[fa].fat].son[s1] = x;
    tree[x].fat = tree[fa].fat;
    tree[x].son[s^1] = fa;
    tree[fa].fat = x;
}

【splay】

splay则是rotate的拓展,因为对于一个点,只进行一次rotate显然并不会有多少优化,只有将其旋转至根结点才方便之后的操作。

splay的过程中需要分类讨论,如果是三点一线的话(x,x的父亲,x的祖父)需要先rotate x的父亲,否则需要先rotate x本身(否则会形成单旋使平衡树失衡)。


1
2
3
4
5
6
7
8
9
10
void splay(int x)
{
    for (int y; (y = tree[x].fat) > 0;)
    {
        if (tree[y].fat)
            Rotate((tree[tree[y].fat].son[1] == y)^(tree[y].son[1] == x) ? y : x);
        Rotate(x);
    }
    root = x;
}

【insert/find/delete】

插入、查找、删除的操作于普通平衡树一样。只是在最后要将操作的点旋转到根结点。

插入:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void ins(int va)
{
    int x = root;
    if (!tree[x].val)
    {
        tree[++tot].val = va;
        tree[tot].tot = tot;
        root = tot;
        return ;
    }
    for (;tree[x].son[va > tree[x].val] && tree[x].val != va; x = tree[x].son[va > tree[x].val]);
    if (tree[x].val == va)
    {
        tree[x].cnt++;
        return ;
    }
    tree[++tot].val = va;
    tree[tot].fat = x;
    tree[x].son[va > tree[x].val] = tot;
    splay(tot);
}

查找:


1
2
3
4
5
6
void Find(int va)
{
    int x = root;
    for (;tree[x].val != va; x = tree[x].son[va > tree[x].val]);
    splay(x);
}

查找前驱/后继:


1
2
3
4
5
6
7
int Find_max(int x)
{
    int y = tree[x].son[0];
    for (;tree[y].son[1]; y = tree[y].son[1]);
        splay(y)
    return y;
}

删除:

删除的操作相对麻烦。如果其只有一个儿子,那么将它的儿子当作根结点就可以。否则,要先找出当前结点的前驱/后继,将其旋转到根结点。那么要操作的结点一定是根的一个儿子,并且它只有一个儿子,于是只要将根的儿子指向要操作的结点的儿子即可。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void del(int x)
{
    if (tree[x].cnt > 1)
    {
        tree[x].cnt--;
        return ;
    }
    int l = (tree[x].son[0] != 0), r = (tree[x].son[1] != 0);
    if (!l && !r)
    {
        root = 0;
        return;
    }
    if (!l)
    {
        tree[tree[x].son[1]].fat = 0;
        root = tree[x].son[1];
        return ;
    }
    splay(Find_max(x));
    tree[root].son[1] = tree[x].son[1];
    if (r) tree[tree[x].son[1]].fat = root;
}

【总结】

splay是一种优化二叉查找的方法,所有的操作一定都满足二叉搜索树的性质。

完整代码:

继续阅读splay(平衡树)

BZOJ3224 Tyvj1728 普通平衡树

BZOJ3224

Tyvj1728

本题可以使用平衡树,线段树,甚至std::vector通过。

splay的话直接做就可以了。

对于1操作,直接插,注意无需重复插入同一数字,用cnt数组统计数字出现次数即可。

对于2操作,先将要删的点splay至根节点,然后分4种情况。1.若根节点的cnt值大于1,将其-1;2.若根节点的cnt值等于1且无左右子节点,清空整棵树;3.若根节点的cnt值等于1且左右子节点无其中一个,将根结点一直另一子节点;4.若根节点的cnt值等于1且左右子节点都存在,找出根节点的前驱,将其splay至根节点,即可删除原来的根节点。注意在2,3,4情况时处理好父子节点的关系。

对于3,4,5,6操作,应用类似普通二叉查找树的方法即可。注意在5,6操作中可能存在查询不在树中的数字。

继续阅读BZOJ3224 Tyvj1728 普通平衡树

BZOJ1588 [HNOI2002]营业额统计

BZOJ1588

splay。

把每天的营业额加入splay,查找前驱和后继,统计即可。

注意使用双旋的splay,因为单旋在链状树的情况下时间复杂度会退化。具体证明去问Tarjan。

也可使用其他平衡树或双向链表。双向链表的做法可参考 朱晨光《基本数据结构在信息学竞赛中的应用》。

继续阅读BZOJ1588 [HNOI2002]营业额统计