..MindWrite..

The maximum size of the child subtree of a binary complete tree of size n is 2n/3

Posted by guptaradhesh on October 20, 2010

The maximum size of the child subtree of a binary complete tree of size n is 2n/3.  This is also a problem P.131 of the CLR. I liked the approach of proving things given by my TA and then I completed the proof. Here is all-

> The root has two child subtrees – the left one and the right one. Let’s call these subtrees T1 (the left one) and T2 (the right one). One very important property of heap is, in every level, the elements are packed to the leftmost. So if there is an element in the i-th level of T2, then the i-th level of T1 is full.
> By previous point, we may assume that T1 and T2 are both full in their 1st to j-th level, and there are some extra elements in the (j+1)-st level of T1 and T2.
> Here we become greedy. We know that size(T1) >= size(T2), and we want size(T1) as large as possible and size(T2) as small as possible (so that T1 will occupy a greater portion of the total tree). To be greedy, we want the (j+1)-st level of T1 be full, and the (j+1)-st level of T2 be empty.

Now, for this case, let X be the elements in right subtree of a node. Then number of elements in left subtree is X+X = 2X (elements till second last level + elements in last level). Total number of elements = 2X+X = 3X.

So, maximum number of elements a child subtree can have = 2X = 2/3(3X)

Hence Justified.

Advertisements

2 Responses to “The maximum size of the child subtree of a binary complete tree of size n is 2n/3”

  1. arvind said

    sir,please explore how number of elements in left subtree be 2x if no. of elements in right subtree were x a/q to given case?
    i think no of elements in left subtree be 2x+1.plz explain sir.

  2. begeeben said

    I wrote a simple mathematical explanation on this:http://begeeben.wordpress.com/2012/08/20/why-do-subtrees-have-size-at-most-2n3/#more-774

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: