Binary Tree and Overhead fraction Calculation
Find the overhead fraction (the ratio of data space over total space) for each of the following binary tree implementations on n nodes:
2) Only leaf nodes store data; internal nodes store two child pointers. The data field requires four bytes and each pointer requires two bytes.
Above is a question from Steven Skiena Algorithm Design Manual. The answer on the wiki says:
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.
I dont understand above explanation since we are given n nodes. How can you say n leaf nodes?
I calculated it in a different way. Assume we have a balanced binary tree. Let L be number of leaf nodes. Then number of internal nodes is L-1.
$$L + L-1 = n$$
$$L =n+1/2$$
$$L-1 =n-1/2$$
We can now calculate the overhead fraction as:
$$(n+1/2) * 4 / (n+1/2) * 4 + (n-1/2) * 4 $$
$$(n+1/2) / (n+1/2) + (n-1/2) $$
$$(n+1) / 2n $$
Can some help me figure out if my answer is correct ?
algorithms trees
edited Aug 18 at 15:07
HugoTeixeira
3281313
asked Jul 10 '13 at 2:36
gopal
819
add a comment |
Find the overhead fraction (the ratio of data space over total space) for each of the following binary tree implementations on n nodes:
2) Only leaf nodes store data; internal nodes store two child pointers. The data field requires four bytes and each pointer requires two bytes.
Above is a question from Steven Skiena Algorithm Design Manual. The answer on the wiki says:
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.
I dont understand above explanation since we are given n nodes. How can you say n leaf nodes?
I calculated it in a different way. Assume we have a balanced binary tree. Let L be number of leaf nodes. Then number of internal nodes is L-1.
$$L + L-1 = n$$
$$L =n+1/2$$
$$L-1 =n-1/2$$
We can now calculate the overhead fraction as:
$$(n+1/2) * 4 / (n+1/2) * 4 + (n-1/2) * 4 $$
$$(n+1/2) / (n+1/2) + (n-1/2) $$
$$(n+1) / 2n $$
Can some help me figure out if my answer is correct ?
algorithms trees
edited Aug 18 at 15:07
HugoTeixeira
3281313
asked Jul 10 '13 at 2:36
gopal
819
If you have $L+L-1=n$ then $L=(n/2)+(1/2)$, not $n+(1/2)$.
– Rick Decker
Jul 10 '13 at 14:06
add a comment |
Find the overhead fraction (the ratio of data space over total space) for each of the following binary tree implementations on n nodes:
2) Only leaf nodes store data; internal nodes store two child pointers. The data field requires four bytes and each pointer requires two bytes.
Above is a question from Steven Skiena Algorithm Design Manual. The answer on the wiki says:
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.
I dont understand above explanation since we are given n nodes. How can you say n leaf nodes?
I calculated it in a different way. Assume we have a balanced binary tree. Let L be number of leaf nodes. Then number of internal nodes is L-1.
$$L + L-1 = n$$
$$L =n+1/2$$
$$L-1 =n-1/2$$
We can now calculate the overhead fraction as:
$$(n+1/2) * 4 / (n+1/2) * 4 + (n-1/2) * 4 $$
$$(n+1/2) / (n+1/2) + (n-1/2) $$
$$(n+1) / 2n $$
Can some help me figure out if my answer is correct ?
algorithms trees
edited Aug 18 at 15:07
HugoTeixeira
3281313
asked Jul 10 '13 at 2:36
gopal
819
Find the overhead fraction (the ratio of data space over total space) for each of the following binary tree implementations on n nodes:
2) Only leaf nodes store data; internal nodes store two child pointers. The data field requires four bytes and each pointer requires two bytes.
Above is a question from Steven Skiena Algorithm Design Manual. The answer on the wiki says:
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.
I dont understand above explanation since we are given n nodes. How can you say n leaf nodes?
I calculated it in a different way. Assume we have a balanced binary tree. Let L be number of leaf nodes. Then number of internal nodes is L-1.
$$L + L-1 = n$$
$$L =n+1/2$$
$$L-1 =n-1/2$$
We can now calculate the overhead fraction as:
$$(n+1/2) * 4 / (n+1/2) * 4 + (n-1/2) * 4 $$
$$(n+1/2) / (n+1/2) + (n-1/2) $$
$$(n+1) / 2n $$
Can some help me figure out if my answer is correct ?
algorithms trees
algorithms trees
edited Aug 18 at 15:07
HugoTeixeira
3281313
asked Jul 10 '13 at 2:36
gopal
819
edited Aug 18 at 15:07
HugoTeixeira
3281313
asked Jul 10 '13 at 2:36
gopal
819
edited Aug 18 at 15:07
HugoTeixeira
3281313
edited Aug 18 at 15:07
HugoTeixeira
3281313
edited Aug 18 at 15:07
HugoTeixeira
3281313
3281313
asked Jul 10 '13 at 2:36
gopal
819
asked Jul 10 '13 at 2:36
gopal
819
asked Jul 10 '13 at 2:36
gopal
819
819
If you have $L+L-1=n$ then $L=(n/2)+(1/2)$, not $n+(1/2)$.
– Rick Decker
Jul 10 '13 at 14:06
add a comment |
If you have $L+L-1=n$ then $L=(n/2)+(1/2)$, not $n+(1/2)$.
– Rick Decker
Jul 10 '13 at 14:06
If you have $L+L-1=n$ then $L=(n/2)+(1/2)$, not $n+(1/2)$.
– Rick Decker
Jul 10 '13 at 14:06
If you have $L+L-1=n$ then $L=(n/2)+(1/2)$, not $n+(1/2)$.
– Rick Decker
Jul 10 '13 at 14:06
add a comment |
1 Answer
1
active
oldest
votes
The method makes the total number of nodes 2n not n as the question says. But for calculation of overhead fraction it does not matter since we take ratio. According to the question I think you should use:
Number of leaves $= 0.5cdot n$
Number of internal nodes$= 0.5cdot n-1$ (this a theorem of full binary tree i.e number of internal nodes is $1$ less than the number of leaves)
So now calculate total number of nodes its equal to
$$
(text{leaves} +text{internal nodes}+ text{root})=0.5cdot n+0.5cdot n-1+1 = n
$$
Now according to the problem :
Space occupied by pointers=space occupied by internal nodes and root since leaves store no data $=(0.5cdot n-1+1)cdot 2cdot p=0.5cdot ncdot 2cdot p$ (Let $p$ be the amount of space allocated to pointer for you its $4$ bytes. $2cdot p$ because each note has $2$ pointers)
Space occupied by data$= 0.5cdot ncdot d $(d for you is again $4$ bytes)
Another thing I think is OVERHEAD fraction
$$
frac{text{space taken by pointer}}{text{space taken by data+space taken by pointer}}
$$
[not the reciprocal]
Therefore overhead fraction
$$
=frac{0.5cdot ncdot 2cdot p}{(0.5cdot ncdot 2cdot p)+(0.5cdot ncdot d)}=frac{2cdot p}{2cdot p+d}
$$
Hope this helps.If I am wrong please tell me. :)
edited May 12 '15 at 20:18
quapka
1,251719
answered May 12 '15 at 19:44
Jeeco
11
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f440137%2fbinary-tree-and-overhead-fraction-calculation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
The method makes the total number of nodes 2n not n as the question says. But for calculation of overhead fraction it does not matter since we take ratio. According to the question I think you should use:
Number of leaves $= 0.5cdot n$
Number of internal nodes$= 0.5cdot n-1$ (this a theorem of full binary tree i.e number of internal nodes is $1$ less than the number of leaves)
So now calculate total number of nodes its equal to
$$
(text{leaves} +text{internal nodes}+ text{root})=0.5cdot n+0.5cdot n-1+1 = n
$$
Now according to the problem :
Space occupied by pointers=space occupied by internal nodes and root since leaves store no data $=(0.5cdot n-1+1)cdot 2cdot p=0.5cdot ncdot 2cdot p$ (Let $p$ be the amount of space allocated to pointer for you its $4$ bytes. $2cdot p$ because each note has $2$ pointers)
Space occupied by data$= 0.5cdot ncdot d $(d for you is again $4$ bytes)
Another thing I think is OVERHEAD fraction
$$
frac{text{space taken by pointer}}{text{space taken by data+space taken by pointer}}
$$
[not the reciprocal]
Therefore overhead fraction
$$
=frac{0.5cdot ncdot 2cdot p}{(0.5cdot ncdot 2cdot p)+(0.5cdot ncdot d)}=frac{2cdot p}{2cdot p+d}
$$
Hope this helps.If I am wrong please tell me. :)
edited May 12 '15 at 20:18
quapka
1,251719
answered May 12 '15 at 19:44
Jeeco
11
add a comment |
The method makes the total number of nodes 2n not n as the question says. But for calculation of overhead fraction it does not matter since we take ratio. According to the question I think you should use:
Number of leaves $= 0.5cdot n$
Number of internal nodes$= 0.5cdot n-1$ (this a theorem of full binary tree i.e number of internal nodes is $1$ less than the number of leaves)
So now calculate total number of nodes its equal to
$$
(text{leaves} +text{internal nodes}+ text{root})=0.5cdot n+0.5cdot n-1+1 = n
$$
Now according to the problem :
Space occupied by pointers=space occupied by internal nodes and root since leaves store no data $=(0.5cdot n-1+1)cdot 2cdot p=0.5cdot ncdot 2cdot p$ (Let $p$ be the amount of space allocated to pointer for you its $4$ bytes. $2cdot p$ because each note has $2$ pointers)
Space occupied by data$= 0.5cdot ncdot d $(d for you is again $4$ bytes)
Another thing I think is OVERHEAD fraction
$$
frac{text{space taken by pointer}}{text{space taken by data+space taken by pointer}}
$$
[not the reciprocal]
Therefore overhead fraction
$$
=frac{0.5cdot ncdot 2cdot p}{(0.5cdot ncdot 2cdot p)+(0.5cdot ncdot d)}=frac{2cdot p}{2cdot p+d}
$$
Hope this helps.If I am wrong please tell me. :)
edited May 12 '15 at 20:18
quapka
1,251719
answered May 12 '15 at 19:44
Jeeco
11
add a comment |
The method makes the total number of nodes 2n not n as the question says. But for calculation of overhead fraction it does not matter since we take ratio. According to the question I think you should use:
Number of leaves $= 0.5cdot n$
Number of internal nodes$= 0.5cdot n-1$ (this a theorem of full binary tree i.e number of internal nodes is $1$ less than the number of leaves)
So now calculate total number of nodes its equal to
$$
(text{leaves} +text{internal nodes}+ text{root})=0.5cdot n+0.5cdot n-1+1 = n
$$
Now according to the problem :
Space occupied by pointers=space occupied by internal nodes and root since leaves store no data $=(0.5cdot n-1+1)cdot 2cdot p=0.5cdot ncdot 2cdot p$ (Let $p$ be the amount of space allocated to pointer for you its $4$ bytes. $2cdot p$ because each note has $2$ pointers)
Space occupied by data$= 0.5cdot ncdot d $(d for you is again $4$ bytes)
Another thing I think is OVERHEAD fraction
$$
frac{text{space taken by pointer}}{text{space taken by data+space taken by pointer}}
$$
[not the reciprocal]
Therefore overhead fraction
$$
=frac{0.5cdot ncdot 2cdot p}{(0.5cdot ncdot 2cdot p)+(0.5cdot ncdot d)}=frac{2cdot p}{2cdot p+d}
$$
Hope this helps.If I am wrong please tell me. :)
edited May 12 '15 at 20:18
quapka
1,251719
answered May 12 '15 at 19:44
Jeeco
11
The method makes the total number of nodes 2n not n as the question says. But for calculation of overhead fraction it does not matter since we take ratio. According to the question I think you should use:
Number of leaves $= 0.5cdot n$
Number of internal nodes$= 0.5cdot n-1$ (this a theorem of full binary tree i.e number of internal nodes is $1$ less than the number of leaves)
So now calculate total number of nodes its equal to
$$
(text{leaves} +text{internal nodes}+ text{root})=0.5cdot n+0.5cdot n-1+1 = n
$$
Now according to the problem :
Space occupied by pointers=space occupied by internal nodes and root since leaves store no data $=(0.5cdot n-1+1)cdot 2cdot p=0.5cdot ncdot 2cdot p$ (Let $p$ be the amount of space allocated to pointer for you its $4$ bytes. $2cdot p$ because each note has $2$ pointers)
Space occupied by data$= 0.5cdot ncdot d $(d for you is again $4$ bytes)
Another thing I think is OVERHEAD fraction
$$
frac{text{space taken by pointer}}{text{space taken by data+space taken by pointer}}
$$
[not the reciprocal]
Therefore overhead fraction
$$
=frac{0.5cdot ncdot 2cdot p}{(0.5cdot ncdot 2cdot p)+(0.5cdot ncdot d)}=frac{2cdot p}{2cdot p+d}
$$
Hope this helps.If I am wrong please tell me. :)
edited May 12 '15 at 20:18
quapka
1,251719
answered May 12 '15 at 19:44
Jeeco
11
edited May 12 '15 at 20:18
quapka
1,251719
edited May 12 '15 at 20:18
quapka
1,251719
edited May 12 '15 at 20:18
quapka
1,251719
1,251719
answered May 12 '15 at 19:44
Jeeco
11
answered May 12 '15 at 19:44
Jeeco
11
answered May 12 '15 at 19:44
Jeeco
11
11
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f440137%2fbinary-tree-and-overhead-fraction-calculation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
If you have $L+L-1=n$ then $L=(n/2)+(1/2)$, not $n+(1/2)$.
– Rick Decker
Jul 10 '13 at 14:06