一、概念：为什么需要 Splay Tree
伸展树（Splay Tree） 是一种自调整（self-adjusting）的二叉搜索树，由 Sleator 和 Tarjan 于 1985 年提出。它不显式维护平衡因子或节点高度，而是对每次被访问（查找 / 插入 / 删除）的节点执行一个称为 Splay 的操作——通过一系列旋转把它「伸展」到树根。
因为最近访问的节点会被推到根，所以频繁访问的元素离根更近。从摊还（amortized）角度看，任意连续 m 次操作的总时间都是 O(m log n)，单次的摊还复杂度为 O(log n)，且无需存储任何平衡信息，实现极其简洁。
与 AVL / 红黑树的区别：AVL 靠高度严格平衡，红黑树靠颜色约束；Splay 树「懒」——平时可以很不平衡，但访问会顺手把热点拉到根。
二、核心操作：Splay（伸展）
Splay(x) 的目标：反复对节点 x 做旋转，直到 x 成为根。旋转分三种情形，设 p = parent(x)，g = parent(p)：
| 情形 | 条件 | 旋转动作 |
|---|---|---|
| zig | p 就是根 | 对 x 做一次单旋（左/右取决于 x 是 p 的哪侧孩子） |
| zig-zig | x 与 p 同为左孩子（或同为右孩子） | 先旋 p，再旋 x |
| zig-zag | x 是 p 的左孩子但 p 是 g 的右孩子（或相反） | 连续两次旋 x（第一次左旋/右旋，第二次相反） |
关键：zig-zig / zig-zag 是「双旋」，这正是 Splay 摊还复杂度 O(log n) 的来源（类似「减半距离」的势能论证）。
Mermaid · 渲染中（下方为源码）
graph TD
A["访问节点 x"] --> B{"p 是根?"}
B -->|是| C["zig：单旋 x 到根"]
B -->|否| D{"x 与 p 同侧?"}
D -->|同侧| E["zig-zig：旋 p 再旋 x"]
D -->|异侧| F["zig-zag：旋 x 两次"]
C --> G["x 成为根，结束"]
E --> G
F --> G