用3种不同的AVL树代表AVL树

Question

出于某种原因，我需要构造 1 个 AVL 树，但用 3 个不同的 AVL 树表示它并保持树之间的平衡，例如，对于具有 15 个节点的 AVL 树，横向按顺序时的前 5 个应该位于第一棵树中下一棵树中的第二个 5 等等...

假设键是整数，您需要从树中插入/删除节点

示例：如果AVL树的中序横向输出为1,2,3,4,5,6

它应该由3棵AVL树表示 (1,2)(3,4)(5,6) 也可以是 (2,1)(3,4)(5,6) 每棵树的顺序并不重要。

我想不出保持树之间平衡的算法

Answer 1

实现此目的的一个务实方法是：

• 跟踪三棵树中每棵树的节点数量
• 跟踪每棵树中的最小和最大值

我不会在下面的算法中明确提及这些属性的更新，但请注意在需要时更新它们。

插入

1. 选择最左边的树，其最大值大于要插入的值。如果没有这样的树，则选择最正确的树。

2. 在该树中进行通常的 AVL 插入，包括适当时的标准 AVL 重新平衡。

3. 如果这棵树恰好比节点数最少的树多 2 个节点，则检查较小的树相对于当前树的位置：

   • 如果在左边，则从较大的树中删除最小值，并将其插入到紧邻左侧的树中（从顶部重复该过程）

   • 如果它在右侧，则从较大的树中删除最大值并将其插入到紧邻右侧的树中（从顶部重复该过程）

4. 此时所有约束均已满足。

删除

1. 根据每棵树的最小最大信息找到必须具有目标值的树

2. 对该树执行标准 AVL 删除算法。

3. 如果该树中的节点数比最大的树少 2，则检查更大的树在哪里，然后：

   • 如果较大的树在左侧，则从较小的树的左邻居中获取最大值，并将其插入到当前树中，最后从左邻居中删除它（从顶部重复当前过程）
   • 如果较大的树在右侧，则从较小的树的直接右邻居中获取最大值，并将其插入到当前树中，最后从右邻居中删除它（从顶部重复当前过程）

4. 此时所有约束均已满足。