一、Splay 树是什么？

Splay 树（伸展树）是一种自调整的二叉搜索树（BST），其核心特性是：每次访问（查找 / 插入 / 删除）某个节点后，会通过一系列旋转操作将该节点调整到树根位置。

这种 "局部性" 优化使得最近访问的节点更容易被再次访问，在实际应用中（如缓存、频繁访问的数据集）性能表现优异。Splay 树不保证绝对的平衡，但能保证均摊时间复杂度为 O (logn)。

核心思想

• 旋转操作（Zig/Zig-Zig/Zig-Zag）：通过旋转调整节点位置，避免树退化成链表
• 伸展操作：将目标节点逐层旋转至根节点，过程中自动平衡树结构

二、Splay 树的核心操作

1. 旋转操作

Splay 树的旋转分为三种情况，本质是二叉搜索树旋转的扩展：

旋转类型	适用场景	核心逻辑
Zig（单旋）	目标节点的父节点是根节点	节点 → 父节点（根）直接旋转
Zig-Zig（双旋）	目标节点、父节点、祖父节点在同一条直线上	先旋父节点，再旋目标节点
Zig-Zag（双旋）	目标节点、父节点、祖父节点呈折线	先旋目标节点，再旋目标节点

2. 基本操作

• 查找：查找目标值，找到后将其伸展到根
• 插入：按 BST 规则插入节点，再将其伸展到根
• 删除：先将待删除节点伸展到根，删除后合并左右子树
• 前驱 / 后继：利用 BST 特性查找，结合伸展优化

三、Splay 树实战：洛谷 P3369 【模板】普通平衡树

题目描述

实现支持以下 6 种操作的有序集合：

1. 1 x：插入数值 x
2. 2 x：删除数值 x（若有多个相同的 x，只删除一个）
3. 3 x：查询数值 x 的排名（排名定义为比 x 小的数的个数 + 1）
4. 4 k：查询排名为 k 的数值
5. 5 x：查询 x 的前驱（小于 x 的最大数）
6. 6 x：查询 x 的后继（大于 x 的最小数）

完整 AC 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

// 定义无穷大常量，作为哨兵节点的值
const int INF = 0x3f3f3f3f;

// Splay树节点结构（扩展版，支持重复元素）
struct Node {
    int key;        // 节点存储的数值
    int cnt;        // 相同数值的节点计数（处理重复元素）
    int size;       // 子树大小（包含重复计数：size = cnt + 左size + 右size）
    Node *left;     // 左孩子指针
    Node *right;    // 右孩子指针
    Node *parent;   // 父节点指针

    // 构造函数：初始化值、计数为1、大小为1，指针置空
    Node(int val) : key(val), cnt(1), size(1), left(nullptr), right(nullptr), parent(nullptr) {}
};

class SplayTree {
private:
    Node *root; // 整棵树的根节点

    /**
     * @brief 更新节点的子树大小（包含重复计数）
     * @param x 要更新的节点
     * @note size = 自身计数 + 左子树size + 右子树size
     */
    void update(Node *x) {
        if (x) {
            x->size = x->cnt; // 先初始化为本节点的计数
            if (x->left) x->size += x->left->size; // 加上左子树大小
            if (x->right) x->size += x->right->size; // 加上右子树大小
        }
    }

    /**
     * @brief 判断节点是父节点的左孩子还是右孩子
     * @param x 要判断的节点
     * @return true：左孩子，false：右孩子
     */
    bool isLeftChild(Node *x) {
        return x == x->parent->left;
    }

    /**
     * @brief 旋转操作：将x向上旋转一层
     * @param x 要旋转的节点
     * @note 与基础版逻辑一致，旋转后更新size
     */
    void rotate(Node *x) {
        Node *p = x->parent;  // x的父节点
        Node *g = p->parent;  // x的祖父节点

        if (isLeftChild(x)) { // x是左孩子 → 右旋
            p->left = x->right;
            if (x->right) x->right->parent = p;
            x->right = p;
        } else { // x是右孩子 → 左旋
            p->right = x->left;
            if (x->left) x->left->parent = p;
            x->left = p;
        }

        // 更新父节点指针
        p->parent = x;
        x->parent = g;

        // 更新祖父节点的子节点指针
        if (g) {
            if (g->left == p) g->left = x;
            else g->right = x;
        } else {
            root = x; // x成为新根
        }

        // 先更p，再更x（x是p的父节点）
        update(p);
        update(x);
    }

    /**
     * @brief 伸展操作：将x调整到目标位置
     * @param x 要伸展的节点
     * @param target 目标父节点（默认根）
     */
    void splay(Node *x, Node *target = nullptr) {
        while (x->parent != target) {
            Node *p = x->parent;
            Node *g = p->parent;

            if (g != target) {
                // 双旋优化：Zig-Zig或Zig-Zag
                if (isLeftChild(x) == isLeftChild(p)) rotate(p);
                else rotate(x);
            }
            rotate(x); // 单旋
        }
        if (target == nullptr) root = x;
    }

