Question

Answer the following questions about insertions into the Red-Black Tree shown above.

Important: This tree only works with integers between 1 and 35. Insert one integer into each box, no duplicates allowed.

Inserting _______ will cause a recolouring without a rotation.

Inserting _______ will cause a single rotation. The original root of the subtree rotated upon is _______ and the new root is _______ 

Inserting _______ will require multiple recolourings and/or rotations. In the final rotation, the original root of the subtree rotated upon is _______ and the new root is_______ 

Answer 1

# STAY HOME # STAY SAFE

If we insert 1 then its parent will be 2(red) and uncle will be 6(red) => Recoloring occurs without any rotation => 2 and 6 becomes black and 4 becomes red.

=> Inserting 1 will cause a recoloring without a rotation

If we insert 33 then its parent will be 34(red) and uncle is not present (black) => LL rotation will occur upon the subtree with root 35 and after rotation the new root will be 34.

=> Inserting 33 will cause a single rotation. The original root of the subtree rotated upon is 35 and the new root is 34.

If we insert 8 then its parent will be 9(red) and uncle will be 11(red) => Relocoring occurs => 9 and 11 becomes black and 10 becomes red. Now there is a red-red conflict between 10 and 12 => Rl rotation occurs upon 12 and the new root becomes 10.

=> Inserting 8 will require multiple recolorings and/ or rotations. In the final rotation the original root of the subtree rotated upon is 12 and the new root is 10.