Vtyjkyuk

Find the overhead fraction (the ratio of data space over total space) for each of the following binary tree implementations on n nodes:

2) Only leaf nodes store data; internal nodes store two child pointers. The data field requires four bytes and each pointer requires two bytes.

Above is a question from Steven Skiena Algorithm Design Manual. The answer on the wiki says:

In a full tree, given n leaf nodes, there are n-1 internal nodes. Both leaf and internal nodes are worth 4 bytes:
$4*n / (4*n + 4*(n-1))$ = $4*n / 4 * (n + n -1) = n / 2*n - 1$, this approaches 1/2 as n gets large.

I dont understand above explanation since we are given n nodes. How can you say n leaf nodes?

I calculated it in a different way. Assume we have a balanced binary tree. Let L be number of leaf nodes. Then number of internal nodes is L-1.
$$L + L-1 = n$$
$$L =n+1/2$$

$$L-1 =n-1/2$$

We can now calculate the overhead fraction as:

$$(n+1/2) * 4 / (n+1/2) * 4 + (n-1/2) * 4 $$

$$(n+1/2) / (n+1/2) + (n-1/2) $$

$$(n+1) / 2n $$

Can some help me figure out if my answer is correct ?

The method makes the total number of nodes 2n not n as the question says. But for calculation of overhead fraction it does not matter since we take ratio. According to the question I think you should use:

Number of leaves $= 0.5cdot n$
Number of internal nodes$= 0.5cdot n-1$ (this a theorem of full binary tree i.e number of internal nodes is $1$ less than the number of leaves)

So now calculate total number of nodes its equal to
$$
(textleaves +textinternal nodes+ textroot)=0.5cdot n+0.5cdot n-1+1 = n
$$

Now according to the problem :

Space occupied by pointers=space occupied by internal nodes and root since leaves store no data $=(0.5cdot n-1+1)cdot 2cdot p=0.5cdot ncdot 2cdot p$ (Let $p$ be the amount of space allocated to pointer for you its $4$ bytes. $2cdot p$ because each note has $2$ pointers)

Space occupied by data$= 0.5cdot ncdot d $(d for you is again $4$ bytes)

Another thing I think is OVERHEAD fraction
$$
fractextspace taken by pointertextspace taken by data+space taken by pointer
$$
[not the reciprocal]

Therefore overhead fraction
$$
=frac0.5cdot ncdot 2cdot p(0.5cdot ncdot 2cdot p)+(0.5cdot ncdot d)=frac2cdot p2cdot p+d
$$

Hope this helps.If I am wrong please tell me. :)