Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 11: Q26E (page 756)

A full \({\bf{m - }}\)ary tree \(T\) has \(81\) leaves and height \(4\).

\({\bf{a)}}\)Give the upper and lower bounds for \({\bf{m}}\).

\({\bf{b)}}\)What is \({\bf{m}}\) if \(T\) is also balanced?

A complete \({\bf{m - }}\)ary tree is a full \({\bf{m - }}\)ary tree in which every leaf is at the same level.

Short Answer

Expert verified

(a) Lower bound 3 and upper bound 21 .

(b) m=3

Step by step solution

Achieve better grades quicker with Premium

  • Unlimited AI interaction
  • Study offline
  • Say goodbye to ads
  • Export flashcards
Start your free trial Skip

Over 22 million students worldwide already upgrade their learning with Vaia!

01

Using the theorem \(4\left( {iii} \right)\)

A m-ary tree is a tree where every internal vertex has exactly m children.

A m-ary tree of height h is balanced if the leaves are at levels h or h-1.

Theorem \(4\left( {iii} \right)\): A full m-ary tree with l leaves has \(n = \frac{{ml - 1}}{{m - 1}}\) vertices and \(i = \frac{{l - 1}}{{m - 1}}\) internal vertices.

Given: the full m-ary tree has 81 leaves and height 4.

\(l = 81\)

By theorem \(4\left( {iii} \right)\), the number of internal vertices is:

\(i = \frac{{l - 1}}{{m - 1}} = \frac{{81 - 1}}{{m - 1}} = \frac{{80}}{{m - 1}}\)

Since the number of internal vertices needs to be an integer, m-1 needs to divide 80 . The divisors of 80 are:

\(m - 1 = 1,2,4,5,8,10,16,20,40 or 80\)

02

(a) Substitute the values for \({\bf{m}}\)

The possible values of m are then the divisors of 80 increased by 1:

\(m = 2,3,5,6,9,11,17,21,41\)or 81

If m=2 and the height is 4, then the number of vertices is at most \(1 + 2 + 4 + 8 + 16 = 31\) (as each vertex can have 2 children) and thus we cannot obtain 81 leaves. Thus m=2 is not possible.

If m=3 and the height is 4, then the number of vertices is at most \(1 + 3 + 9 + 27 + 81 = 152\) (as each vertex can have 3 children) and thus we can obtain 81 leaves. Thus m=3 is possible. Similar for all values of m larger than 3 and up to 21. If \(m > 21\), then we have more than \(1 + 21 + 21 + 21 + 21 = 85\) vertices (as each vertex can have 21 children or no children). Moreover, the tree with one vertex with children at each level has exactly 81 leaves, thus if the number of children per level increase, then we will obtain more than 81 leaves. Thus \(m > 21\) is not possible. The possible values of m are then restricted to \(3 \le m \le 21\).

03

(b) Finding the number of leaves

The tree is balanced, if the levels only occur at the last 2 levels. Note that a balanced full m-ary tree then contains \(1 + m + {m^2}\) vertices in the first 3 levels.

At level 3, there are \({m^3}\) vertices and at level 4, there are at least m vertices. The total number of leaves is then at least \({m^3} - 1 + m\).

Since there can be at most \({m^4}\) leaves at level 4, there can be at most \({m^4}\) leaves.

\({m^3} - 1 + m \le Number of leaves \le {m^4}\)

When m=3, then the maximum number of leaves is \({m^4} = {3^4} = 81\) and thus there exists a balanced tree with height 4 and 81 leaves when m=3

When m=5, then the minimum number of leaves of a balanced full m-tree is \({m^3} - 1 + m = {5^3} - 1 + 5 = 129\) and thus there does not exists a balanced tree with height 4 and 81 leaves when \(m \ge 5\).

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

a. Explain how to use preorder, in-order, and post-order traversals to find the pre-fix, in-fix, and post-fix forms of an arithmetic expression.

b. Draw the ordered rooted tree that represents \({\bf{((x - 3) + ((x/4) + (x - y)}} \uparrow {\bf{3))}}\)

c. Find the pre-fix and post-fix forms of the expression in part \(\left( {\bf{b}} \right)\).

Show that if no two edges in a weighted graph have the same weight, then the edge with least weight incident to a vertex v is included in every minimum spanning tree.

Sollin's algorithm produces a minimum spanning tree from a connected weighted simple graph \({\bf{G = (V,E)}}\) by successively adding groups of edges. Suppose that the vertices in \({\bf{V}}\) are ordered. This produces an ordering of the edges where \({\bf{\{ }}{{\bf{u}}_{\bf{0}}}{\bf{,}}{{\bf{v}}_{\bf{0}}}{\bf{\} }}\) precedes \({\bf{\{ }}{{\bf{u}}_{\bf{1}}}{\bf{,}}{{\bf{v}}_{\bf{1}}}{\bf{\} }}\) if \({{\bf{u}}_{\bf{0}}}\) precedes \({{\bf{u}}_{\bf{1}}}\) or if \({{\bf{u}}_{\bf{0}}}{\bf{ = }}{{\bf{u}}_{\bf{1}}}\) and \({{\bf{v}}_{\bf{0}}}\) precedes \({{\bf{v}}_{\bf{1}}}\). The algorithm begins by simultaneously choosing the edge of least weight incident to each vertex. The first edge in the ordering is taken in the case of ties. This produces a graph with no simple circuits, that is, a forest of trees (Exercise \({\bf{24}}\) asks for a proof of this fact). Next, simultaneously choose for each tree in the forest the shortest edge between a vertex in this tree and a vertex in a different tree. Again the first edge in the ordering is chosen in the case of ties. (This produces a graph with no simple circuits containing fewer trees than were present before this step; see Exercise \({\bf{24}}\).) Continue the process of simultaneously adding edges connecting trees until \({\bf{n - 1}}\) edges have been chosen. At this stage a minimum spanning tree has been constructed.

Show that the addition of edges at each stage of Sollin’s algorithm produces a forest.

Show that if there are \(r\) trees in the forest at some intermediate step of Sollin’s algorithm, then at least \(\left\lceil {\frac{r}{2}} \right\rceil \)edges are added by the next iteration of the algorithm.

Find a maximum spanning tree for the weighted graph in Exercise\(3\).
See all solutions

Recommended explanations on Math Textbooks

Geometry

Read Explanation

Statistics

Read Explanation

Decision Maths

Read Explanation

Discrete Mathematics

Read Explanation

Logic and Functions

Read Explanation

Applied Mathematics

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free