17.1.1. Operations on Search Trees

Try these first

1. 1.

   What does the term 'height' refer to in a tree?

   Hint

   Think about how we measure paths.

2. 2.

   What is an AVL tree?

   Hint

   Recall the full name of the tree!

3. 3.

   What is the maximum allowable slope in an AVL tree?

   • 3
   • 1
   • 2

   Hint

   Revisit how slopes function in balancing.

4. 4.

   True or False: An AVL tree can have two subtrees with height differences of more than two nodes.

   • True
   • False

   Hint

   Think back to what defines an AVL tree.

5. 5.

   You are given an AVL tree. Insert the value 15, drawing the tree and showing rotations needed to maintain AVL properties.

   Hint

   Visualize where the imbalance occurs after insertion.

6. 6.

   Consider an unbalanced binary tree. Convert it into an AVL tree through rotations and explain each step.

   Hint

   Pay attention to rebalancing like in earlier examples.