Difference between revisions of "TADM2E 3.5"

From Algorithm Wiki
Jump to: navigation, search
(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)
Line 1: Line 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:  
+
1: Each node is identical, so the ratio of data over total should be: <br>
  
−
<math>
+
4 / (4 + 3*4) = 1/4
−
\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: <br>
  
−
<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
+
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 04:55, 29 December 2016

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

Retrieved from "https://algorist.com/algowiki_v2/index.php?title=TADM2E_3.5&oldid=479"