Fix size boundary height of 2-3-4 Tree

The bound of height (fix size) of 2-3-4Tree

#define floor(n) is the largest integer that is smaller than real number n#define ceil(n) is the smallest integer that is larger than real number n#define lg n as log base 2 n 

Ans : floor ( lg (3n + 1) / 2 ) <= h <= ceil ( lg (n + 1) ) 

Proof

Assume we are fixing height h, find the maximum number of nodes:

Then the maximum number of nodes would be every node is 4-node:

So the number of nodes N

=  1 + 4 + 4^2 + 4^3 + … + 4^ (h – 1) = (4^(h) – 1) / 3

Then 

3N + 1 = 4 ^ (h)

lg (3N + 1) = 2h

h = lg (3N + 1) / 2

**Note that fix height h, got maximum number of nodes, So when we fix number of nodes, we will get min height

Similarly, assume we are fixing height h, find the minimum number of nodes:

Then the minimum number of nodes would be every node is 2-node:

So the number of nodes N

=  1 + 2 + 2^2 + 2^3 + … + 2^ (h – 1) = (2^(h) – 1

Then N + 1 = 2 ^ (h)

lg (N + 1) = h

h = lg (N + 1)

**Note that fix height h, got minimum number of nodes, So when we fix number of nodes, we will get max height