Difference between revisions of "TADM2E 3.5"
From Algorithm Wiki
(Undo revision 457 by Letientai299 (talk), the hypothesis is that all node is identical, so the child pointers in the leaf node count as overhead even if not connected) |
(Prettyprint using math extension) |
||
| Line 1: | Line 1: | ||
1: Each node is identical, so the ratio of data over total should be: <br> | 1: Each node is identical, so the ratio of data over total should be: <br> | ||
| − | 4 | + | <math> |
| + | \frac{Data}{Data + 3*Pointers} = \frac{4}{4 + 3*4} = \frac{1}{4} | ||
| + | </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: <br> | 2: In a full tree, given n leaf nodes, there are n-1 internal nodes. Both leaf and internal nodes are worth 4 bytes: <br> | ||
| − | 4*n | + | <math> |
| + | \frac{\text{Size of Leafs}}{\text{Size of Leaf} + \text{Size of Internal Nodes}} = \frac{4 * n}{4*n + 4*(n-1)} = \frac{n}{2n-1} = \frac{1}{2} (n\to\infty) | ||
| + | </math> | ||
Latest revision as of 05:06, 29 December 2016
1: Each node is identical, so the ratio of data over total should be:
$ \frac{Data}{Data + 3*Pointers} = \frac{4}{4 + 3*4} = \frac{1}{4} $
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{\text{Size of Leafs}}{\text{Size of Leaf} + \text{Size of Internal Nodes}} = \frac{4 * n}{4*n + 4*(n-1)} = \frac{n}{2n-1} = \frac{1}{2} (n\to\infty) $
