Question

We discussed 3 cases in the red-black tree insertion and 4 cases in the red-black tree deletion on fixing the red-black property. For each of the 3 insertion cases, we showed in class that only the capital-lettered nodes' black heights might change after the rotation and/or recoloring, and we can use a constant time to calculate this change for each capital-lettered node. For each of the 3 insertion cases, we also showed in class that the black height of the parent of the root of the shown subtree remains unchanged after the rotation. and/or recoloring.

a) For each of the 4 deletion cases, show that only the capital-lettered nodes' black heights might change after the rotation and/or recoloring, and we can use a constant time to calculate this change for each capital-lettered node.
b) For each of the 4 deletion cases, verify that the black height of the parent of the root of the shown subtree remains unchanged after the rotation and/or recoloring

Answer 1

In red-black tree deletion, only the capital-lettered nodes' black heights may change, and it can be calculated in constant time. The black height of the parent of the root remains unchanged.

Step-by-step explanation:

a) For each of the 4 deletion cases:

• In case 1, the black height of nodes A, B, and C may change after the rotation and/or recoloring. The change can be calculated in constant time for each capital-lettered node by counting the number of black nodes on the path from the root to that node before and after the rotation/coloring.
• In case 2, the black height of nodes D, E, F, and G may change. Similarly, the change can be calculated in constant time for each capital-lettered node.
• In case 3, the black height of nodes H, I, J, K, L, and M may change. Again, the change can be calculated in constant time for each capital-lettered node.
• In case 4, the black height of nodes N, O, and P may change. The change can be calculated in constant time for each capital-lettered node.

b) For each of the 4 deletion cases:

• In all 4 deletion cases, the black height of the parent of the root of the shown subtree remains unchanged after the rotation and/or recoloring.