如何在O(n)时间内从ArrayList创建一个AVL树？

Question

我的任务是在O(n)时间内从排序的数组值列表中创建一个AVL树,其中n是值的数量

我一直在努力,但我不能得到O(n)时间,我能得到的最好的是O(nlog(n))

我的问题是,每次插入导致树不平衡的节点时,我必须做另一个循环来找到不平衡的节点并应用旋转以再次平衡树.

非常感谢任何帮助,谢谢!

Answer 1

如何创建一个完整的平衡树,可能缺少最低级别的一些节点,例如6个元素

      o
    /   \
   o     o
  / \    /
 o   o  o

然后执行inorder walk,当您访问第i个节点时,将其键设置为A [i].

这是一个有效的AVL树,因为每个节点都有一个左右孩子,其高度最多相差一个.

原始树可以用O(n)构造,并且inorder遍历O(n),因此复杂度是O(n).

顺便提一下,在一个半自由的音符上,有一种叫做heapify的技术,用于构建一个整数数组的堆(混合或最大),这个整数数组是长度为n的数组的O(n),即使插入堆中的是O(log n) ) - 诀窍是自下而上.

Answer 2

插入就是如此，没有人能比插入时O(logn)做得更好。O(nlogn)实际上，您不应该插入AVL 树。您应该只创建树。创建所有节点并在构建新节点时从数组中选取值。不要查找/搜索您需要的值，只需取它即可，数组已排序。

例如，给定一个包含 5 个元素且已排序的列表，[1,2,3,4,5]树的根是什么？7个元素怎么样？10？...？

得到根之后，那么左子树的根就是什么。要看什么清单？列表的哪一部分必须存储在左子树中？

就这样。