Geek Answers Handbook

How to create an AVL tree from ArrayList values ​​in O (n) time?

My purpose is to create an AVL tree from a list of sorted arrays of values ​​in O (n) time, where n is the number of values

I am 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 is inserted that causes an imbalance in the tree, I have to do another loop to find a node that is asymmetrical and apply rotation (s) to rebalance the tree.

Any help is much appreciated, thanks!

+4
source share
2 answers

How to simply create a complete balanced tree with several nodes at the lowest level, possibly missing, for example, for 6 elements, create

  o
     / \
    oo
   / \ /
  ooo

Then do the usual move, and when you visit the ith node, set its key to [i].

This is a valid AVL tree, since each node has left and right children, whose height differs by no more than one.

The source tree can be built in O (n), and is like in O (n), so the complexity is O (n).

By the way, in a semidefinite note, there is a method called heapify for constructing a heap (mix or max) from an array of integers, which is O (n) for an array of length n, even if the insert into the heap is O (log n) - the trick is to do it from bottom to top.

+5
source

Insert O(logn) , so it is true that no one can do better than O(nlogn) when pasting. Indeed, you should not embed AVL in the tree. You just have to create a tree. Create all nodes and select values ​​from the array when creating new nodes. Do not find / look for the desired value, just take it, the array is sorted.

Given a list containing 5 elements and sorted, for example [1,2,3,4,5] , what will be the root of the tree? How about 7 items? ten?...

After you get the root, what will be the root of the left subtree. Which list to see? What part of the list should you keep in the left subtree?

What all.

-1
source

More articles:


All Articles