avl-tree - 排序列表中的多个AVL树？

Question

我正在处理一个 AVL 树分配，我有一个关于它们的定义的快速问题 - 我们得到一个排序列表，我们必须在 O(n) 时间内从中生成一个 AVL 树。我已经完成了这个（感谢 StackOverflow 的其他帮助！），但我的结果虽然是有效的 AVL 树，但与提供的示例的结果不同。是否可以从同一个排序列表中生成多个 AVL 树？

谢谢！

Answer 1

是的。考虑只有两个节点的树的退化情况。在这种情况下，任何一个节点都可以是根，另一个是叶子。就整体平衡而言，两者是等价的。

Answer 2

是的，例如，以下是 <1,2,3,4,5> 的两种可能的 AVL 树：

(2 1 (3 4 5))

和

(4 (2 1 3) 5)

其中 (a T1 T2) 表示具有根 a、左树 T1 和左右 T2 的树。