17.1.3. Height-Balanced Trees

Try these first

1. 1.

   Define an AVL tree.

   Hint

   Think about the balance criteria for the tree.

2. 2.

   What happens when a node is added to an AVL tree?

   Hint

   Consider the condition for rotations.

3. 3.

   What is the maximum height difference in an AVL tree?

   • 0
   • 1
   • 2
   • 3

   Hint

   Recall the balance criterion for AVL trees.

4. 4.

   True or False: A tree can be an AVL tree if the height difference between subtrees is 2.

   • True
   • False

   Hint

   Think about the definition of an AVL tree.

5. 5.

   Given a series of insertions into an AVL tree (e.g., 10, 20, 30, 25), demonstrate the steps taken during each insertion, including any rotations.

   Hint

   Draw each insertion step to visualize the changes.

6. 6.

   Describe the difference in insertion steps between a regular BST and an AVL tree using examples.

   Hint

   Think of a scenario where an AVL tree becomes unbalanced.