Worst case in Max-Heapify - How do you get 2n/3?

Question

In CLRS, third Edition, on page 155, it is given that in MAX-HEAPIFY,

The children’s subtrees each have size at most 2n/3—the worst case occurs when the bottom level of the tree is exactly half full.

I understand why it is worst when the bottom level of the tree is exactly half full. And it is also answered in this question worst case in MAX-HEAPIFY: "the worst case occurs when the bottom level of the tree is exactly half full"

My question is how to get 2n/3?

Why if the bottom level is half full, then the size of the child tree is up to 2n/3?

How to calculate that?

Thanks

Answer 1

In a tree where each node has exactly either 0 or 2 children, the number of nodes with 0 children is one more than the number of nodes with 2 children.{Explanation: number of nodes at height h is 2^h, which by the summation formula of a geometric series equals (sum of nodes from height 0 to h-1) + 1; and all the nodes from height 0 to h-1 are the nodes with exactly 2 children}

    ROOT   L      R  / \    / \ /   \  /   \ -----  ----- ***** 

Let k be the number of nodes in R. The number of nodes in L is k + (k + 1) = 2k + 1. The total number of nodes is n = 1 + (2k + 1) + k = 3k + 2 (root plus L plus R). The ratio is (2k + 1)/(3k + 2), which is bounded above by 2/3. No constant less than 2/3 works, because the limit as k goes to infinity is 2/3.

Answer 2

Understand the maximum number of elements in a subtree happens for the left subtree of a tree that has the last level half full.Draw this on a piece of paper to realize this.

Once that is clear, the bound of 2N/3 is easy to get.

Let us assume that the total number of nodes in the tree is N.

Number of nodes in the tree = 1 + (Number of nodes in Left Subtree) + (Number of nodes in Right Subtree)

For our case where the tree has last level half full, iF we assume that the right subtree is of height h, then the left subtree if of height (h+1):

Number of nodes in Left Subtree =1+2+4+8....2^(h+1)=2^(h+2)-1 .....(i)

Number of nodes in Right Subtree =1+2+4+8....2^(h) =2^(h+1)-1 .....(ii)

Thus, plugging into:

Number of nodes in the tree = 1 + (Number of nodes in Left Subtree) + (Number of nodes in Right Subtree)

=> N = 1 + (2^(h+2)-1) + (2^(h+1)-1)

=> N = 1 + 3*(2^(h+1)) - 2

=> N = 3*(2^(h+1)) -1

=> 2^(h+1) = (N + 1)/3

Plugging in this value into equation (i), we get:

Number of nodes in Left Subtree = 2^(h+2)-1 = 2*(N+1)/3 -1 =(2N-1)/3 < (2N/3)

Hence the upper bound on the maximum number of nodes in a subtree for a tree with N nodes is 2N/3.