Question

Assume that for some binary tree node implementation, a pointer requires 4 bytes and a data object requires 28 bytes. Further assume that we are storing a Full binary tree, that the internal nodes are implemented to store only two pointers (no data field), and that the leaf nodes store only a data field. Type a fraction (like "1/2") that represents the fraction of the total space taken up by overhead. Give your fraction in lowest terms.

Answer 1

The fraction of total space taken up by overhead in the binary tree implementation is (2n + 5) / (7n), where 'n' is the number of leaf nodes.

Step-by-step explanation:

To calculate the overhead for the binary tree implementation, we need to consider the space occupied by the pointers and the data objects. Let's assume the tree has 'n' leaf nodes. Since each internal node has two pointers and no data field, the space occupied by internal nodes would be 2 * 4 * (n - 1). The space occupied by the leaf nodes would be 28 * n. The total space occupied by the tree would be the sum of these two values.

Overhead = ((2 * 4 * (n - 1)) + (28 * n)) / (n * 28) = (8 * n - 8 + 28) / (28 * n) = (8n + 20) / (28n) = (2n + 5) / (7n)

Therefore, the fraction of total space taken up by overhead is (2n + 5) / (7n). This fraction cannot be further simplified as it is already in its lowest terms.