This is the question :

A Red$-$Black tree is a type of Binary tree in which each node is either red or black. The trees are self

balancing and as such, maintain consistent logarithmic complexity for insert, delete and search methods.

Red Back trees have several basic rules:

$$ The root must be black

$$ Each node is either red or black

$$ Red nodes cannot have red children

$$ Black Property: Every path from a node to its descendant null nodes $($leaves$)$ has the same number

of black nodes.

$$ Leaf Property: All leaves $($NIL nodes$)$ are black.

Assume that this tree is a full tree, prove using structural induction that the max height is $2$ log$($n $+1),$

where n is the number of nodes. $[$Hint: Consider the number of vertices, and determine the cases for

adding a red node or a black node.$]$