Q5. (5+5+5+15 Points) Number of Internal Nodes Let n > 2. We define M(n) to be...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Q5. (5+5+5+15 Points) Number of Internal Nodes Let n > 2. We define M(n) to be the maximum number of internal nodes that can be attained by a 2-3 tree of size n. Similarly, let µ(n) be the minimum number of internal nodes that can be attained by a 2-3 tree of size n. For instance, you should convince yourself of the values in this table: 71 2 3 4 113 5 67 8 9 3 4 4 M(n): μ(n): 1 1 3 3 3 4 4 ? REMEMBER our instruction at the beginning of this homework: you must always briefly justify how your answers, especially answers that requires a single number! (a) What is M(9) and (9) in the above table? (b) Compute M (200). (c) Compute (200). (d) Prove that M (n) ≤ n - 1 for n ≥ 2. HINT: If you look at the above table, you see that M (n) < n - 1 is true. When do you get M(n) = n - 1 in the table? Outline of an inductive Proof: Let the level profile of the 2-3 tree of height h>1 and size n > 2 be (lo, ls,... lk) where lo 1 and , - n. We must prove that lo + ls + + lr-2 + ln-1 ≤ lr-1=n-1. Use induction on h. Don't forget to work out the base case where h = 1. Q5. (5+5+5+15 Points) Number of Internal Nodes Let n > 2. We define M(n) to be the maximum number of internal nodes that can be attained by a 2-3 tree of size n. Similarly, let µ(n) be the minimum number of internal nodes that can be attained by a 2-3 tree of size n. For instance, you should convince yourself of the values in this table: 71 2 3 4 113 5 67 8 9 3 4 4 M(n): μ(n): 1 1 3 3 3 4 4 ? REMEMBER our instruction at the beginning of this homework: you must always briefly justify how your answers, especially answers that requires a single number! (a) What is M(9) and (9) in the above table? (b) Compute M (200). (c) Compute (200). (d) Prove that M (n) ≤ n - 1 for n ≥ 2. HINT: If you look at the above table, you see that M (n) < n - 1 is true. When do you get M(n) = n - 1 in the table? Outline of an inductive Proof: Let the level profile of the 2-3 tree of height h>1 and size n > 2 be (lo, ls,... lk) where lo 1 and , - n. We must prove that lo + ls + + lr-2 + ln-1 ≤ lr-1=n-1. Use induction on h. Don't forget to work out the base case where h = 1.
Expert Answer:
Answer rating: 100% (QA)
23 Trees 23 tree is a tree data structure in which every internal node nonleaf node has either one d... View the full answer
Related Book For
Algorithm Design And Applications
ISBN: 9781118335918
1st Edition
Authors: Michael T. Goodrich, Roberto Tamassia
Posted Date:
Students also viewed these programming questions
-
How do you Sales Forecast and an Expense forecast for future years?
-
The following additional information is available for the Dr. Ivan and Irene Incisor family from Chapters 1-5. Ivan's grandfather died and left a portfolio of municipal bonds. In 2012, they pay Ivan...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
? Fisheries Bhd is a small listed company involves in fishing and selling fish to the public via retail outlets. The company owns a building that was acquired in early September 2014 for RM1,200,000,...
-
Randy's Rentals reported the following on its year-end balance sheets: Randy's rents space to a number of tenants, all of whom pay their monthly rent on the 10th of the following month. Randy's...
-
Urban Elite Cosmetics has used a traditional cost accounting system to apply quality-control costs uniformly to all products at a rate of 14.5 percent of direct-labor cost. Monthly direct-labor cost...
-
What approach(es) are used to analyze impairment on available-for-sale and held-to-maturity debt securities?
-
Inara Serra Co. uses special journals and a general journal. The following transactions occurred during May 2012. May 1 I. Serra invested $50,000 cash in the business. 2 Sold merchandise to Morena...
-
Compute an amortization schedule for a $19600, 10 year annual amortization loan, paying 9.8%. Payments are to be made at the beginning of the year. Suppose that you are only able to pay $2600 in the...
-
Is there evidence consistent with gender discrimination in training level? To answer this, proceed as follows: a. Create a table of counts for the two qualitative variables gender and training level....
-
Read Case Study 5.1 and answer the following three questions: Cite and support two reasons from the case study which have led to a shift in evaluating performance. Name and discuss two positive...
-
Use the following novel 'Colonial Discourse and Post-Colonial Theory :A Reader By Patrick Williams, Laura Chrisman" to respond to the following. write an essay on a topic that relates to...
-
Discuss the role of women and children as agents of resistance against neocolonialism in Ngugi wa Thiongo Trial of Dedan Kimathi
-
Describe context in communication
-
How would public speaking expand ones professional network
-
Why education is considered a science
-
we went over the example of the Geico Gecco. Please tell me why you think the Gecco has been such a successful marketing campaign for Geico.
-
The executor of Gina Purcells estate has recorded the following information: Assets discovered at death (at fair value): Cash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....
-
Describe how to modify the MaxsubFastest algorithm so that it uses just a single loop and, instead of computing n + 1 different Mt values, it maintains just a single variable M.
-
Show that the SUBSET-SUM problem is in NP.
-
Suppose you are given a sorted set, S, of n items, stored in a binary search tree. How many different range queries can be done where both of the values, k 1 and k 2 , in the query range [k 1 , k 2 ]...
-
8. Ryder leased a truck to Florida Food Service; Powers, an employee, drove it to make deliveries. He noticed that the door strap used to close the rear door was frayed, and he asked Ryder to fix it....
-
9. A new truck, manufactured by General Motors Corp. (GMC), stalled in rush hour traffic on a busy interstate highway because of a defective alternator, which caused a complete failure of the truck's...
-
10. A prison inmate bit a hospital employee. The employee sued the state for negligence and lack of supervision, claiming a fear of AIDS. The plaintiff had tested negative for HIV three times, and...
Study smarter with the SolutionInn App