18. AVL Tree Rotations

Try these first

1. 1.

   What is the balance factor in AVL trees?

   Hint

   It's related to the heights of current node's children.

2. 2.

   Define a left rotation.

   Hint

   Think about which way the tree is rotating.

3. 3.

   What does a balance factor of -2 indicate?

   • The left subtree is heavier
   • The right subtree is heavier
   • The tree is balanced

   Hint

   Think about how height differences affect balance.

4. 4.

   When is a left rotation performed?

   • True
   • False

   Hint

   Recall when imbalance necessitates rotative adjustments.

5. 5.

   Given a series of values to insert into an AVL tree, demonstrate the rebalancing steps needed to maintain balance. List the rotations performed after each insertion.

   Hint

   Refer to individual balance factors after each node is added to check for required rotations.

6. 6.

   Create a visual representation of an AVL tree before and after a series of rotations. What does this tell about the efficiency of AVL balancing relative to normal BSTs?

   Hint

   Be attentive to height imbalances when comparing the two tree types.