3

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

谢谢!

4

2 回答 2

3

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

在此处输入图像描述

于 2011-10-30T19:57:38.810 回答
2

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

(2 1 (3 4 5))

(4 (2 1 3) 5)

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

于 2011-10-30T19:58:51.837 回答