0

Take the following tree:

          50                 
        40 
      30 
    20 
  10

Which node will be balanced first? 50 or 30

Case 1: 50
The tree is 

             30
          20    40
       10          50

Case 2: 30
The tree is 

              40
            /   \
          20     50
       10    30

Well, both are AVL Trees, so are both correct?

Improve this question
1
  • If you ask me I'd do 30 first, but what about 50? Commented Jan 6, 2011 at 16:33

3 Answers 3

Reset to default
5

Your first tree is not an AVL tree. Even minus an element it is not an AVL tree (so we can't even consider it as an AVL tree undergoing balance).

AVL operations are defined on AVL trees to produce a new AVL tree. They are defined in terms of the node that was inserted or deleted.

So, we don't have an AVL tree to start, and we have no information about how we got that tree (was something just inserted or deleted, and if so, what?). In short, I think the question needs to be clarified.

Improve this answer
3
  • That was exactly what I thought. Saw this in a book (Case 1). Talk about bad authors :) Commented Jan 8, 2011 at 5:19
  • if the OP provides an insertion order then we'll know what the tree will look like. Commented Nov 9, 2011 at 20:05
  • Exactly the tree to begin with is left heavy - which it would never have been if it were balanced as nodes were added to it. How can you "balance" something which has the operation undefined on it? Commented Nov 9, 2011 at 20:45
1

It is easier to think about the problem recursively by balancing 30 prior to 50. Since leaf nodes (with no child nodes) are already balanced, you can balance the tree in a bottom up fashion knowing that all nodes below the current node are balanced trees.

Improve this answer
0

z5h is right. If you want an AVL tree you have to build it, adding the elements one by one and balancing if necessary.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.