AVL rotations and red-black rules

Questions 1 to 5 of 9

1. 1. Put these steps in the order an AVL tree repairs itself after an insert.

   Use the arrows to put the steps in order.

   1. 1.Find the first node on the way up whose balance factor is +2 or -2↑↓
   2. 2.Pick the case from the heavy child's lean and rotate at that node↑↓
   3. 3.Walk back up to the root and update each node's height↑↓
   4. 4.Add the new value as a leaf, the same way a plain BST does↑↓
2. 2. Node 30 has balance factor +2, and its left child 20 has balance factor +1. Which case is this, and what is the fix?

   RR, one left rotation at 30LL, one right rotation at 30LR, a left rotation at 20 and then a right rotation at 30RL, a right rotation at 20 and then a left rotation at 30
3. 3. During an AVL insert, the heavy child of the bad node can have a balance factor of 0.

   True, because a child with two equal sides needs a double rotationFalse, because the child just grew taller on one side, so its balance is +1 or -1
4. 4. Put these steps in the order for the RL delete case. After deleting 10, node 20 has balance -2, and its right child 30 leans left (+1).

   Use the arrows to put the steps in order.

   1. 1.Rotate node 30 right, so its left child 25 moves up↑↓
   2. 2.Rotate node 20 left, so 25 moves to the top of the subtree↑↓
   3. 3.Find node 20 with balance -2, and see that its right child 30 leans the opposite way↑↓
5. 5. A red-black tree holds 7 keys. What is the largest height the bound from the lesson allows?

   37146