深入理解Splay树（C++语言Splay树实现方法详解）

Splay树的核心操作

Splay树的关键在于伸展操作（Splay），它由一系列旋转组成。根据节点与其父节点、祖父节点的相对位置，分为以下几种情况：

• zig：当目标节点的父节点是根节点时，执行单次旋转。
• zig-zig：当目标节点与其父节点同为左子或右子时，先旋转祖父，再旋转父节点。
• zig-zag：当目标节点与父节点方向相反（如父为左子，目标为右子），则先旋转父节点，再旋转目标节点。

C++ Splay树实现

下面我们用C++实现一个完整的Splay树，包含节点定义、旋转、伸展、插入、查找和删除等操作。

1. 节点结构定义

struct Node {    int key;    Node *left, *right, *parent;    Node(int k) : key(k), left(nullptr), right(nullptr), parent(nullptr) {}};  

2. 辅助函数：判断左右子

bool isLeftChild(Node* child) {    return child->parent && child->parent->left == child;}Node* rotate(Node* x) {    Node* p = x->parent;    Node* g = p->parent;    if (!p) return x;    if (isLeftChild(x)) {        p->left = x->right;        if (x->right) x->right->parent = p;        x->right = p;    } else {        p->right = x->left;        if (x->left) x->left->parent = p;        x->left = p;    }    p->parent = x;    x->parent = g;    if (g) {        if (isLeftChild(p)) g->left = x;        else g->right = x;    }    return x;}  

3. 伸展操作（Splay）

void splay(Node* x, Node*& root) {    while (x->parent) {        Node* p = x->parent;        Node* g = p->parent;        if (!g) {            // zig            rotate(x);        } else if ((isLeftChild(x) && isLeftChild(p)) ||                   (!isLeftChild(x) && !isLeftChild(p))) {            // zig-zig            rotate(p);            rotate(x);        } else {            // zig-zag            rotate(x);            rotate(x);        }    }    root = x; // x becomes the new root}  

4. 查找与插入

Node* find(Node* root, int key) {    Node* curr = root;    Node* last = nullptr;    while (curr) {        last = curr;        if (key == curr->key) {            splay(curr, root);            return curr;        } else if (key < curr->key) {            curr = curr->left;        } else {            curr = curr->right;        }    }    if (last) splay(last, root);    return nullptr;}void insert(Node*& root, int key) {    if (!root) {        root = new Node(key);        return;    }    Node* curr = root;    Node* parent = nullptr;    while (curr) {        parent = curr;        if (key == curr->key) {            splay(curr, root);            return; // duplicate, no insertion        } else if (key < curr->key) {            curr = curr->left;        } else {            curr = curr->right;        }    }    Node* newNode = new Node(key);    newNode->parent = parent;    if (key < parent->key)        parent->left = newNode;    else        parent->right = newNode;    splay(newNode, root);}  

为什么选择Splay树？

Splay树虽然不保证严格的平衡（不像AVL或红黑树），但其均摊时间复杂度为O(log n)，且实现相对简洁。更重要的是，它具有自适应性——热点数据会自动移到顶部，非常适合处理具有局部访问特性的数据。

总结

通过本教程，我们详细讲解了C++ Splay树的实现原理与代码编写。你现在已经掌握了如何构建一个支持插入、查找的Splay树。若想进一步完善，可添加删除操作（通常通过两次splay实现）。Splay树作为自平衡二叉搜索树的一种，是高级数据结构学习的重要一环。希望这篇Splay树教程能帮助你打下坚实基础！

关键词回顾：Splay树实现、C++ Splay树、Splay树教程、自平衡二叉搜索树