AVL rotations and red-black rules

Questions 1 to 5 of 9

1. 1. The tree is 20 at the root, with 10 on its left and 30 on its right. The left child of 30 is 25. Delete 10. Put these steps in the order the AVL repair runs.

   Use the arrows to put the steps in order.

   1. 1.Rotate right at 30, which lifts 25 and straightens the path 20, 25, 30↑↓
   2. 2.Delete 10, so the root 20 has balance factor -2↑↓
   3. 3.Rotate left at 20, which lifts 25 to the root↑↓
2. 2. Keys 10, 30 and 20 are inserted in that order into an empty AVL tree. Which case does the repair use?

   LR at 10RL at 10LL at 10RR at 10
3. 3. An AVL tree has a root with balance factor -2 whose right child has balance factor +1. What two-letter name does the lesson give this case?

   Type your answer.

4. 4. After a delete, the heavy child of an unbalanced node can have balance factor 0, so one rotation can fix the node. Is this true, and why?

   True, because the removed key was on the lighter side, so the heavy child can end up with equal heights on both sidesFalse, because a heavy child always has a balance factor of +1 or -1, even after a delete
5. 5. Put these steps of the height-bound argument in order, for any path from the root to a null spot in a red-black tree.

   Use the arrows to put the steps in order.

   1. 1.So the path has at most as many red nodes as black nodes↑↓
   2. 2.The height of the tree is at most 2b, which is twice the black height↑↓
   3. 3.Every path has the same black count b, so the path has at most 2b nodes↑↓
   4. 4.Match each red node on the path with the black node just before it↑↓