Splay树（自平衡二叉搜索树）的伸展操作与性能分析

一、问题描述

Splay树是一种自平衡二叉搜索树，它通过"伸展"操作将最近访问的节点移动到根节点位置，利用局部性原理提高频繁访问节点的性能。与其他平衡树（如AVL树、红黑树）不同，Splay树不严格保持平衡，而是通过摊还分析证明其操作具有O(log n)的平均时间复杂度。题目要求理解伸展操作的具体步骤、实现原理，并分析其性能特性。

二、核心概念铺垫

1. 基本性质：

   • 与普通BST相同，满足左子树所有节点值 < 根节点值 < 右子树所有节点值。
   • 每次访问（查找、插入、删除）后都会执行伸展操作，将被访问节点移动到根位置。
   • 不需要存储额外平衡因子或颜色信息。

2. 伸展操作目标：

   • 将目标节点x通过一系列旋转移动到根节点。
   • 同时压缩访问路径，使后续访问相同路径节点时速度更快。

三、伸展操作的三种情况（Zig-Zig/Zag-Zag/Zig-Zag）

设x为需要伸展的节点，p为其父节点，g为祖父节点（如果存在）。

情况1：Zig（或Zag）

• 当x的父节点p是根节点时执行。
• 若x是p的左孩子：对x执行右旋（即Zig旋转）。
• 若x是p的右孩子：对x执行左旋（即Zag旋转）。
• 旋转后x成为新的根节点。

示例（右旋Zig）：

     p                  x
    / \                / \
   x   C  --右旋-->   A   p
  / \                    / \
 A   B                  B   C

情况2：Zig-Zig（或Zag-Zag）

• 当x和p都是左孩子（或都是右孩子）时执行。
• 先对p和g进行旋转（使p上升），再对x和p进行旋转（使x上升）。
• 连续两次同方向旋转。

示例（Zig-Zig）：

       g                p                x
      / \              / \              / \
     p   D            x   g            A   p
    / \      -->     / \ / \    -->       / \
   x   C            A   B C D            B   g
  / \                                         / \
 A   B                                       C   D
步骤：1. 对g和p右旋（Zig） 2. 对p和x右旋（Zig）

情况3：Zig-Zag（或Zag-Zig）

• 当x是p的右孩子而p是g的左孩子（或相反）时执行。
• 先对p和x旋转（使x上升），再对g和x旋转（使x进一步上升）。
• 两次不同方向旋转。

示例（Zig-Zag）：

     g                g                x
    / \              / \              / \
   p   D            x   D            p   g
  / \      -->     / \        -->   / \ / \
 A   x            p   C            A   B C D
    / \          / \
   B   C        A   B
步骤：1. 对p和x左旋（Zag） 2. 对g和x右旋（Zig）

四、伸展操作实现步骤

1. 查找目标节点x：从根开始标准BST查找。
2. 循环伸展：当x的父节点不为空时（即x不是根）：
   • 若x的祖父为空：执行情况1（Zig或Zag）。
   • 否则：
     • 若x和父节点方向一致（都是左孩子或都是右孩子）：执行情况2（Zig-Zig或Zag-Zag）。
     • 否则：执行情况3（Zig-Zag或Zag-Zig）。
3. 更新根指针：最后将根设置为x。

伪代码示例：

function splay(x):
    while x.parent != null:
        p = x.parent
        g = p.parent
        if g == null:               # 情况1
            if x == p.left:
                rightRotate(p)      # Zig
            else:
                leftRotate(p)       # Zag
        else:
            if (x == p.left) and (p == g.left):    # 情况2 Zig-Zig
                rightRotate(g)
                rightRotate(p)
            elif (x == p.right) and (p == g.right): # 情况2 Zag-Zag
                leftRotate(g)
                leftRotate(p)
            elif (x == p.right) and (p == g.left):  # 情况3 Zig-Zag
                leftRotate(p)
                rightRotate(g)
            else:                                   # 情况3 Zag-Zig
                rightRotate(p)
                leftRotate(g)
    root = x

五、Splay树的基本操作

1. 查找（Search）：

   • 标准BST查找节点x。
   • 如果找到x：对x执行伸展操作。
   • 如果未找到：对查找路径上最后一个访问的节点执行伸展操作。

2. 插入（Insert）：

   • 标准BST插入新节点x。
   • 对x执行伸展操作，使其成为根。

3. 删除（Delete）：

   • 查找目标节点x并伸展到根。
   • 删除根节点，得到左子树L和右子树R。
   • 在L中查找最大值节点（即L的最右节点），伸展到L的根。
   • 此时L的根无右孩子，将R作为其右子树。

六、性能分析

1. 摊还时间复杂度：

   • 单个操作可能达到O(n)（如退化成链时）。
   • 但通过势能法（potential method）分析，m次操作的摊还代价为O(m log n)，因此单次操作平均O(log n)。

2. 优势：

   • 无需存储平衡信息，节省空间。
   • 局部性原理：频繁访问的节点靠近根，后续访问更快。
   • 适合缓存、垃圾收集等场景。

3. 劣势：

   • 不保证严格平衡，最坏情况性能较差。
   • 不适合实时性要求严格的场景。
   • 伸展操作增加常数因子开销。

七、简单示例

插入序列[5,3,7,2,4]并查找4：

1. 插入5：根为5。
2. 插入3：3作为5的左孩子，执行Zig旋转使3成为根。
3. 插入7：7作为5的右孩子（当前根3的右子树），插入后伸展7到根。
4. 插入2：2作为3的左孩子，插入后伸展2到根。
5. 插入4：4作为3的右孩子，插入后执行Zig-Zag旋转使4成为根。
6. 查找4：4已在根位置，无需旋转。

通过这个示例可以看出，最近插入的节点会被移动到根附近，后续访问成本降低。

八、总结

Splay树通过简单的伸展操作实现自调整，利用数据访问的局部性提高性能。虽然不保证绝对平衡，但摊还分析证明其平均效率优秀，且实现相对简单。理解三种旋转情况的区别是掌握伸展操作的关键，实际应用中需根据数据访问模式选择是否使用Splay树。