Consider a version of a binary search tree (BST) for sorted maps that stores additional information...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Consider a version of a binary search tree (BST) for sorted maps that stores additional information as data members of each node w of the tree to account for the smallest and largest keys in the subtree rooted at w. Suppose that we can access this information using w. min, for the smallest integer key, and w.max, for the largest. Algorithm 6 (Node), given below, provides the pseudocode for the constructor of a node in a binary tree with the additional information. Algorithm 6 NODE(k, v, left, right, parent) 1: w new node 2: w.key k 3: w.value v 4: w.left left 5: w.right right 6: w.parent parent 7: w.min k 8: w.max ← k 9: return w Note that this version of the BST data structure must maintain the invariant that the data members w. min and w. max of every node whold the smallest and largest keys in the subtree rooted at w. Hence, both the insertion and removal operations must be properly adapted. Complete the implementation of updatelnfo in Algorithm 8, given below, which would be useful for the adaptation of the the insertion and removal operation. The method takes as input a node w. It has the precondition that all the descendant nodes of w, possibly excluding witself, satisfy the invariant. It has the postcondition that all the ancestors of satisfy the invariant. (Match each missing statement # on the left with the proper operation on the right.) Algorithm 8 UPDATEINFO(w) 1: while w NULL do 2: if w.left 3: 4: 5: 6: 7: 8: 9: 10: Statement 3 Statement 5 Statement 7 Statement 9 Statement 10 else = if w.right else NULL then - NULL then [Choose] [Choose w.min <- w.left.min w.max <-w.right.max w.min <- w.key w <-w.parent w.max <-w.key Choose [Choose ] [Choose ] Consider a version of a binary search tree (BST) for sorted maps that stores additional information as data members of each node w of the tree to account for the smallest and largest keys in the subtree rooted at w. Suppose that we can access this information using w. min, for the smallest integer key, and w.max, for the largest. Algorithm 6 (Node), given below, provides the pseudocode for the constructor of a node in a binary tree with the additional information. Algorithm 6 NODE(k, v, left, right, parent) 1: w new node 2: w.key k 3: w.value v 4: w.left left 5: w.right right 6: w.parent parent 7: w.min k 8: w.max ← k 9: return w Note that this version of the BST data structure must maintain the invariant that the data members w. min and w. max of every node whold the smallest and largest keys in the subtree rooted at w. Hence, both the insertion and removal operations must be properly adapted. Complete the implementation of updatelnfo in Algorithm 8, given below, which would be useful for the adaptation of the the insertion and removal operation. The method takes as input a node w. It has the precondition that all the descendant nodes of w, possibly excluding witself, satisfy the invariant. It has the postcondition that all the ancestors of satisfy the invariant. (Match each missing statement # on the left with the proper operation on the right.) Algorithm 8 UPDATEINFO(w) 1: while w NULL do 2: if w.left 3: 4: 5: 6: 7: 8: 9: 10: Statement 3 Statement 5 Statement 7 Statement 9 Statement 10 else = if w.right else NULL then - NULL then [Choose] [Choose w.min <- w.left.min w.max <-w.right.max w.min <- w.key w <-w.parent w.max <-w.key Choose [Choose ] [Choose ]
Expert Answer:
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these programming questions
-
Do you believe the federal government of Canada should limit the number ofimmigrants it accepts? https://globalnews.ca/news/5397306/canada--poll/immigration
-
Write two or three paragraphs regarding what you have learned about the World Federation of the Deaf, its core values, mission, and especially why they are doing the International Week of Deaf.
-
During the previous year, Nightwork Co's.net sales was $135,000, cost of goods sold was $60,750, operating expenses were $81,000, and other revenues were $13,550. What was Nightwork's gross profit?
-
Shoppers enter Hamilton Place Mall at an average of 120 per hour. What is the probability that at least 35 shoppers will enter the mall between 5:00 and 5:10 pm?
-
The motorcyclist travels with constant velocity along a straight, horizontal, banked road. If he aligns his bike so that the tires are perpendicular to the road at A, determine the frictional force...
-
Consider the following T-bonds, prices are taken on 10.20.2023: Maturity Coupon Bid price Ask price Yield Duration 5/15/2043 2.875% 70.094 70.104 5/15/2043 3.875% 87.216 87.216 8/15/2053 4.125%...
-
Consider the multiple linear regression model fit to the baseball data in Problem 3.41. Problem 3.41 Consider the 2016 major league baseball data in Table B.22. While team ERA was useful in...
-
Z-Bar Pastures is a 160-hectare farm on the outskirts of Swift Current, Saskatchewan, specializing in the boarding of brood mares and their foals. A recent economic downturn in the thoroughbred...
-
For 11, how do we know the vector should be pointing this way? For 12, I do not understand the explanation provided. What is meant by force in new direction? How do we know the trajectory is not...
-
Journal Entry 14 15 17 19 SESSION DATE - APRIL 14, 2023 Memo #4 Dated April 8/23 From Owner: Cheque #5033 for $2 435.60 from Grande Pointe Towers was postdated and the discount period had expired. It...
-
b) A function is defined as follows x < 3 x = 3 x > 3 2 - 1 k f(x) = 8 For what value of k, f(x) is continuous at x = 3?
-
Hedge funds are not risky because, as their name indicates, they hedge risks. Is this statement true, false, or uncertain? Explain.
-
Write up the asset and liability and capital accounts to record the following transactions in the records of D. Mair: 2017 July 1 Started business with 24,000 in the bank. 2 Bought office furniture...
-
What is ERISA, and why was it established?
-
What are the three main proposals for privatizing Social Security? What are their advantages and disadvantages?
-
Why is Social Security in danger of eventually going bankrupt?
-
Consider the system shown in Figure 4-64. The system is at restfor t < O. Assume that the displacement x is the output of thesystem and is measured from the equilibrium position. At t = 0, thecart...
-
The financial statements of Eastern Platinum Limited (Eastplats) are presented in Appendix A at the end of this textbook. Instructions (a) Does East plats report any investments on its statement of...
-
Show that any sequence of m MAKE-SET, FIND-SET, and LINK operations, where all the LINK operations appear before any of the FIND-SET operations, takes only O(m) time if we use both path compression...
-
Prove that every diagonal element of a symmetric positive-definite matrix is positive.
-
Give an efficient algorithm to solve a system Ax b of difference constraints when all of the elements of b are real-valued and a specified subset of some, but not necessarily all, of the unknowns x...
-
Identify and explain the meaning of the term "strategy."
-
Identify and describe the major features of the Strategic Management model.
-
Identify and describe the relationship between the strategy formulation process and the strategy implementation process.
Study smarter with the SolutionInn App