Splay Tree 是什么，为什么常访问的节点会更快？

简化版

Splay Tree 是一种自调整二叉搜索树。每次访问、插入或删除节点后，都会通过 Zig、Zig-Zig、Zig-Zag 旋转把目标节点伸展到根。它不维护高度、颜色或随机优先级，但能保证操作的摊还复杂度 O(log n)，并让最近访问过的热点节点更靠近根。

详细版

Splay Tree 的核心思想是“用访问行为调整树形”。如果某个节点刚被访问，它很可能很快再次被访问，于是把它旋到根，可以利用时间局部性。伸展操作分三类：节点父亲是根时做 Zig 单旋；节点和父亲、祖父同向时做 Zig-Zig；节点与父亲、祖父异向时做 Zig-Zag。

Splay Tree 单次操作最坏可能 O(n)，因为树可能暂时很斜；但从一串操作整体看，摊还复杂度是 O(log n)。它适合访问分布有热点、需要 split/merge 的场景，但不适合对单次延迟有强约束的系统。

完整版教学

一、Splay Tree 解决的不是“每一刻都严格平衡”

AVL 和红黑树会在每次更新后维护明确的平衡约束。Splay Tree 走另一条路：它不保存高度、颜色、priority，而是在每次访问节点后把它旋到根。这样树形会随着访问模式自动调整，热点节点会长期停留在较浅位置。

访问序列:
  20, 20, 20, 5, 20

Splay 思路:
  第一次访问 20 后把 20 旋到根
  后续访问 20 会非常快

所以 Splay Tree 的关键词是“自调整”和“局部性”。它不是让树每个瞬间都最矮，而是让未来可能被重复访问的节点变近。

二、三种伸展旋转

伸展操作把目标节点 x 一路旋到根。根据 x、父节点 p、祖父节点 g 的相对位置，有三种基本情况。

情况	结构	操作
Zig	p 是根，x 是 p 的孩子	对 p 做一次单旋
Zig-Zig	x 和 p 同向，都是左孩子或都是右孩子	先旋 g，再旋 p
Zig-Zag	x 和 p 异向，一个左一个右	先旋 p，再旋 g

Zig-Zig 左左:
      g
     /
    p
   /
  x

先右旋 g，再右旋 p，x 上升两层。

Zig-Zig 不是简单“把 x 一层层转上来”。先旋祖父再旋父亲，可以同时压缩路径，让整体摊还复杂度成立。

三、Zig-Zag 为什么要双旋

Zig-Zag 出现在目标节点和父节点方向相反时，例如 x 是 p 的右孩子，p 是 g 的左孩子。此时先对 p 左旋，让 x 到 p 的位置；再对 g 右旋，让 x 到 g 的位置。这样 x 上升两层，并且中序顺序保持不变。

伸展前:
      g=30
     /
   p=10
      \
      x=20

左旋 p 后:
      30
     /
    20
   /
  10

右旋 g 后:
     20
    /  \
   10  30

这个例子也说明旋转不是随便换边。所有旋转都要保持 BST 的中序序列 10,20,30 不变。

四、查找和插入如何使用 splay

查找时，如果找到目标节点，就把它 splay 到根；如果没找到，通常把最后访问到的节点 splay 到根，这样下次查相近 key 时路径也可能变短。插入时先按 BST 插入，再把新节点 splay 到根。

Node search(Node root, int key) {
    Node cur = root;
    Node last = null;
    while (cur != null) {
        last = cur;
        if (key == cur.key) {
            return splay(root, cur);
        } else if (key < cur.key) {
            cur = cur.left;
        } else {
            cur = cur.right;
        }
    }
    return last == null ? null : splay(root, last);
}

真实实现里 splay 需要父指针或递归返回结构，代码比概念略长。面试讲清楚“访问后伸展到根”比强行背完整代码更重要。

五、复杂度为什么说摊还 O(log n)

Splay Tree 单次操作可能很慢。假设树暂时是一条链，访问最深节点可能要 O(n) 次旋转。但伸展后，这条路径会被压缩，后续操作收益很大。摊还分析看的不是某一次，而是一串 m 次操作的总成本。

单次最坏：O(n)
m 次操作总成本：O(m log n) 摊还意义下
平均到每次：O(log n)

这和动态数组扩容的摊还思想类似：某一次扩容很贵，但分摊到很多次 push 后仍然便宜。Splay Tree 的代价模型更复杂，但面试中说明“不是 worst-case O(log n)，而是 amortized O(log n)”就很关键。

六、常见误区与追问

记忆钩子：Splay 不存平衡信息，它把刚访问的节点搬到根，用局部性换摊还效率。

误区：Splay Tree 每次操作最坏都是 O(log n)。 它保证的是摊还 O(log n)，单次最坏可能 O(n)。
误区：Zig-Zig 就是连续两次把 x 和父亲旋转。 标准 Zig-Zig 先旋祖父再旋父亲，这样才能压缩路径。
误区：查找失败时什么都不做。 常见实现会把最后访问节点 splay 到根，以优化相近 key 的后续访问。
追问：Splay Tree 适合什么场景？ 适合访问有热点或局部性的场景，也常用于 split/merge 方便的动态序列结构。
追问：为什么标准库更常用红黑树？ 红黑树单次最坏 O(log n) 更稳定，Splay 的单次延迟波动较大。
追问：它需要维护高度或颜色吗？ 不需要，它靠访问后的旋转自调整，不存额外平衡字段。

七、加强记忆

Splay Tree 的核心不是“严格平衡”，而是“访问后伸展到根”。Zig 处理父亲是根的情况，Zig-Zig 处理同向两层，Zig-Zag 处理异向两层；这些旋转都保持 BST 中序顺序不变。它的优势是实现不需要高度和颜色、能利用热点访问局部性；代价是单次最坏 O(n)，只能承诺摊还 O(log n)。面试时把“自调整、三种旋转、摊还复杂度、适用场景”四个点串起来就够有深度。

简化版

详细版