Q5. (5+5+5+15 Points) Number of Internal Nodes Let n > 2. We define M(n) to be...

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.

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