18.8. Summary of AVL Tree Operations

Try these first

1. 1.

   What is the balance factor of a node with height 3 on the left and height 1 on the right?

   Hint

   Remember balance factor = height of left - height of right.

2. 2.

   What type of rotation is performed for a balance factor of +2?

   Hint

   What action is taken to balance the tree?

3. 3.

   What is the resulting balance factor of a node where the left height is 4 and the right height is 2?

   • -2
   • 2
   • 0

   Hint

   Calculate using the difference of heights.

4. 4.

   True or False: The AVL tree guarantees that the tree remains perfectly balanced at all times.

   • True
   • False

   Hint

   Consider what balance factors allow.

5. 5.

   Given the sequence of integers 10, 20, 30, 40, 50, insert them into an AVL tree and show the necessary rotations.

   Hint

   Draw the tree after each insertion.

6. 6.

   After deleting a node from an AVL tree, describe how you would recheck the balance and what steps would follow for rebalance.

   Hint

   Follow the rebalancing procedures you learned.