WARNING! Read the conditions for the problems in this set very carefully! The type of tree and node structure can change from problem to problem.
Assume that for some binary tree node implementation, a pointer requires P bytes and a data object requires D bytes. Further assume that all nodes are implemented to store two pointers and 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.
ANS
The overhead is the space taken up by the pointers to the node's children, as a fraction of all space in the node.
Every node has two pointers and a data field.
The total space is therefore 2*P + D and the
overhead is 2*P.
If you have values like 4/8, reduce to 1/2.
Assume that for some binary tree node implementation, a pointer requires P bytes and a data object requires D bytes. Further assume that we are storing a Full binary tree, that the internal nodes are implemented to store two pointers and a 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.
ANS
The overhead is the space taken up by the pointers to the node's children, as a fraction of all space in the node.
In a full binary tree, half the nodes are leaf nodes and half are internal nodes.
Internal nodes have two pointers and a data field, while leaf nodes have only a data field.
The total space is therefore (2*P/2) + D = P + D and the
overhead is (2*P/2).
If you have values like 4/8, reduce to 1/2.
Assume that for some binary tree node implementation, a pointer requires P bytes and a data object requires D 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.
ANS
The overhead is the space taken up by the pointers to the node's children, as a fraction of all space in the node.
In a full binary tree, half the nodes are leaf nodes and half are internal nodes.
Internal nodes have two pointers, while leaf nodes have only a data field.
The total space is therefore (2*P/2) + (D/2) = P + D/2 and the
overhead is P. It is probably simpler to think
of it as 2*P + D total space
and 2*P overhead.
If you have values like 4/8, reduce to 1/2.