前置知识

二叉树

就是一个长这样的树，树中每个结点都有一个父结点（除了根结点没有父结点）和最多两个子结点，每个结点的左儿子一定比它小，右儿子一定比它大。

这棵树的先序遍历很容易知道就是：1 2 3 4 5 6 7 （根左右）
我们还可以从另一个角度理解先序遍历：把整棵树映射到 x 轴上，也就是把它压扁也就是这样：

先序遍历从左到右读出来就可以了

单旋：左旋 / 右旋

口诀：左旋拎右左挂右，右旋拎左右挂左

图示：

code

void zig(int &p) // 右旋 (以p为根)
{
    int q = tr
.l; // 根结点的左儿子，我们要把这个结点旋到根结点
    tr
.l = tr[q].r;
    tr[q].r = p;
    p = q;
    pushup(tr
.r), pushup(p);
}

void zag(int &p) // 左旋 (以p为根)
{
    int q = tr
.r; // 根结点的右儿子，我们要把这个结点旋到根结点
    tr
.r = tr[q].l;
    tr[q].l = p;
    p = q;
    pushup(tr
.l), pushup(p);
}

主要内容

结构体

后续代码全部基于下方结构体定义：

struct Node
{
    int l, r; // 分别表示左右儿子
    int val; // 表示当前点权值
    int size; // 表示以当前点为根的子树中有多少结点
    int cnt; // 表示有多少与当前点权值一样的数
}spl[maxn];

双旋（伸展）

假设我们每次都要将最下层的结点挪到根结点，对于三个结点的组合，有以下四种双旋方式，其中对于一字型的调整也叫做同构调整，对于之字形的调整叫做异构调整

zig-zig

对于这样的一字型，且向左边，我们采用两次右旋

zag-zag

对于这样的一字型，且向右边，我们采用两次左旋

zig-zag

对于这样的之字形，大于号形状，我们采用先对蓝色结点右旋，再对根结点左旋

zag-zig

对于这样的之字形，小于号形状，我们采用先对蓝色结点左旋，再对根结点右旋

code

void splaying(int x, int &y) // 把x挪到y的位置
{
    if (x == y) return;
    int &l = spl[y].l, &r = spl[y].r;
    if (x == l) zig(y); // x是y的左儿子
    else if (x == r) zag(y); // x是y的右儿子
    else // x至少要经过一次双旋才能到y
    {
        if (spl[x].val < spl[y].val) // x在y的左子树
        {
            if (spl[x].val < spl[l].val) // x在y的左儿子的左子树
            {
                splaying(x, spl[l].l); // 先把x旋转到y的左儿子的左儿子
                zig(y), zig(y); // 进行zig-zig双旋
            }
            else // x在y的左儿子的右子树
            {
                splaying(x, spl[l].r); // 先把x旋转到y的左儿子的右儿子
                zag(l), zig(y); // 进行zag-zig双旋
            }
        }
        else // x在y的右子树
        {
            if (spl[x].val < spl[r].val) // x在y的右儿子的左子树
            {
                splaying(x, spl[r].l); // 先把x旋转到y的右儿子的左儿子
                zig(r), zag(y); // 进行zig-zag双旋
            }
            else // x在y的右儿子的右子树
            {
                splaying(x, spl[r].r); // 先把x旋转到y的右儿子的右儿子
                zag(y), zag(y); // 进行zag-zag双旋
            }
        }
    }
}

插入 insert

递归找到该插入的位置，然后再把这个结点splaying到根结点

void insert(int &p, int val)
{
    if (!p) // 如果p结点不存在，创建结点并将其splaying到根结点
        getnode(p, val), splaying(p, root);
    else if (val < spl
.val) insert(spl
.l, val); // 要插入的值比当前结点值小，递归进入左子树
    else if (val > spl
.val) insert(spl
.r, val); // 要插入的值比当前结点值大，递归进入右子树
    else spl
.size ++ , spl
.cnt ++ , splaying(p, root); // 当前平衡树中已有该值，直接更新
}

删除 remove

