Difference between revisions of "TADM2E 3.5"
From Algorithm Wiki
(Recovering wiki) |
Letientai299 (talk | contribs) |
||
| Line 1: | Line 1: | ||
| − | 1: | + | 1: A tree with <math>n</math> nodes would have <math>n-1</math> 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: |
| − | 4 | + | <math> |
| + | \frac{4n}{4n + 4*2*(n-1)} = \frac{4}{4 + 8} = \frac{1}{3} (n\to\infty) | ||
| + | </math> | ||
| − | 2: In a full tree, given n leaf nodes, there are n-1 internal nodes. Both leaf and internal nodes are worth 4 bytes: | + | 2: 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 | + | <math> \frac{4*n}{(4*n + 4*(n-1))} = \frac{4*n}{4 * (n + n -1)} = \frac{n}{2*n - 1}</math>, this approaches <math>\frac{1}{2}</math> as n gets large |
Revision as of 09:59, 19 October 2016
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
