TADM2E 3.5

From Algorithm Wiki
Revision as of 09:59, 19 October 2016 by Letientai299 (Talk | contribs)

Jump to: navigation, search

1: A tree with $ n $ nodes would have $ n-1 $ edges, because our internal nodes have both parent and child pointers, we can say that the number of pointers is equal to the double of edges. So, the ratio of data over total should be:

$ \frac{4n}{4n + 4*2*(n-1)} = \frac{4}{4 + 8} = \frac{1}{3} (n\to\infty) $

2: In a full tree, given n leaf nodes, there are n-1 internal nodes. Both leaf and internal nodes are worth 4 bytes:

$ \frac{4*n}{(4*n + 4*(n-1))} = \frac{4*n}{4 * (n + n -1)} = \frac{n}{2*n - 1} $, this approaches $ \frac{1}{2} $ as n gets large