算法学习
7 minutes read (About 1106 words)

算法学习-splay伸展树

本文部分内容转载自 OI Wiki Splay

$\LaTeX$ 就先咕着吧……有时间慢慢搞

概述

Splay是一种二叉查找树，它通过不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链，它由 Daniel Sleator 和 Robert Tarjan 发明。

结构

节点维护信息

  • root 根节点编号
  • cnt 节点个数
  • node[] 节点内部信息
    • fa 父亲
    • ch[0/1] 左右儿子编号
    • val 节点权值
    • cnt 权值出现次数
    • sum 子树大小
1
2
3
4
struct Node {
    int fa, ch[2], val, cnt, sum;
}node[MAXN];
int root, cnt;

基本操作

  • update(u) 在改变节点位置后，将节点u的sum值更新
  • identify(u) 判断节点u是父亲的左儿子还是右儿子
  • clear(u) 销毁节点u
1
2
3
4
5
6
7
8
9
void update(int u) {
    node[u].sum = node[u].cnt + node[node[u].ch[0]].sum + node[node[u].ch[1]].sum;
}
bool identify(int u) {
    return u == node[node[u].fa].ch[1];
}
void clear(int u) {
    node[u].fa = node[u].ch[0] = node[u].ch[1] = node[u].val = node[u].cnt = node[u].sum = 0;
}

连接操作

  • connect(u, f, p) 将u连接在f的下方，连接方向为p
1
2
3
4
void connect(int u, int f, int p) {
    node[u].fa = f;
    node[f].ch[p] = u;
}

旋转操作

分析咕咕咕

1
2
3
4
5
6
7
8
9
10
11
void rotate(int x) {
    int y = node[x].fa;
    int r = node[y].fa;
    int rp = identify(y);
    int yp = identify(x);
    int b = node[x].ch[yp ^ 1];
    connect(b, y, yp);
    connect(y, x, yp ^ 1);
    connect(x, r, rp);
    update(y), update(x);
}

旋转需要保证：

  • 平衡树的中序遍历不变（不能破坏BST的性质）
  • 受影响的节点维护的信息依然正确有效
  • root必须指向旋转后的根节点

如果你能看到这行字，就说明图片爆炸了

如果你能看到这行字，就说明图片爆炸了

具体分析旋转步骤（假设需要旋转的节点为x，其父亲为y，以右旋为例）：

  1. 将y的左儿子指向x的右儿子，且x的右儿子的父亲指向y
  2. 将x的右儿子指向y，且y的父亲指向x
  3. 如果原来的y还有父亲z，那么把z的某个儿子（原来y所在的儿子位置）指向x，且x的父亲指向z
1
2
3
4
5
6
7
8
9
10
11
void rotate(int x) {
    int y = node[x].fa, z = node[y].fa, p = identify(x);
    node[y].ch[p] = node[x].ch[p ^ 1];
    node[node[x].ch[p ^ 1]].fa = y;
    node[x].ch[p ^ 1] = y;
    node[y].fa = x;
    node[x].fa = z;
    if (z) node[z].ch[y == node[z].ch[1]] = x;
    update(y);
    update(x);
}

Splay 操作

Splay规定：每访问一个节点后都要强制将其旋转到根节点。此时旋转操作具体分为6种情况讨论（其中x为需要旋转到根的节点）

分析咕咕咕

1
2
3
4
5
void splay(int x) {
    for (int f = node[x].fa; f = node[x].fa, f; rotate(x)) 
        if (node[f].fa && identify(x) == identify(f)) rotate(f);
   	root = x;
}

插入操作

分析咕咕咕

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void insert(int val) {
    if (root == 0) {
        node[++cnt].val = val;
        node[cnt].cnt++;
        root = cnt;
        update(root);
        return;
    }
    int cur = root, f = 0;
    while (1) {
        if (node[cur].val == val) {
            node[cur].cnt++;
            update(cur);
            update(f);
            splay(cur);
            break;
        }
        f = cur, cur = node[cur].ch[node[cur].val < k];
        if (cur == 0) {
            node[++cnt].val = val;
            node[cnt].cnt++;
            node[cnt].fa = f;
            node[f].ch[node[f].val < k] = cnt;
            update(cnt);
            update(f);
            splay(cnt);
            break;
        }
    }
}

查询x的排名

分析咕咕咕

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int queryid(int val) {
    int ans = 0, cur = root;
    while (1) {
        if (val < node[cur].val) cur = node[cur].ch[0];
        else {
            ans += node[node[cur].ch[0]].sum;
            if (val == node[cur].val) {
                splay(cur);
                return ans + 1;
            }
            ans += node[cur].cnt;
            cur = node[cur].ch[1];
        }
    }
}

查询排名为k的数

分析咕咕咕

1
2
3
4
5
6
7
8
9
10
11
int queryrid(int k) {
    int cur = root;
    while (1) {
        if (node[cur].ch[0] && k <= node[node[cur].ch[0]].sum) cur = node[cur].ch[0];
        else {
            k -= node[cur].cnt + node[node[cur].ch[0]].sum;
            if (k <= 0) return node[cur].val;
            cur = node[cur].ch[1];
        }
    }
}

查询前驱

分析古古古

1
2
3
4
5
6
7
int querypre(int val) {
    insert(val);
    int cur = node[root].ch[0];
    while (node[cur].ch[1]) cur = node[cur].ch[1];
    delet(val);
    return cur;
}

查询后继

1
2
3
4
5
6
7
int querynxt(int val) {
    insert(val);
    int cur = node[root].ch[1];
    while (node[cur].ch[0]) cur = node[cur].ch[0];
    delet(val);
    return cur;
}

删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void delet(int val) {
    queryid(val);
    if (node[root].cnt > 1) {
        node[root].cnt--;
        update(root);
        return;
    }
    if (node[root].ch[0] == 0 && node[root].ch[1] == 0) {
        clear(root);
        root = 0;
        return;
    }
    if (node[root].ch[1] == 0) {
        int cur = root;
        root = node[root].ch[0];
        node[root].fa = 0;
        clear(cur);
        return;
    }
    if (node[root].ch[0] == 0) {
        int cur = root;
        root = node[root].ch[1];
        node[root].fa = 0;
        clear(cur);
        return;
    }
    int u = querypre(val), cur = root; // ???
    node[node[cur].ch[1]].fa = u;
    node[u].ch[1] = node[cur].ch[1];
    clear(cur);
    update(root);
}
# 平衡树, 数据结构
CF游记-Codeforces Round
题解-luogu-p3275糖果

Comments

Follow

一言（ヒトコト）


    2333



Recent

Categories

Tag Cloud

0/1分数规划 2-SAT FFT/NTT KMP Pólya计数 ST算法 bitset dfs序 python set 主席树 乘法逆元 二分图 二分图匹配 二分答案 二叉堆 二维偏序 倍增 分块 前缀和 动态点分治 动态规划 单调队列 博弈论 卡特兰数 可持久化trie 后缀自动机 启发式合并 哈希(hash) 堆 复杂度分析 多项式 字符串 容斥原理 差分 差分约束系统 平衡树 异或 强连通分量 排序 搜索 数学 数学期望 数据结构 数论 最小割 最短路 最短路树 最近公共祖先 构造 栈 树上前缀和 树上差分 树套树 树形dp 树状数组 树链剖分 概率 欧拉函数 欧拉路 点分治 状态压缩 生成函数 生成树 矩阵 离散化 素数 线性基 线段树 组合数 组合计数 网络流 群论 背包 虚树 行列式 计数dp 计算几何 贪心 费用流 逆元 高斯消元
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×