17.1.2. Notions of Balance

Try these first

1. 1.

   Define a balanced search tree.

   Hint

   Think about what balanced means in terms of tree height.

2. 2.

   What is the key property of AVL trees?

   Hint

   Consider what the abbreviation 'AVL' stands for.

3. 3.

   What defines an AVL tree?

   • A complete binary tree
   • A height-balanced binary tree
   • A linear tree structure

   Hint

   Remember the property of height differences in AVL trees.

4. 4.

   True or False: The maximum height difference allowed in AVL trees is 2.

   • True
   • False

   Hint

   Recall the definition of height balance in AVL trees.

5. 5.

   Design an AVL tree and perform a series of insertions and deletions, showing how you handle rebalancing each time. Provide both the initial tree and the final balanced tree.

   Hint

   Keep track of the height differences and slopes for balance restoration.

6. 6.

   Given a sequence of numbers to insert into an AVL tree, make predictions about the shape of the tree with each insertion. Describe the reasoning behind expected rotations.

   Hint

   Think about how each number affects the height of subtrees.