Geek Answers Handbook

Does balancing an AVL tree require more than one turn?

My best guess is that one turn is always enough to balance the AVL tree when inserting or removing an ONE element from an already balanced AVL tree.

Is one turn enough? An example will help us when more than one turn is required.

PS: I consider the RL / LR rotations to be just one rotation.

+4
source share
2 answers

For insert 1 rotation no more.
To remove the number of revolutions is limited to O (log (n)). Log (n) - the height of the tree.
More explanation of AVL removal. When you remove a node from the AVL, you can cause the tree to be unbalanced, which you should track to the point where it is not balanced. If an unbalanced point is the root. You have to rebalance the tree from top to bottom.

+6
source

For input, I believe that this is enough.

but for deletion: consider this tree:

                 50
              /      \
            25       75
           /   \    /   \
          15   40  60    80
               /  /  \    \
              35 55  65   90
                     /
                    62

remove 15, first factor 25 is destroyed, one turn:

                 50
              /      \
            35       75
           /   \    /   \
          25  40  60    80
                  /  \    \
                 55  65   90
                     /
                    62

but, nevertheless, we must check that now the balancing coefficient of the tree root is destroyed, it needs to be rotated again:

                 60
              /      \
            50       75
           /   \     /  \
          35   55   65   80
         /  \       /     \
        25  40     62     90
+4
source

More articles:


All Articles