如何在 O(n) 时间内从值的 ArrayList 创建 AVL 树？
我的任务是在 O(n) 时间内从排序的值数组列表创建一个 AVL 树，其中 n 是我一直在处理此问题的值的数量
，但我无法获得 O(n) 时间，我能得到的最好是O(nlog(n))
我的问题是，每次插入导致树不平衡的节点时，我都必须执行另一个循环来找到不平衡的节点并应用旋转来再次平衡树。
非常感谢任何帮助，谢谢！
My assignment is to create an AVL Tree from a sorted array list of values in O(n) time where n is the number of values
I have been working on this but I cannot get O(n) time, the best I can get is O(nlog(n))
My problem is that every time a node that causes the tree to be unbalanced is inserted, I have to do another loop to find the node that is unbalanced and apply rotation(s) to balance the tree again.
Any help is greatly appreciated, thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如何只创建一个完整的平衡树，最低层的一些节点可能会丢失，例如，对于 6 个元素，创建
o / \ o o / \ / o o o然后进行中序遍历，当您访问第 i 个节点时，将其键设置为 A[i ]。
这是一个有效的 AVL 树，因为每个节点都有一个左右子节点，其高度最多相差 1。
原始树的构造时间为 O(n)，中序遍历的时间为 O(n)，因此复杂度为 O(n)。
顺便说一句，有一个半相关的说明，有一种称为 heapify 的技术，用于从整数数组中构建堆（混合或最大），对于长度为 n 的数组，该数组的复杂度为 O(n)，即使插入到堆中的复杂度为 O(log n ) - 诀窍是自下而上。
How about just creating a complete balanced tree, with a few nodes at the lowest level possibly missing, e.g., for 6 elements, create
o / \ o o / \ / o o oThen do an inorder walk, and when you visit the i-th node, set its key to A[i].
This is a valid AVL tree, since every node has a left and right child whose heights differ by at most one.
The original tree can be constructed in O(n), and the inorder walk in O(n), so the complexity is O(n).
Incidentally, on a semirelated note, there's a technique called heapify for building a heap (mix or max) out of an array of integers that's O(n) for a length n array, even though the insertion into a heap is O(log n) - the trick is to do it bottom up.
插入的时间复杂度为
O(logn)，确实如此，插入时没有人能比O(nlogn)做得更好。实际上，您不应该插入到 AVL 树中。您应该只创建树。创建所有节点并在构建新节点时从数组中选取值。不要查找/搜索您需要的值，只需取它即可，数组已排序。给定一个包含 5 个元素且已排序的列表，例如
[1,2,3,4,5]，树的根是什么？ 7个元素怎么样？ 10？ ...？得到根之后，那么左子树的根就是什么。要看什么清单？列表的哪一部分必须存储在左子树中？
就这样。
Inserting is
O(logn), so true, nobody can do better thanO(nlogn)when inserting. Really, you shouldn't insert into the AVL-tree. You should just create the tree. Create all the nodes and pick the values from the array as you are constructing new nodes. Don't find/search the value you need, just take it, the array is sorted.Given a list that contains 5 elements and is sorted, for example
[1,2,3,4,5], what would be the root of the tree? How about for 7 elements? 10? ...?After you got the root, then what would be the root of the left subtree. What's the list to look at? Which part of the list do you have to store in the left subtree?
That's all.