18.1. Case When Slope is -1

Try these first

1. 1.

   What does a slope of -1 in a binary search tree indicate?

   Hint

   Think about the relationship between the heights of the left and right subtrees.

2. 2.

   How do you perform a rotation in a binary search tree?

   Hint

   Consider how you would restructure the tree while maintaining its properties.

3. 3.

   If the slope of a tree is -1, what does it indicate?

   • The left subtree is taller.
   • The right subtree is taller.
   • The tree is perfectly balanced.

   Hint

   Think about the definition of slope related to height.

4. 4.

   True or False: A slope of -1 requires at least one rotation to restore balance.

   • True
   • False

   Hint

   Consider the conditions under which rebalancing is required.

5. 5.

   You have a binary search tree where multiple insertions have caused a slope of -1. Show the steps you would take to rebalance it through rotations.

   Hint

   Remember the conditions for each type of rotation.

6. 6.

   If you delete a node from an AVL tree that causes an imbalance leading to a slope -1, explain how you would restore balance through rotations.

   Hint

   Make sure you check slopes at the affected nodes after adjustments.