题解思路

问题理解与分析

我们需要模拟一种特殊的二叉搜索树（spaly）的五种操作，并计算每次操作的代价。这种树的特殊之处在于只使用单旋操作（zig/zag）来调整结构。

五种操作：

1. 插入：按BST规则插入，代价 = 插入后新节点的深度
2. 单旋最小值：将最小节点单旋到根，代价 = 旋转前该节点的深度
3. 单旋最大值：将最大节点单旋到根，代价 = 旋转前该节点的深度
4. 删除最小值：先单旋最小值到根，然后删除根，代价同操作2
5. 删除最大值：先单旋最大值到根，然后删除根，代价同操作3

核心洞察

1. 单旋操作的性质

单旋操作（zig/zag）的特点是：

• 每次旋转使目标节点的深度减少1
• 旋转到根需要进行的旋转次数 = 初始深度 - 1
• 但题目只关心旋转前的深度作为代价

2. 树的特殊结构

由于只对最小值和最大值进行单旋，这会导致树呈现特殊形态：

• 最小值总是在最左链上
• 最大值总是在最右链上
• 单旋操作会改变树的结构，但保持BST性质

算法框架

方法：直接模拟 + 优化维护

我们需要维护以下信息：

• 树的根节点
• 每个节点的父节点、左右孩子、深度
• 最小值和最大值节点的引用（用于快速访问）

步骤1：插入操作

1. 如果树为空，新节点为根，深度=1，代价=1
2. 否则从根开始，按BST规则找到插入位置：
   • 如果key < 当前节点，往左子树走
   • 如果key > 当前节点，往右子树走
   • 直到找到空位置
3. 插入新节点，计算深度，返回深度作为代价

步骤2：单旋最小值/最大值

1. 找到最小/最大值节点（最左/最右节点）
2. 记录当前深度作为代价
3. 通过zig/zag操作将其旋转到根：
   • 如果是左孩子，执行zig操作
   • 如果是右孩子，执行zag操作
   • 重复直到成为根

步骤3：删除操作

1. 先执行对应的单旋操作（最小值或最大值）
2. 此时根没有左子树（删除最小值）或没有右子树（删除最大值）
3. 直接删除根，让唯一的子树成为新根

关键技术细节

1. 深度维护策略

在旋转操作中，深度的变化：

• 旋转节点深度减少1
• 旋转节点的原父节点深度增加1
• 其他节点深度不变

可以在旋转时直接更新相关节点的深度。

2. 极值节点维护

为了快速找到最小值和最大值：

• 最小值：总是最左节点，插入时更新
• 最大值：总是最右节点，插入时更新
• 删除后需要重新查找极值

3. 旋转操作实现

复杂度分析

• 插入操作：$O(h)$，需要找到插入位置
• 单旋操作：$O(h)$，需要旋转h-1次
• 删除操作：$O(h)$，先单旋再删除
• 最坏情况：$O(m^2)$（树退化为链）
• 期望情况：$O(m \log m)$

样例分析

对于样例：

操作序列：
1 2 → 插入2，树：2(根)，深度=1，代价=1
1 1 → 插入1，树：2(根)-1(左)，深度=2，代价=2  
1 3 → 插入3，树：2(根)-1(左),3(右)，深度=2，代价=2
4   → 单旋删除最小值：单旋1(深度=2)到根，代价=2
5   → 单旋删除最大值：单旋3(深度=2)到根，代价=2

输出：1, 2, 2, 2, 2

优化策略

1. 路径压缩

在查找插入位置时，可以记录路径，便于后续操作。

2. 懒惰更新

如果不是每次都需要精确深度，可以延迟更新。

3. 极值缓存

维护最小值和最大值节点，避免每次从头遍历。

实现要点

1. 节点结构

2. 旋转实现：确保所有指针正确更新

3. 深度更新：在结构变化时递归更新深度

4. 空树处理：注意边界情况

特殊情况处理

• 空树：插入第一个节点时特殊处理
• 单节点树：删除后树为空
• 极值节点：最小/最大值可能是根节点

总结

这道题的关键在于：

1. 理解单旋操作：掌握zig/zag的具体实现
2. 深度计算：准确维护节点深度信息
3. 极值查找：快速定位最小值和最大值
4. 指针维护：在旋转和删除时正确更新所有关系

通过直接模拟所有操作，我们可以准确计算每种操作的代价。虽然最坏复杂度较高，但在实际数据中通常可以接受。