Question $3$

Consider an initially empty red$-$black tree. Insert the following numbers into the redblack tree:

Insert $41.$

Insert $38.$

Insert $31.$

Insert $12.$

Insert $19.$

Insert $8.$

Insert $6.$

Show your work step by step for each insertion and rotation $($if needed$)$ with the color of each node $($For every insertion, continue from the last version of the tree, with all the numbers before are inserted$).$

Question $4$

To compute the depth of a given node in an RBT in constant time, consider augmenting the depths of nodes as additional attributes in the nodes of the RBT$.$ Please explain by an example why this augmentation increases the asymptotic time complexity of inserting a node into an RBT in the worst case.