algorithm - Building an AVL Tree out of Binary Search Tree -

i need suggest algorithm takes bst (binary search tree), t1 has 2^(n + 1) - 1 keys, , build avl tree same keys. algorithm should effective in terms of worst , average time complexity (as function of n).

i'm not sure how should approach this. clear minimal size of bst has 2^(n + 1) - 1 keys n (and case if full / balanced), how me?

there straight forward method iterate on tree , each time adding root of t1 avl tree , removing t1:

• since t1 may not balanced delete may cost o(n) in worst case
• insert avl cost o(log n)
• there 2^(n + 1) - 1

so in total cost o(n*logn*2^n) , ridiculously expensive.

but why should remove t1? i'm paying lot there , no reason. figured why not using tree traversal on t1 , , each node i'm visiting , add avl tree:

• there 2^(n + 1) - 1 nodes traversal cost o(2^n) (visiting each node once)
• adding current node each time avl cost o(logn)

so in total cost o(logn * 2^n). , best time complexity think of, question is, can done in faster way? in o(2^n) ? way make insert avl tree cost o(1)?

i hope clear , question belongs here.

thank much,

noam

there algorithm balances bst , runs in linear time called day stout warren algorithm

basically convert bst sorted array or linked list doing in-order traversal (o(n)). then, recursively takes middle element of array, makes root, , makes children middle elements of left , right subarrays respectively (o(n)). here's example,

       unbalanced bst             5           /   \          3     8               / \              7   9             /     \            6      10           sorted array       |3|5|6|7|8|9|10| 

now here recursive calls , 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