# Difference between revisions of "TADM2E 3.5"

From Algorithm Wiki

(Recovering wiki) |
(Recovering wiki) |
||

Line 1: | Line 1: | ||

− | 1: Each node is identical, so the ratio of data over total should be: | + | 1: Each node is identical, so the ratio of data over total should be: <br> |

4 / (4 + 3*4) = 1/4 | 4 / (4 + 3*4) = 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: | + | 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 / (4*n + 4*(n-1)) = 4*n / 4 * (n + n -1) = n / 2*n - 1, this approaches 1/2 as n gets large | 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 |

## Revision as of 18:22, 11 September 2014

1: Each node is identical, so the ratio of data over total should be:

4 / (4 + 3*4) = 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:

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