Question

2)

a) Consider a modified red-black tree which satisfies all the usual conditions for a red-black tree exceptthat the root may be either black or red. Suppose a modified red-black tree T has a red root node. If we recolor the root node black, is the resulting tree a “normal” red-black tree?

b)  What is the largest and smallest number of nodes in a red-black tree with black-height k?

Answer 1

1. Yes the resulting tree will be a normal red black tree. Since the root was red, the children would be both black, so if we replace the red node by a black node it would be a normal red- black tree.

2. Black height is the number of black nodes on a path from a node to a leaf, The largest number of nodes in a red-black tree with black height k is
22k-1
and the minimum number of nodes in
2
.

The largest number of black nodes will exist when we have half black and half red nodes and smallest will occur when we have all black nodes.

Also note that by nodes here we mean internal nodes, we are not counting the nil nodes.