17.1.4. AVL Trees

Try these first

1. 1.

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

   Hint

   Balance factor is calculated as left height minus right height.

2. 2.

   Name one operation that can be performed to maintain AVL tree balance.

   Hint

   Think of how we change tree structure.

3. 3.

   What defines an AVL tree?

   • A tree that is completely filled on all levels
   • A tree where left and right heights differ by at most 1
   • A tree that allows duplicates

   Hint

   Think about what it means for trees to be balanced.

4. 4.

   True or False: An AVL tree can have a balance factor of 2.

   • True
   • False

   Hint

   Remember the balance definition in AVL trees.

5. 5.

   Create a balanced AVL tree and explain each step performed during insertions and any rotations applied.

   Hint

   Keep track of the balance factors after each insertion.

6. 6.

   Consider a deletion in an AVL tree. Explain how you can determine if a tree is still balanced after an element is removed.

   Hint

   How do heights change from a deletion action?