如何用3棵平衡AVL树表示单棵AVL树并维护平衡及支持增删？

核心思路 #

将逻辑上的单棵AVL树，按其中序遍历序列的连续键值区间拆分为3棵独立AVL树，通过维护区间边界和子树节点数阈值，在插入/删除操作时保证每棵子树的AVL平衡特性，同时维持分段的合理性。

1. 分段规则定义 #

均分场景（节点数为3的倍数） #

比如15个节点的情况，将中序序列平均分为3段，每段节点数相等。通过逻辑树的第n/3小节点和第2n/3小节点确定区间边界：

• 第一棵树：所有键 ≤ 第n/3小节点
• 第二棵树：键 > 第n/3小节点 且 ≤ 第2n/3小节点
• 第三棵树：键 > 第2n/3小节点

非均分场景（节点数非3的倍数） #

按「前⌊n/3⌋、中⌈n/3⌉、后⌊n/3⌋」的近似规则分配，边界同样由对应排名的节点确定。比如6个节点时，前2、中2、后2，边界为第2小和第4小节点。

2. 关键状态维护 #

需要维护两个边界值：

• split1：第一棵树的最大键
• split2：第二棵树的最大键

这两个值可通过子树的getMax()/getMin()方法快速获取，无需遍历整个逻辑树。每次节点数变化后，检查子树节点数是否偏离阈值（比如与目标数差超过1），若超出则触发区间调整。

3. 插入操作流程 #

• 对比待插入键与split1、split2，确定所属子树
• 在目标子树执行标准AVL插入操作（插入后检查平衡因子，旋转调整）
• 检查子树节点数是否超出阈值：
  • 若第一棵树节点过多：将其最大节点转移到第二棵树，更新split1为第一棵树新的最大键
  • 若第二棵树节点过多：根据溢出方向，将最小节点移到第一棵树或最大节点移到第三棵树，更新对应边界值
  • 若第三棵树节点过多：将其最小节点转移到第二棵树，更新split2为第二棵树新的最大键
• 转移节点时，目标子树同样执行标准AVL插入，保证自身平衡

4. 删除操作流程 #

• 根据待删除键确定所属子树，执行标准AVL删除操作（删除后检查平衡因子，旋转调整）
• 检查子树节点数是否低于阈值：
  • 若第一棵树节点过少：从第二棵树转移最小节点到第一棵树，更新split1
  • 若第二棵树节点过少：从节点数较多的相邻子树（第一或第三）转移边界节点，更新对应边界值
  • 若第三棵树节点过少：从第二棵树转移最大节点到第三棵树，更新split2
• 转移节点时，源子树执行标准AVL删除，目标子树执行插入，均维持AVL平衡

关键注意事项 #

• 所有子树的平衡逻辑复用标准AVL树的旋转调整，无需修改核心算法
• 区间调整的触发阈值设为「子树节点数与目标值差超过1」，避免频繁调整
• 边界值的更新依赖子树的极值查询，需保证AVL树支持O(logk)时间的极值查询（k为子树节点数）

示例验证 #

以中序序列1,2,3,4,5,6为例：

1. 初始分段：第一棵树{1,2}、第二棵{3,4}、第三棵{5,6}，split1=2，split2=4
2. 插入7：属于第三棵树，插入后第三棵树为{5,6,7}，AVL平衡（无需旋转）
3. 删除2：第一棵树仅剩{1}，触发调整，从第二棵树转移3到第一棵树。此时第一棵树为{1,3}（AVL平衡），第二棵树为{4}，split1更新为3

内容的提问来源于stack exchange，提问作者3xhaust