What is a "complete m-ary tree"
Favorites|Homepage
Subscriptions | sitemap
HOME > Mathematics > What is a "complete m-ary tree"

What is a "complete m-ary tree"

[From: ] [author: ] [Date: 11-08-13] [Hit: ]
..Can you help me, please?Thanks in advance-Grosss definition is the correct one (for mathematicians).The C-programming definition you cite is not the mathematical definition.......
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

-
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.

-
" 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

1
keywords: quot,ary,What,complete,tree,is,What is a "complete m-ary tree"
New
Hot
© 2008-2010 http://www.science-mathematics.com . Program by zplan cms. Theme by wukong .