分类：平衡树

【引入】

先来看一道题：营业额统计。

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

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

我们可以发现，下图的二叉树与上图的二叉树是等价的，但下图的深度比上图的深度少了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(平衡树)