Difference between revisions of "TADM2E 3.5"

From Algorithm Wiki
Jump to: navigation, search
(Prettyprint using math extension)
 
(One intermediate revision by the same user not shown)
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>
 
<math>
−
\frac{4n}{4n + 4*2*(n-1)} = \frac{4}{4 + 8} = \frac{1}{3} (n\to\infty)
+
\frac{Data}{Data + 3*Pointers} = \frac{4}{4 + 3*4} = \frac{1}{4}
 
</math>
 
</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
+
<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) $

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