Splay：用旋转把节点“翻”到根 - CSP-S | C++ & Algorithm 编程研习社

Splay树：把常用节点“翻”到根——从生活例子到代码实现

你有没有这样的经历？一本厚厚的笔记本，你总是翻到同一页查公式。如果你每次看完后把那一页标记好、甚至折起角，下次找起来就快多了。Splay树做的事情跟这个很像：它把刚刚操作过的节点“翻”到树根，让频繁访问的节点一直待在靠近根的位置，这样反复操作时查找速度就特别快。

Splay是一种自平衡二叉搜索树（BST）。它不保证每次操作都是严格的 $O(\log n)$ ，但通过伸展（Splay）操作，能在连续多次操作中达到均摊 $O(\log n)$ 的复杂度。更重要的是，它能方便地处理区间翻转、区间插入删除等操作，常被用于解决「序列问题」和「Link-Cut Tree」等高级数据结构。

一、Splay的核心：伸展操作

每次做完查找、插入或删除后，我们都会把这次操作涉及的节点通过一系列旋转变成树的根。这个旋转过程叫做伸展（Splay）。

旋转分为三种情况：

情况	图示比喻	操作
单旋（Zig / Zag）	目标节点是根的直接孩子	一次左旋或右旋，把它提到根的位置
一字型双旋（Zig-Zig / Zag-Zag）	目标节点和它的父节点都是左孩子（或都是右孩子）	先旋转父节点，再旋转目标节点
之字形双旋（Zig-Zag / Zag-Zig）	目标节点是左孩子，父节点是右孩子（或相反）	连续两次旋转目标节点

生活中的例子：假设你有一叠试卷，常翻的试卷你会把它抽到最上面。如果它和它上面的试卷都是从上往下第二张（同方向），你会先把你上面的试卷抽到最上面，再抽你自己；如果它和上面的试卷方向不同（一左一右），你需要把自己两次抽出来才能到最上面。

旋转代码实现

旋转是Splay的基础。我们维护每个节点的 parent 指针（指回父节点），这样旋转时能够更新父子关系。

struct Node {
    int val;                // 节点的值
    Node *left, *right;     // 左孩子、右孩子
    Node *parent;           // 父节点
    Node(int v) : val(v), left(nullptr), right(nullptr), parent(nullptr) {}
};

// 对节点x进行单旋（左旋或右旋）
void rotate(Node* x) {
    Node* y = x->parent;    // y是x的父节点
    Node* z = y->parent;    // z是x的祖父节点

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

    y->parent = x;
    x->parent = z;
    if (z) {                // 更新祖父节点的孩子指针
        if (z->left == y) z->left = x;
        else z->right = x;
    }
}

Splay函数：把节点x一直旋转到根

rotate 只处理一次旋转，而 splay 会通过循环把节点x一层层往上转，直到它成为根。

void splay(Node* x) {
    while (x->parent) {                     // 只要x还不是根
        Node* y = x->parent;                // 父节点
        Node* z = y->parent;                // 祖父节点
        if (!z) {                           // 情况1：y是根 -> 单旋
            rotate(x);
        } else if ((y->left == x) == (z->left == y)) {
            // 情况2：一字型（x和y都是左孩子，或都是右孩子）
            rotate(y);                      // 先旋转父节点
            rotate(x);                      // 再旋转目标节点
        } else {
            // 情况3：之字形（x和y方向不同）
            rotate(x);                      // 连续两次旋转目标节点
            rotate(x);
        }
    }
}

这里的 (y->left == x) == (z->left == y) 巧妙地判断了方向：当 true 时表示x与y同侧（一字型），否则为异侧（之字形）。

二、查找操作：找到即“翻”

查找与普通BST一样，找到目标值后把它伸展到根。如果没找到，就把最后一次访问的节点（最接近目标值的节点）伸展到根。这样下次相近的值查找更快。

// 在树中查找值为val的节点，返回该节点（已被伸展到根）
Node* find(Node* root, int val) {
    Node* cur = root;
    while (cur) {
        if (val == cur->val) {
            splay(cur);
            return cur;
        } else if (val < cur->val) {
            if (!cur->left) break;      // 左子树为空，提前退出
            cur = cur->left;
        } else {
            if (!cur->right) break;
            cur = cur->right;
        }
    }
    // 没找到，将最后访问的节点cur伸展到根
    if (cur) splay(cur);
    return nullptr;
}

