TADM2E 3.5
From Algorithm Wiki
Revision as of 04:55, 29 December 2016 by Joky (talk | contribs) (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)
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