先把要删除的结点splaying到根结点，然后：

• 如果根结点没有右子树（也就是没有后继（也就是根结点就是最大值）），那么直接删掉即可，也就是把根结点变成当前根结点的左儿子
• 如果根结点有右子树（也就是有后继），就递归找到根结点的后继（也就是从根结点开始，先往右走一步，再一直往左走），把后继splaying到根结点的右儿子，此时这个后继一定没有左子树（因为有左子树，后继就会是左子树里的值），我们要删去根结点，直接让根结点的右儿子的左儿子指向根结点的左儿子即可

code

void remove(int p, int val) // 当前结点为p，要删去值为val的结点
{
    if (spl
.val == val)
    {
        splaying(p, root); // 先把要删去的结点splaying到根结点
        if (spl
.cnt > 1) spl
.cnt -- , spl
.size -- ; // 要删去的数在树中存在不止一个，更新cnt和size即可
        else if (!spl[root].r) root = spl[root].l; // 当前结点没有后继
        else // 当前结点有后继
        {
            // 找到当前结点后继q
            int q = spl[root].r;
            while (spl[q].l) q = spl[q].l;

            splaying(q, spl[root].r); // 把后继splaying到根结点的右儿子
            spl[spl[root].r].l = spl[root].l; // 后继的左儿子变为根结点的左儿子
            root = spl[root].r; // 根结点变为后继

            pushup(root);
        }
    }
    else if (val < spl
.val) remove(spl
.l, val); // 待删结点在当前结点左子树
    else remove(spl
.r, val); // 待删结点在当前结点右子树
}

根据值查询排名

int getrank_bykey(int val)
{
    int p = root, rank = 1;
    while (p)
    {
        if (spl
.val == val) // 找到值为val的结点
        {
            rank += spl[spl
.l].size;
            splaying(p, root); // 把当前结点splaying到根结点
            break;
        }
        if (val <= spl
.val) p = spl
.l; // 待求结点在当前结点的左子树
        else // 待求结点在当前结点的右子树
        {
            rank += spl[spl
.l].size + spl
.cnt; // 加上左子树和本身的结点数
            p = spl
.r;
        }
    }
    return rank;
}

根据排名查询值

int getkey_byrank(int rank)
{
    int p = root;
    while (p)
    {
        if (spl[spl
.l].size < rank && rank <= spl[spl
.l].size + spl
.cnt) // 在这个范围内就是当前结点
        {
            splaying(p, root); // 把当前结点splaying到根结点
            break;
        }
        else if (rank <= spl[spl
.l].size) p = spl
.l; // 待求结点在当前结点的左子树
        else // 待求结点在当前结点的右子树
        {
            rank -= spl[spl
.l].size + spl
.cnt; // 减去左子树和本身的结点数
            p = spl
.r;
        }
    }
    return spl
.val;
}

完整代码模板

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;

struct Node
{
    int l, r; // 分别表示左右儿子
    int val; // 表示当前点权值
    int size; // 表示以当前点为根的子树中有多少结点
    int cnt; // 表示有多少与当前点权值一样的数
}spl[maxn];

int idx; // 记录结点编号开到几
int root; // 记录当前根结点编号是几

void getnode(int &p, int val) // 建立一个编号为p 权值是val的结点
{
    if (!p) p = ++ idx; // 给新结点编号
    spl
.size = spl
.cnt = 1; // 初始化size和cnt
    spl
.val = val; // 赋初值
}

void pushup(int u)
{
    spl[u].size = spl[spl[u].l].size + spl[spl[u].r].size + spl[u].cnt;
}

void zig(int &p) // 右旋 (以p为根)
{
    int q = spl
.l;
    spl
.l = spl[q].r;
    spl[q].r = p;
    p = q;
    pushup(spl
.r), pushup(p);
}

void zag(int &p) // 左旋 (以p为根)
{
    int q = spl
.r;
    spl
.r = spl[q].l;
    spl[q].l = p;
    p = q;
    pushup(spl
.l), pushup(p);
}

