第77课 - 伸展树 (Splay Tree)

学习目标

理解伸展树（Splay Tree）的基本思想：通过“伸展（Splay）”操作，将最近访问的节点调整到树根，以优化后续对相同或附近数据的访问。
掌握实现伸展树所需的两种核心旋转操作：左旋（Zig）和右旋（Zag）。
能够理解并实现将任意节点伸展至树根的过程，包含单旋（Zig/Zag）、一字旋（Zig-Zig/Zag-Zag）和之字旋（Zig-Zag/Zag-Zig）三种情况。
了解伸展树的时间复杂度特性：虽然单次操作最坏为O(N)，但连续M次操作的均摊复杂度为O(log N)。
能够使用C++ STL中的std::set（通常由红黑树实现）对比理解伸展树的应用场景与性能特点。

核心概念

1. 伸展树是什么？

想象你有一个图书馆，但这次规则变了：每当你从书架上找到一本书并阅读后，你会动态地调整书架的顺序，把这本书和它附近的书都移到最容易拿到的地方（比如书架最前面）。这就是伸展树的核心思想。

它是一种二叉搜索树（BST），但不同于AVL树或红黑树通过严格平衡来保证操作复杂度，伸展树不保证严格的平衡。它的主要优势在于，通过一个名为 “伸展（Splay）” 的操作，在每次访问（查找、插入、删除）一个节点后，都将该节点旋转移动到树的根部。这样做的逻辑是：刚刚被访问过的数据很可能很快再次被访问（局部性原理），将其放在根部可以极大优化后续访问。

2. 核心操作：旋转与伸展

伸展树的所有操作都依赖于旋转（Rotation），这是改变树局部结构的基本操作，类似于AVL树中的旋转。

右旋（Zig）：将某个节点X和其左孩子L的位置互换。X成为L的右孩子，L原来的右孩子LR成为X的左孩子。
左旋（Zag）：将某个节点X和其右孩子R的位置互换。X成为R的左孩子，R原来的左孩子RL成为X的右孩子。

伸展（Splay）操作 是指将节点X通过一系列旋转，从当前位置移动到树根的过程。这个过程需要根据X、其父节点P、祖父节点G的位置关系，分三种情况递归处理，直到X成为根节点：

Zig/Zag（单旋）：X是根的直接子节点。直接对X进行一次右旋或左旋即可将其升为根。
Zig-Zig / Zag-Zag（一字旋）：X和其父节点P位于祖父节点G的同一侧（都是左孩子或都是右孩子）。先对G进行一次旋转，再对P进行一次旋转。这能把整个路径“拉直”，减少树的高度。
Zig-Zag / Zag-Zig（之字旋）：X和P位于G的两侧（一个是左孩子，另一个是右孩子）。先对P进行一次旋转，再对G进行一次旋转。这能将树调整为更平衡的形状。

3. 均摊复杂度

伸展树的单次Splay操作最坏时间复杂度是O(N)（例如树退化成链表）。但是，数学家们通过均摊分析（Amortized Analysis） 证明，执行任意连续的M次操作（查找、插入、删除等），其总时间复杂度为O(M log N)。这意味着平均下来，每次操作的时间是O(log N)。这种“用一次昂贵操作，带来后续多次廉价操作”的特性，非常适合处理具有局部性的数据访问模式。

代码示例

下面是一个简单的伸展树C++实现，包含插入、查找和伸展操作。为了简洁，这里实现的是顶向下（Top-Down） 的伸展，这是实践中更高效、更常用的实现方式（避免了为每个节点存储父指针）。

#include <iostream>
#include <string>
using namespace std;

