Question $1$:$25$ points

A valid Red$-$Black tree should possess the following properties:

Every node is either red or black.

The root is black.

Every leaf is NULL and black.

If a node is red, then both its children are black.

All paths from a node $x$ to any leaf have same number of black nodes in between $($i$.$e$.,$ their Black$-$Height$((x)$ is the same$)$

After insertion of a new key $x$ to the tree, properties $3$ and $5$ may be violated causing the tree to be become unbalanced. These violations can be overcome by rotating the tree around certain nodes and updating their colors, as described in the slides.

$($a$)[10$ points$]$ Consider the Red$-$Black Tree given above. Insert the key $36$ into it$.$ Which cases from the slides are you going to encounter? What rotations would you need to overcome these problematic cases? What will the final tree look like? Explain your answer.

$($Note: You must show the final state in picture and also explain which violation caused you to use which rotation on which node as your progressed through the rebalancing of the tree$)$

$($b$)[10$ points$]$ Asymptotic cost of inserting a new key to a red$-$black tree is $O(logn).$ Why? Explain your answer by showing the math.

$($c$)[5$ points$]$ Where would you use red$-$black trees? Why?