CODEWITHSUNDEEP
algorithmdata-structurestime-complexitybinary-search-treeavl-tree
Noam
Noam

Reputation: 1804

Building an AVL Tree out of Binary Search Tree

I need to suggest an algorithm that takes BST (Binary Search Tree), T1 that has 2^(n + 1) - 1 keys, and build an AVL tree with same keys. The algorithm should be effective in terms of worst and average time complexity (as function of n).

I'm not sure how should I approach this. It is clear that the minimal size of a BST that has 2^(n + 1) - 1 keys is n (and that will be the case if it is full / balanced), but how does it help me?

There is the straight forward method that is to iterate over the tree , each time adding the root of T1 to the AVL tree and then removing it from T1:

So in total that will cost O(n*logn*2^n) and that is ridiculously expensive.

But why should I remove from T1? I'm paying a lot there and for no good reason. So I figured why not using tree traversal over T1 , and for each node I'm visiting , add it to the AVL tree:

So in total that will cost O(logn * 2^n). and that is the best time complexity I could think of, the question is, can it be done in a faster way? like in O(2^n) ? Some way that will make the insert to the AVL tree cost only O(1)?

I hope I was clear and that my question belongs here.

Thank you very much,

Noam

Upvotes: 2

Views: 6289

Answers (1)

Chris Gong
Chris Gong

Reputation: 8229

There is an algorithm that balances a BST and runs in linear time called Day Stout Warren Algorithm

Basically all it does is convert the BST into a sorted array or linked list by doing an in-order traversal (O(n)). Then, it recursively takes the middle element of the array, makes it the root, and makes its children the middle elements of the left and right subarrays respectively (O(n)). Here's an example,

       UNBALANCED BST
            5
          /   \
         3     8
              / \
             7   9
            /     \
           6      10


        SORTED ARRAY
      |3|5|6|7|8|9|10|

Now here are the recursive calls and resulting tree,

 DSW(initial array)

             7
 7.left = DSW(left array) //|3|5|6|
 7.right = DSW(right array) //|8|9|10|

             7
            / \
           5   9
 5.left = DSW(|3|)
 5.right = DSW(|6|)
 9.left = DSW(|8|)
 9.right = DSW(|10|)

             7
            / \
           5   9
          / \ / \
         3  6 8 10

Upvotes: 4

Related Questions