Question $5$

Mark the following statements as true or false and provide explanations for your answers. No explanation gets $0$ points.

$($a$)$ A red$-$black tree insertion requires $O(1)$ rotations in the worst case.

$($b$)$ A red$-$black tree insertion requires $O(1)$ node recoloring in the worst case.

$($c$)$ Walking a red$-$black tree with $n$ nodes in pre$-$order takes $(nlogn).$