I'm studying for a final exam, and I have a doubt:
According to Gross ("Graph Theory and its applications")
A complete m-ary tree is an m-ary tree in which every internal vertex has exactly m children and all leaves have the same depth
But, isn't it a perfect m-ary tree?
Here is a different definition
http://www.cprogramming.com/tutorial/com…
"(...) More precisely, a complete tree is one that has every level filled in before adding a node to the next level, and one that has the nodes in a given level filled in from left to right, with no breaks. (...)"
Can you help me, please?
Thanks in advance
According to Gross ("Graph Theory and its applications")
A complete m-ary tree is an m-ary tree in which every internal vertex has exactly m children and all leaves have the same depth
But, isn't it a perfect m-ary tree?
Here is a different definition
http://www.cprogramming.com/tutorial/com…
"(...) More precisely, a complete tree is one that has every level filled in before adding a node to the next level, and one that has the nodes in a given level filled in from left to right, with no breaks. (...)"
Can you help me, please?
Thanks in advance
-
Gross's definition is the correct one (for mathematicians).
The C-programming definition you cite is not the mathematical definition.
The author there is making his own definition for "complete".
He should have used a different term, like "properly filled" or something similar.
In graph theory, "complete" means "nothing missing at all".
In the programming example:
http://www.cprogramming.com/tutorial/com…
neither of those trees is complete in the mathematical sense.
A complete binary tree of 3 levels has 7 nodes and 6 edges:
..... 0
.. /..... \
..1 .... ... 2
./ \. .. . / ...\
3 ..4 ...5 ... 6
That guy's "complete" tree (on the left) is missing #5 and #6,
so it is not complete.
In general, for m-ary trees of n levels,
the number of nodes = 1 + m + m^2 + m^3 + ... m^n.
The C-programming definition you cite is not the mathematical definition.
The author there is making his own definition for "complete".
He should have used a different term, like "properly filled" or something similar.
In graph theory, "complete" means "nothing missing at all".
In the programming example:
http://www.cprogramming.com/tutorial/com…
neither of those trees is complete in the mathematical sense.
A complete binary tree of 3 levels has 7 nodes and 6 edges:
..... 0
.. /..... \
..1 .... ... 2
./ \. .. . / ...\
3 ..4 ...5 ... 6
That guy's "complete" tree (on the left) is missing #5 and #6,
so it is not complete.
In general, for m-ary trees of n levels,
the number of nodes = 1 + m + m^2 + m^3 + ... m^n.
-
" What [CLR90, page 95] calls a complete tree, we call a perfect k-ary tree. "
Report Abuse
-
[CLR90, page 95] is "Introduction to Algorithms". And there it's used the term "complete k-ary tree" in the same way as in Gross-Yellen's book
Report Abuse