2

AVL Trees seem to have four kinds of transformations: Left-Left, Left-Right, Right-Left, and Right-Right. However, it seems like there could be other circumstances as well. I submit this as Left-Balanced:

enter image description here

Neither Left nor Right rotations can balance this tree. What algorithm would one use to balance it?

Mark Karavan
  • 2,654
  • 1
  • 18
  • 38
  • AV&L did _not_ give a procedure to balance _any_ ordered binary tree into an AVL tree with "at most one double rotation". They presented how to re-balance a binary tree after an insertion of a single node using but one of three states/two extra bits per node. This was extended to other operations. None of the three "left" trees shown above can be the result of adding a single node to a valid AVL tree, each might result from deleting one node deserving a label greater than 50. That said, what (in terms of height) _is_ different in the nodes labelled 40 and 45 between the "last two left trees"? – greybeard Dec 22 '15 at 09:51

2 Answers2

3

Both LL and LR can be applied here

        50
       /  \
     40    55
    /  \
  35    45
  / \   / \
34  36 44 46

After first LR turn:

           50
          /  \
        45   55
       /  \
     40    46
    /  \
  35    44
  / \
34  36

After second LR turn:

        45
       /  \
     40    50
    / \    / \
  35  44  46  55
 / \
34  36

This is the valid AVL tree. Note that

In an AVL tree, the heights of the two child subtrees of any node differ by at most one

You can also do the LL turn:

     40
    /  \
  35    50
  / \   / \
34  36 45  55
       /\
     44  46

Again this is the valid AVL tree.

1

I think you can't get the left-balance case. Because if you built the left-balance one, you may get the left-left or left-right first, then the tree would rotate and keep balance.

lancelot
  • 11
  • 3