注意：find 返回的是被伸展到根的节点指针，调用后树的根会改变。在外部记得更新 root 变量。

三、插入与删除：也是先“翻”后做

插入操作

按BST规则找到应该插入的位置。
创建新节点，并连接到父节点。
将新节点 splay 到树根。

Node* insert(Node* root, int val) {
    if (!root) return new Node(val);  // 空树直接创建

    Node* cur = root;
    Node* parent = nullptr;
    while (cur) {
        parent = cur;
        if (val < cur->val) cur = cur->left;
        else if (val > cur->val) cur = cur->right;
        else {
            // 值已存在，通常不重复插入，伸展已有节点
            splay(cur);
            return cur;
        }
    }

    Node* newNode = new Node(val);
    newNode->parent = parent;
    if (val < parent->val) parent->left = newNode;
    else parent->right = newNode;

    splay(newNode);          // 把新节点翻到根
    return newNode;          // 新节点就是树的根
}

删除操作

删除需要把目标节点先伸展到根，然后合并左右子树。

找到并 splay 目标节点（如果存在）。
如果左子树为空，右子树直接成为新根。
如果右子树为空，左子树直接成为新根。
否则，将左子树中最大的节点（即左子树最右的节点）splay 到左子树的根，然后把右子树接上去。

Node* erase(Node* root, int val) {
    Node* target = find(root, val);  // 查找并把目标伸展到根
    if (!target) return root;        // 没找到，返回原树

    Node* leftTree = target->left;
    Node* rightTree = target->right;

    delete target;                   // 释放节点

    if (!leftTree) {
        if (rightTree) rightTree->parent = nullptr;
        return rightTree;
    }
    if (!rightTree) {
        leftTree->parent = nullptr;
        return leftTree;
    }

    // 找左子树中的最大节点（最右）
    Node* maxLeft = leftTree;
    while (maxLeft->right) maxLeft = maxLeft->right;
    splay(maxLeft);                  // 把它伸展到左子树的根
    maxLeft->parent = nullptr;       // 现在它是整棵树的根

    maxLeft->right = rightTree;
    rightTree->parent = maxLeft;
    return maxLeft;
}

注意：删除后要返回新的根节点。

四、完整可运行示例：一本“笔记本”的插入、查找、删除

下面是一个完整的Splay树实现，包含了中序遍历输出。你可以把它复制到IDE里运行，观察节点如何被“翻”到根。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;                // 节点的值
    Node *left, *right;     // 左孩子、右孩子
    Node *parent;           // 父节点
    Node(int v) : val(v), left(nullptr), right(nullptr), parent(nullptr) {}
};

// 单旋
void rotate(Node* x) {
    Node* y = x->parent;
    Node* z = y->parent;

    if (y->left == x) {
        y->left = x->right;
        if (x->right) x->right->parent = y;
        x->right = y;
    } else {
        y->right = x->left;
        if (x->left) x->left->parent = y;
        x->left = y;
    }

    y->parent = x;
    x->parent = z;
    if (z) {
        if (z->left == y) z->left = x;
        else z->right = x;
    }
}

// 伸展
void splay(Node* x) {
    while (x->parent) {
        Node* y = x->parent;
        Node* z = y->parent;
        if (!z) {
            rotate(x);
        } else if ((y->left == x) == (z->left == y)) {
            rotate(y);
            rotate(x);
        } else {
            rotate(x);
            rotate(x);
        }
    }
}

// 查找（并伸展）
Node* find(Node* root, int val) {
    Node* cur = root;
    while (cur) {
        if (val == cur->val) {
            splay(cur);
            return cur;
        } else if (val < cur->val) {
            if (!cur->left) break;
            cur = cur->left;
        } else {
            if (!cur->right) break;
            cur = cur->right;
        }
    }
    if (cur) splay(cur);
    return nullptr;
}

