Difference between revisions of "TADM2E 3.5"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Prettyprint using math extension)
 
(3 intermediate revisions by 3 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 / (4 + 3*4) = 1/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: &lt;br&gt;
+
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
+
<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) $