void splaying(int x, int &y) // 把x挪到y的位置
{
    if (x == y) return;
    int &l = spl[y].l, &r = spl[y].r;
    if (x == l) zig(y); // x是y的左儿子
    else if (x == r) zag(y); // x是y的右儿子
    else // x至少要经过一次双旋才能到y
    {
        if (spl[x].val < spl[y].val) // x在y的左子树
        {
            if (spl[x].val < spl[l].val) // x在y的左儿子的左子树
            {
                splaying(x, spl[l].l); // 先把x旋转到y的左儿子的左儿子
                zig(y), zig(y); // 进行zig-zig双旋
            }
            else // x在y的左儿子的右子树
            {
                splaying(x, spl[l].r); // 先把x旋转到y的左儿子的右儿子
                zag(l), zig(y); // 进行zag-zig双旋
            }
        }
        else // x在y的右子树
        {
            if (spl[x].val < spl[r].val) // x在y的右儿子的左子树
            {
                splaying(x, spl[r].l); // 先把x旋转到y的右儿子的左儿子
                zig(r), zag(y); // 进行zig-zag双旋
            }
            else // x在y的右儿子的右子树
            {
                splaying(x, spl[r].r); // 先把x旋转到y的右儿子的右儿子
                zag(y), zag(y); // 进行zag-zag双旋
            }
        }
    }
}

void insert(int &p, int val)
{
    if (!p) // 如果p结点不存在，创建结点并将其splaying到根结点
        getnode(p, val), splaying(p, root);
    else if (val < spl
.val) insert(spl
.l, val); // 要插入的值比当前结点值小，递归进入左子树
    else if (val > spl
.val) insert(spl
.r, val); // 要插入的值比当前结点值大，递归进入右子树
    else spl
.size ++ , spl
.cnt ++ , splaying(p, root); // 当前平衡树中已有该值，直接更新
}

void remove(int p, int val) // 当前结点为p，要删去值为val的结点
{
    if (spl
.val == val)
    {
        splaying(p, root); // 先把要删去的结点splaying到根结点
        if (spl
.cnt > 1) spl
.cnt -- , spl
.size -- ; // 要删去的数在树中存在不止一个，更新cnt和size即可
        else if (!spl[root].r) root = spl[root].l; // 当前结点没有后继
        else // 当前结点有后继
        {
            // 找到当前结点后继q
            int q = spl[root].r;
            while (spl[q].l) q = spl[q].l;

            splaying(q, spl[root].r); // 把后继splaying到根结点的右儿子
            spl[spl[root].r].l = spl[root].l; // 后继的左儿子变为根结点的左儿子
            root = spl[root].r; // 根结点变为后继

            pushup(root);
        }
    }
    else if (val < spl
.val) remove(spl
.l, val); // 待删结点在当前结点左子树
    else remove(spl
.r, val); // 待删结点在当前结点右子树
}

int getrank_bykey(int val)
{
    int p = root, rank = 1;
    while (p)
    {
        if (spl
.val == val) // 找到值为val的结点
        {
            rank += spl[spl
.l].size;
            splaying(p, root); // 把当前结点splaying到根结点
            break;
        }
        if (val <= spl
.val) p = spl
.l; // 待求结点在当前结点的左子树
        else // 待求结点在当前结点的右子树
        {
            rank += spl[spl
.l].size + spl
.cnt; // 加上左子树和本身的结点数
            p = spl
.r;
        }
    }
    return rank;
}

int getkey_byrank(int rank)
{
    int p = root;
    while (p)
    {
        if (spl[spl
.l].size < rank && rank <= spl[spl
.l].size + spl
.cnt) // 在这个范围内就是当前结点
        {
            splaying(p, root); // 把当前结点splaying到根结点
            break;
        }
        else if (rank <= spl[spl
.l].size) p = spl
.l; // 待求结点在当前结点的左子树
        else // 待求结点在当前结点的右子树
        {
            rank -= spl[spl
.l].size + spl
.cnt; // 减去左子树和本身的结点数
            p = spl
.r;
        }
    }
    return spl
.val;
}

例题（待补充）