// 插入（并伸展）
Node* insert(Node* root, int val) {
    if (!root) return new Node(val);

    Node* cur = root;
    Node* parent = nullptr;
    while (cur) {
        parent = cur;
        if (val < cur->val) cur = cur->left;
        else if (val > cur->val) cur = cur->right;
        else {
            splay(cur);
            return cur;
        }
    }

    Node* newNode = new Node(val);
    newNode->parent = parent;
    if (val < parent->val) parent->left = newNode;
    else parent->right = newNode;

    splay(newNode);
    return newNode;
}

// 删除（并伸展）
Node* erase(Node* root, int val) {
    Node* target = find(root, val);
    if (!target) return root;

    Node* leftTree = target->left;
    Node* rightTree = target->right;
    delete target;

    if (!leftTree) {
        if (rightTree) rightTree->parent = nullptr;
        return rightTree;
    }
    if (!rightTree) {
        leftTree->parent = nullptr;
        return leftTree;
    }

    // 找左子树最大节点
    Node* maxLeft = leftTree;
    while (maxLeft->right) maxLeft = maxLeft->right;
    splay(maxLeft);

    maxLeft->parent = nullptr;
    maxLeft->right = rightTree;
    rightTree->parent = maxLeft;
    return maxLeft;
}

// 中序遍历（打印升序序列）
void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main() {
    Node* root = nullptr;
    // 插入：4, 2, 6, 1, 3, 5, 7
    int vals[] = {4, 2, 6, 1, 3, 5, 7};
    for (int v : vals) root = insert(root, v);

    cout << "插入后中序: ";
    inorder(root);               // 输出: 1 2 3 4 5 6 7
    cout << "\n当前根: " << root->val << endl;  // 最后插入的7是根

    // 查找3，会把它翻到根
    Node* found = find(root, 3);
    cout << "查找3后根: " << found->val << endl; // 输出3
    cout << "中序: ";
    inorder(found);              // 仍为有序：1 2 3 4 5 6 7
    cout << endl;

    // 删除5
    root = erase(found, 5);
    cout << "删除5后中序: ";
    inorder(root);               // 输出: 1 2 3 4 6 7
    cout << endl;

    return 0;
}

运行结果：

插入后中序: 1 2 3 4 5 6 7 
当前根: 7
查找3后根: 3
中序: 1 2 3 4 5 6 7 
删除5后中序: 1 2 3 4 6 7

可以看到，每次查找后，被查的节点变成了根，而整个树仍然保持BST的有序性。

五、新手常见错误

旋转后忘记更新父指针
rotate 中必须同时修改 x、y、z 的 parent 以及孩子的 parent。漏掉一个就会导致splay循环出错或指针混乱。
Splay循环条件判断失误
代码中 (y->left == x) == (z->left == y) 很巧妙，但自己实现时容易写成 y->left == x && z->left == y 然后 else 里又处理其他情况，导致逻辑覆盖不全。建议直接使用标准写法。
没有更新全局根指针
每次 splay 结束后，x 成为新根，但外部变量可能还指向旧根。记得把 root 赋值为 x。在上面的代码中，find、insert、erase 都返回新根，因此主函数里需要用赋值更新。
删除时没有正确合并子树
尤其是左子树最大节点的 splay 后，它的父指针变为 nullptr，然后要把右子树挂上去。如果忘了处理父指针，后续操作会出错。
递归栈溢出
Splay 通常用迭代实现，但有些人会写递归旋转。递归深度可能很大，导致栈溢出。一定要用迭代的 while 循环。

六、相关指引

Splay 树是平衡树家族中非常独特的一员。如果你掌握了它，可以继续学习：

Treap（树堆）：另一种随机化平衡树，使用优先级维护堆性质，代码更简单。
AVL / 红黑树：严格平衡的BST，实现细节多，但效率稳定。
Splay维护序列：通过把节点下标作为键，可以实现区间翻转、区间求和、区间插入删除，是解决序列问题的利器。
Link-Cut Tree（LCT）：基于Splay的动态树结构，用于处理树上的路径操作、连通性问题，是CSP-S/NOI的常考难点。

希望这篇“翻书”般的指南能帮你理解Splay的精髓。动手运行一下代码，观察每次操作后根的变化，你会更直观地感受到它的威力！

例题精讲