// 伸展树节点
struct Node {
    int key;
    Node* left;
    Node* right;
    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

// 右旋（Zig）操作，返回新的根节点
Node* rightRotate(Node* x) {
    Node* y = x->left;
    x->left = y->right;
    y->right = x;
    return y;
}

// 左旋（Zag）操作，返回新的根节点
Node* leftRotate(Node* x) {
    Node* y = x->right;
    x->right = y->left;
    y->left = x;
    return y;
}

// 伸展操作：将键为k的节点（或最后访问的节点）移动到树根
// 如果树中没有键k，则将最接近k的节点移动到根
Node* splay(Node* root, int k) {
    if (!root || root->key == k) return root;

    // 键k在左子树
    if (root->key > k) {
        if (!root->left) return root; // k不在树中

        // Zig-Zig（左-左）情况
        if (root->left->key > k) {
            // 首先递归地将k伸展到左左子树的根
            root->left->left = splay(root->left->left, k);
            // 对根进行第一次右旋（Zig）
            root = rightRotate(root);
        }
        // Zig-Zag（左-右）情况
        else if (root->left->key < k) {
            // 首先递归地将k伸展到左右子树的根
            root->left->right = splay(root->left->right, k);
            // 对左子节点进行左旋（Zag）
            if (root->left->right)
                root->left = leftRotate(root->left);
        }

        // 对根进行最后的右旋（Zig），如果左子节点存在
        return (root->left) ? rightRotate(root) : root;
    }
    // 键k在右子树（对称情况）
    else {
        if (!root->right) return root;

        // Zag-Zig（右-左）情况
        if (root->right->key > k) {
            root->right->left = splay(root->right->left, k);
            if (root->right->left)
                root->right = rightRotate(root->right);
        }
        // Zag-Zag（右-右）情况
        else if (root->right->key < k) {
            root->right->right = splay(root->right->right, k);
            root = leftRotate(root);
        }

        return (root->right) ? leftRotate(root) : root;
    }
}

// 将键k插入到伸展树中，返回新树的根
Node* insert(Node* root, int k) {
    if (!root) return new Node(k);

    // 先将最接近k的节点伸展到根
    root = splay(root, k);

    // 如果根节点就是k，直接返回
    if (root->key == k) return root;

    Node* newNode = new Node(k);

    // 如果k < root->key，则newNode应为新根，原根及其右子树成为newNode的右子树
    if (root->key > k) {
        newNode->right = root;
        newNode->left = root->left;
        root->left = nullptr;
    }
    // 如果k > root->key，则newNode应为新根，原根及其左子树成为newNode的左子树
    else {
        newNode->left = root;
        newNode->right = root->right;
        root->right = nullptr;
    }
    return newNode;
}

// 在伸展树中查找键k，并将包含k的节点（或最接近的节点）伸展到根
Node* search(Node* root, int k) {
    return splay(root, k);
}

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

int main() {
    Node* root = nullptr;

    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    cout << "插入序列后的中序遍历（应有序）: ";
    inorder(root);
    cout << endl;
    cout << "根节点应是25（最后插入时伸展的结果）: " << root->key << endl;

    // 查找20，并将其伸展到根
    root = search(root, 20);
    cout << "查找20后，新的根节点是: " << root->key << endl;
    cout << "查找20后的中序遍历: ";
    inorder(root);
    cout << endl;

    return 0;
}

运行预期输出：

插入序列后的中序遍历（应有序）: 10 20 25 30 40 50 
根节点应是25（最后插入时伸展的结果）: 25
查找20后，新的根节点是: 20
查找20后的中序遍历: 10 20 25 30 40 50

实践练习

练习1：基础理解

问题：在上述代码的splay函数中，处理“Zig-Zig”情况时，为什么先递归调用splay，再进行两次旋转？直接旋转两次不行吗？这样做的目的是什么？

预期输出/思路：你应该能说明这是为了保证伸展操作的递归正确性。先通过递归将目标节点k伸展到左左子树的根，然后再进行两次旋转，最终能保证k被一步步推到整棵树的根。如果直接旋转两次而没有递归，那么旋转操作可能作用在错误的子树上。

练习2：功能扩展

问题：请为上面的伸展树实现删除操作。提示：先删除一个节点通常需要先将其伸展到根部，然后根据情况进行左右子树合并。要求：

实现 Node* deleteNode(Node* root, int k) 函数。
删除后，树仍然是一棵有效的二叉搜索树。
在main函数中测试删除操作，并打印结果。

预期输出：删除节点后，树的中序遍历结果正确，且根节点是删除操作后剩余子树伸展的结果。

练习3：性能对比

问题：分别使用本课实现的伸展树和C++标准库的std::set（底层通常是红黑树），完成以下任务，比较它们的运行时间。

向数据结构中顺序插入10万个随机整数（范围1-100万）。
随机访问（查找）其中的1万个整数，并记录总时间。思考：在什么情况下，伸展树可能会比std::set表现更好？（提示：考虑访问的局部性）

常见错误

忘记处理父节点指针：在基于父指针的递归实现中，旋转操作后必须正确更新相关节点的parent指针，否则后续的伸展会出错。本课示例采用顶向下方式避免了此问题。
旋转逻辑错误：左旋和右旋的代码实现虽然对称，但细节容易混淆。一个常见的错误是旋转后丢失了子树的连接（例如，在leftRotate(x)中，x->right的左孩子被赋给了x，但原始的x->right需要检查是否为空）。
混淆“顶向下”和“底向上”伸展：初学者容易混淆两种伸展策略。底向上伸展需要父指针，思路更直观但实现稍繁；顶向下伸展是实际应用中的优选，但理解其递归和指针变换更复杂。
忽略边界条件：在splay函数中，必须仔细检查节点指针（root->left, root->right等）是否为空，再进行访问或旋转，否则会导致程序崩溃。

小结

核心思想：伸展树是一种自调整的二叉搜索树。每次访问一个节点后，都会通过伸展（Splay） 操作将其移动到树根，以利用“局部性”原理优化后续访问。
关键操作：伸展操作基于左旋（Zag） 和右旋（Zig） 两种基本旋转，并根据节点与父、祖父节点的位置关系，分为单旋、一字旋和之字旋三种情况递归完成。
时间复杂度：单次操作最坏为O(N)，但连续M次操作的均摊复杂度为O(log N)。这使其在动态数据、尤其是具有访问局部性的场景（如网络缓存、文本编辑器缓存）中非常高效。
对比与权衡：相比严格的平衡树（如AVL树、红黑树），伸展树的常数因子更小，实现可能更简单，且无需存储额外的平衡信息。但其最坏情况性能不稳定，不适合对单次操作延迟要求极高的实时系统。
下一课预览：接下来我们将学习稀疏表（Sparse Table），这是一种用于静态区间查询（如区间最小值、最大值）的高效数据结构，是对倍增思想的典型应用。

练习编辑器

rust