Difference between revisions of "TADM2E 3.5"
From Algorithm Wiki
(Recovering wiki) |
(Prettyprint using math extension) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| 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) $