    /**
     * @brief 内部查找函数：查找值为val的节点
     * @param val 要查找的数值
     * @return 最后访问的节点指针
     * @note 查找后伸展到根
     */
    Node* findNode(int val) {
        Node *cur = root;
        while (cur) {
            if (cur->key == val) break;
            else if (val < cur->key) {
                if (!cur->left) break;
                cur = cur->left;
            } else {
                if (!cur->right) break;
                cur = cur->right;
            }
        }
        if (cur) splay(cur);
        return cur;
    }

    /**
     * @brief 递归销毁树节点，释放内存
     * @param x 当前节点
     */
    void destroy(Node *x) {
        if (!x) return;
        destroy(x->left);
        destroy(x->right);
        delete x;
    }

public:
    /**
     * @brief 构造函数：初始化根节点，并插入哨兵节点
     * @note 插入-INF和INF作为哨兵，简化边界条件处理
     */
    SplayTree() : root(nullptr) {
        insert(-INF); // 左哨兵（最小值）
        insert(INF);  // 右哨兵（最大值）
    }

    // 析构函数：销毁整棵树
    ~SplayTree() { destroy(root); }

    /**
     * @brief 1. 插入操作（支持重复元素）
     * @param val 要插入的数值
     * @note 1. 存在则增加计数 2. 不存在则创建新节点 3. 伸展到根
     */
    void insert(int val) {
        if (!root) { // 树为空
            root = new Node(val);
            update(root);
            return;
        }

        Node *cur = root;
        Node *p = nullptr;

        // 查找插入位置
        while (cur) {
            p = cur;
            if (cur->key == val) { // 数值已存在，增加计数
                cur->cnt++;
                update(cur);      // 更新size
                splay(cur);       // 伸展到根
                return;
            } else if (val < cur->key) { // 往左找
                cur = cur->left;
            } else { // 往右找
                cur = cur->right;
            }
        }

        // 创建新节点
        Node *newNode = new Node(val);
        newNode->parent = p;
        if (val < p->key) p->left = newNode;
        else p->right = newNode;

        // 更新父节点size，并伸展新节点到根
        update(p);
        splay(newNode);
    }

    /**
     * @brief 2. 删除操作（支持重复元素）
     * @param val 要删除的数值
     * @return true：删除成功，false：数值不存在
     * @note 1. 计数>1则减少计数 2. 计数=1则删除节点 3. 合并左右子树
     */
    bool remove(int val) {
        // 查找并伸展目标节点到根
        Node *x = findNode(val);
        if (!x || x->key != val) { // 数值不存在
            return false;
        }

        // 情况1：重复计数>1，仅减少计数
        if (x->cnt > 1) {
            x->cnt--;
            update(x); // 更新size
            return true;
        }

        // 情况2：计数=1，真正删除节点
        splay(x); // 确保x是根节点
        Node *leftSub = x->left;  // 左子树
        Node *rightSub = x->right; // 右子树

        delete x; // 释放节点内存
        root = nullptr;

        // 合并左右子树
        if (leftSub) {
            leftSub->parent = nullptr;
            root = leftSub;

            // 找到左子树的最大值节点（最右侧）
            Node *maxLeft = leftSub;
            while (maxLeft->right) {
                maxLeft = maxLeft->right;
            }
            splay(maxLeft); // 伸展到根

            // 连接右子树
            root->right = rightSub;
            if (rightSub) {
                rightSub->parent = root;
            }
            update(root); // 更新根节点size
        } else if (rightSub) { // 只有右子树
            rightSub->parent = nullptr;
            root = rightSub;
        }

        return true;
    }

    /**
     * @brief 3. 查询数值val的排名
     * @param val 要查询的数值
     * @return 排名（比val小的数的个数 + 1）
     * @note 排名 = 根节点左子树的size（哨兵节点不影响）
     */
    int getRank(int val) {
        Node *x = findNode(val);
        // 确保定位准确（处理val不存在的情况）
        if (x->key < val) splay(x);
        
        // 根节点左子树的size即为比val小的数的个数
        return root->left->size;
    }

    /**
     * @brief 4. 查询排名为k的数值
     * @param k 排名（输入的k）
     * @return 对应数值
     * @note 1. k++ 抵消左哨兵(-INF)的影响 2. 根据size递归查找
     */
    int getKth(int k) {
        k++; // 跳过左哨兵节点（-INF），排名整体+1
        Node *cur = root;

        while (cur) {
            // 左子树的节点总数
            int leftSize = cur->left ? cur->left->size : 0;

            if (leftSize >= k) { 
                // 左子树节点数 >=k → 目标在左子树
                cur = cur->left;
            } else if (leftSize + cur->cnt < k) { 
                // 左子树+当前节点 <k → 目标在右子树，更新k
                k -= leftSize + cur->cnt;
                cur = cur->right;
            } else { 
                // 找到目标节点，伸展到根并返回值
                splay(cur);
                return cur->key;
            }
        }
        return -1; // 理论上不会执行到这里（有哨兵节点）
    }

