Splay树详解（C语言实现自调整二叉搜索树的完整教程）

一、Splay树的基本结构

首先，我们定义Splay树的节点结构。每个节点包含键值、左右子节点指针：

typedef struct Node {    int key;    struct Node *left, *right;} Node;

二、核心旋转操作

Splay树依赖两种基本旋转：右旋（Zig）和左旋（Zag）。这些旋转用于将目标节点“伸展”到根。

1. 右旋（Zig）

Node* rightRotate(Node *x) {    Node *y = x->left;    x->left = y->right;    y->right = x;    return y;}

2. 左旋（Zag）

Node* leftRotate(Node *x) {    Node *y = x->right;    x->right = y->left;    y->left = x;    return y;}

三、伸展（Splay）操作

这是Splay树的核心！根据目标节点与父节点、祖父节点的相对位置，分为三种情况处理：

• Zig：节点是根的直接子节点（单次旋转）
• Zig-Zig：节点与其父节点在同一方向（两次同向旋转）
• Zig-Zag：节点与其父节点在不同方向（先子旋转再父旋转）

Node* splay(Node *root, int key) {    if (root == NULL || root->key == key)        return root;    // 目标在左子树    if (root->key > key) {        if (root->left == NULL) return root;        // Zig-Zig (Left Left)        if (root->left->key > key) {            root->left->left = splay(root->left->left, key);            root = rightRotate(root);        }        // Zig-Zag (Left Right)        else if (root->left->key < key) {            root->left->right = splay(root->left->right, key);            if (root->left->right != NULL)                root->left = leftRotate(root->left);        }        return (root->left == NULL) ? root : rightRotate(root);    }        // 目标在右子树    else {        if (root->right == NULL) return root;        // Zig-Zig (Right Right)        if (root->right->key < key) {            root->right->right = splay(root->right->right, key);            root = leftRotate(root);        }        // Zig-Zag (Right Left)        else if (root->right->key > key) {            root->right->left = splay(root->right->left, key);            if (root->right->left != NULL)                root->right = rightRotate(root->right);        }        return (root->right == NULL) ? root : leftRotate(root);    }}

四、插入操作

插入新节点后，我们会对新插入的节点执行splay操作，使其成为新的根。

Node* insert(Node *root, int key) {    if (root == NULL) {        Node *newNode = (Node*)malloc(sizeof(Node));        newNode->key = key;        newNode->left = newNode->right = NULL;        return newNode;    }    root = splay(root, key);    if (root->key == key)        return root; // 已存在    Node *newNode = (Node*)malloc(sizeof(Node));    newNode->key = key;    if (root->key > key) {        newNode->right = root;        newNode->left = root->left;        root->left = NULL;    } else {        newNode->left = root;        newNode->right = root->right;        root->right = NULL;    }    return newNode;}

五、查找操作

查找时，若找到目标节点，则将其splay到根；否则返回NULL。

Node* search(Node *root, int key) {    root = splay(root, key);    if (root && root->key == key)        return root;    return NULL;}

六、为什么使用Splay树？

Splay树具有以下优势：

• 自适应性：频繁访问的元素会自动移到靠近根的位置
• 无需额外存储：不像AVL或红黑树需要存储平衡因子或颜色
• 均摊时间复杂度优秀：基本操作均摊O(log n)

虽然最坏情况下的单次操作可能达到O(n)，但由于自调整二叉搜索树的特性，实际应用中性能非常出色。

七、总结

通过本教程，你已经掌握了如何用C语言实现Splay树。Splay树是一种强大而优雅的数据结构，特别适合需要频繁访问某些热点数据的场景。

记住：实践是最好的老师！建议你亲手敲一遍代码，调试并测试各种操作，加深理解。希望这篇数据结构教程对你有所帮助！

关键词回顾：Splay树、C语言实现、自调整二叉搜索树、数据结构教程