Splay简易教程

Splay简易教程
简介
二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
左、右子树也分别为二叉排序树
同样的序列，因为排序不同，可能会生成不同的二叉排序树，查找效率性对就不一定了。如果是二叉排序树退化成一条链，效率就很低。
伸展树（Splay）是一种平衡二叉树，即优化后的二叉查找树。伸展树可以自我调整，这就要依靠伸展操作Splay(x,S)，使得提升效率。
变量定义
N：常量，节点个数。
ch[N][2]：二维数组，ch[x][0]代表x的左儿子，ch[x][1]代表x的右儿子。
val[N]：一维数组，val[x]代表x存储的值。
cnt[N]：一维数组，cnt[x]代表x存储的重复权值的个数。
par[N]：一维数组，par[x]代表x的父节点。
size[N]：一维数组，size[x]代表x子树下的储存的权值数（包括重复权值）。
各种操作
chk操作
辅助操作，查询一个节点位于其父节点的方向。

int chk(int x) {
    return ch[par[x]][1] == x;
}

pushup操作

辅助操作，更新size数组的值。

void pushup(int x) {
    size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x];
}

比如最开始的树是这样子的：

现在我们想把2号点搞到4号点的位置。
那么2下面的子树就有1,3,4,5。一种比较优秀的玩法是这样的：

那么我们可以考虑这么操作：

先把4→2的边改成4→3。
再把6→4的边改成6→2。
最后把2→3的边改成2→4。
第一次连边

第二次连边

第三次连边

连边前(原图)

旋转操作有四种。自行模拟后发现：

旋转后，父节点会将连向需旋转的该子节点的方向的边连向该子节点位于其父节点方向的反方向的节点。
令x = 该节点, y = par[x], k = chk(x), w = ch[x][k^1]，则ch[y][k] = w; par[w] = y;
旋转后，爷爷节点会将连向父节点的边连向需旋转的该节点。
ch[z][chk(y)] = x; par[x] = z;
旋转后，需旋转的该节点会将连向该子节点位于其父节点方向的反方向的子节点的边连向其父节点。
ch[x][k^1] = y; par[y] = x;
综合一下，得到下列代码(可见自然语言是多么的无力)：

void rotate(int x) {
    int y = par[x], z = par[y], k = chk(x), w = ch[x][k^1];
    ch[y][k] = w; par[w] = y;
    ch[z][chk(y)] = x; par[x] = z;
    ch[x][k^1] = y; par[y] = x;
    pushup(y); pushup(x);
}

伸展(splay)

将一个节点一路rotate到指定节点的儿子。
注意，如果该节点、该父节点和该爷爷节点「三点一线」，那么应该先旋转父节点。
此处进行的操作是将3 splay到根节点。

旋转父节点后

旋转自身后

并且注意处理爷爷节点已经是目标的情况。

void splay(int x, int goal = 0) {
    while (par[x] != goal) {
        int y = par[x], z = par[y];
        if (z != goal) {
            if (chk(x) == chk(y)) rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
    if (!goal) root = x;
}

find操作

辅助操作，将最大的小于等于x的数所在的节点splay到根。

void find(int x) {
    if (!root) return;
    int cur = root;
    while (ch[cur][x > val[cur]] && x != val[cur]) {
        cur = ch[cur][x > val[cur]];
    }
    splay(cur);
}

插入(insert)

从根节点开始，一路搜索下去。如果节点存在则直接自增cnt的值。否则新建节点并与父节点连边。
因为新建节点时可能会拉出一条链，所以新建节点后需要将该节点splay到根节点。沿途的rotate操作可以使平衡树恢复平衡。

void insert(int x) {
    int cur = root, p = 0;
    while (cur && val[cur] != x) {
        p = cur;
        cur = ch[cur][x > val[cur]];
    }
    if (cur) {
        cnt[cur]++;
    } else {
        cur = ++ncnt;
        if (p) ch[p][x > val[p]] = cur;
        ch[cur][0] = ch[cur][1] = 0;
        val[cur] = x; par[cur] = p;
        cnt[cur] = size[cur] = 1;
    }
    splay(cur);
}

查询k大(kth)

从根节点开始，一路搜索下去。每次判断要走向哪个子树。注意考虑重复权值。

int kth(int k) {
    int cur = root;
    while (1) {
        if (ch[cur][0] && k <= size[ch[cur][0]]) {
            cur = ch[cur][0];
        } else if (k > size[ch[cur][0]] + cnt[cur]) {
            k -= size[ch[cur][0]] + cnt[cur];
            cur = ch[cur][1];
        } else {
            splay(cur);
            return cur;
        }
    }
}

查询rank(rank)

并不需要专门写操作。将该节点find到根后返回左子树的权值数即可。

find(x);
printf("%d\n", size[ch[root][0]]);

前驱(pre)

将该节点find到根后返回左子树最右边的节点即可。

int pre(int x) {
    find(x);
    if (val[root] < x) return root;
    int cur = ch[root][0];
    while (ch[cur][1]) {
        cur = ch[cur][1];
    }
    splay(cur);
    return cur;
}

后继(succ)

同理，返回右子树最左边的节点即可。

int succ(int x) {
    find(x);
    if (val[root] > x) return root;
    int cur = ch[root][1];
    while (ch[cur][0]) {
        cur = ch[cur][0];
    }
    splay(cur);
    return cur;
}

删除(remove)

显然，任何一个数的前驱和后继之间只有它自身。
令该点的前驱为last，后继为next。
那么可以考虑把前驱splay到根，后继splay到前驱的右儿子，那么后继的左儿子就是要删除的点。

最后判特判权值数大于的情况即可。

void remove(int x) {
    int last = pre(x), next = succ(x);
    splay(last); splay(next, last);
    int del = ch[next][0];
    if (cnt[del] > 1) {
        cnt[del]--;
        splay(del);
    }
    else ch[next][0] = 0;
    pushup(next), pushup(x);
}

二叉搜索树BST NOI级提高级

Splay简易教程

相关

标签