    /**
     * @brief 5. 查询val的前驱（小于val的最大数）
     * @param val 目标数值
     * @return 前驱值
     * @note 技巧：临时插入val，根节点左子树的最大值即为前驱，最后删除val
     */
    int getPrev(int val) {
        insert(val); // 插入val并伸展到根
        Node *x = root->left; // 根节点的左子树
        // 找左子树的最大值（最右侧节点）
        while (x->right) {
            x = x->right;
        }
        int res = x->key; // 记录前驱值
        remove(val);      // 删除临时插入的val
        return res;
    }

    /**
     * @brief 6. 查询val的后继（大于val的最小数）
     * @param val 目标数值
     * @return 后继值
     * @note 技巧：临时插入val，根节点右子树的最小值即为后继，最后删除val
     */
    int getNext(int val) {
        insert(val); // 插入val并伸展到根
        Node *x = root->right; // 根节点的右子树
        // 找右子树的最小值（最左侧节点）
        while (x->left) {
            x = x->left;
        }
        int res = x->key; // 记录后继值
        remove(val);      // 删除临时插入的val
        return res;
    }
};

int main() {
    // 加速输入输出：关闭同步，解除cin与cout绑定
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; // 操作数
    cin >> n;

    SplayTree st; // 创建Splay树对象

    while (n--) {
        int op, x; // op：操作类型，x：操作数
        cin >> op >> x;

        switch (op) {
            case 1: // 插入操作
                st.insert(x);
                break;
            case 2: // 删除操作
                st.remove(x);
                break;
            case 3: // 查询排名
                cout << st.getRank(x) << endl;
                break;
            case 4: // 查询第k大
                cout << st.getKth(x) << endl;
                break;
            case 5: // 查询前驱
                cout << st.getPrev(x) << endl;
                break;
            case 6: // 查询后继
                cout << st.getNext(x) << endl;
                break;
        }
    }

    return 0;
}

1. 重复元素处理

• 新增cnt属性：记录相同数值的节点个数，避免重复创建节点
• 插入时：若数值已存在，仅增加cnt计数，不新建节点
• 删除时：先减少cnt计数，仅当cnt=0时才真正删除节点
• size属性更新：size = cnt + 左子树size + 右子树size，保证排名计算准确

2. 哨兵节点优化

• 插入-INF和INF作为哨兵节点，避免处理空指针、边界值等特殊情况
• 第 k 大查询时k++：抵消左哨兵-INF的影响，保证排名计算正确

3. 排名 / 第 k 大查询

• 排名查询：核心逻辑是排名 = 根节点左子树size，因为左子树所有节点都小于当前节点
• 第 k 大查询：根据左子树size判断目标位置：
  • 左子树size >=k → 目标在左子树
  • 左子树size + cnt <k → 目标在右子树，k -= 左子树 size + cnt
  • 否则当前节点即为目标

4. 前驱 / 后继查询（简化版）

6 核心函数说明

注意事项

---

总结

• 前驱：小于 x 的最大数 → 临时插入 x 后，根节点左子树的最大值
• 后继：大于 x 的最小数 → 临时插入 x 后，根节点右子树的最小值
• 临时插入后删除，无需处理复杂的边界条件，代码更简洁

  5. 节点结构设计

• key：存储节点值
• left/right/parent：分别指向左孩子、右孩子、父节点（父节点指针是 Splay 树的关键）
• size：子树大小（可选功能，用于实现排名、第 k 大等操作）
• rotate 旋转函数：完成单个节点的旋转，调整父子关系，旋转后更新节点的size属性
• splay 伸展函数：核心逻辑，根据节点位置选择单旋 / 双旋，将目标节点调整到根
• 插入 / 删除 / 查找：基于 BST 规则实现，操作后均执行伸展操作优化后续访问

  五、Splay 树的应用场景与注意事项

  应用场景

• 缓存系统：利用局部性原理，频繁访问的节点靠近根，访问更快
• 区间操作：结合区间树思想，实现高效的区间查询 / 修改（如文艺平衡树）
• 替代普通 BST：在频繁访问少量节点的场景下，性能优于 AVL / 红黑树
• 实现有序集合：如排行榜、有序数据存储、数值排名系统
• Splay 树不保证最坏情况的时间复杂度，极端情况下（如顺序插入）可能退化成 O (n)
• 适合访问模式具有局部性的场景（如近期访问的节点大概率再次访问），不适合单次操作必须保证 O (log n) 的场景
• 实现时需重点维护父节点指针，这是旋转 / 伸展操作中最容易出错的地方
• 内存管理：析构函数中递归销毁所有节点，避免内存泄漏
• 输入输出优化：处理大量数据时，使用ios::sync_with_stdio(false); cin.tie(nullptr);加速
• Splay 树核心特性是访问节点后将其伸展到根，通过旋转（Zig/Zig-Zig/Zig-Zag）实现自平衡，均摊时间复杂度为 O (logn)；
• 基础实现需掌握旋转和伸展操作，扩展实现需处理重复元素（cnt 属性）、边界条件（哨兵节点）；