Question

What is the minimum number of nodes in a red-black tree of height 8?

Answer 1

Minimum number of nodes in a red-block tree: h + 1 on the right path and necessary nodes on the left sub trees.

 

For a tree with height h, the black –height is greater than or equal to h/s.

 

Therefore for n internal nodes the height will be,

h ≤ 2 lg(n + 1)

 

To find minimum n:

h ≤ 2 lg(n + 1)

8/2 ≤ 2lg(n + 1)

4 ≤ log2(n + 1)

4 = log2(n + 1)

n + 1 = 2^4

n + 1 = 16

n = 15

 

Thus the minimum number of nodes is 15.

Thus the minimum number of nodes is 15.