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 Complete the pseudocode for the put function in Algorithm 9, given below. The auxiliary method makeChild(p, c, leftChild?) properly modifies the data structure so as to make node c the left child of node p if the leftChild? predicate is true; otherwise, it makes c the right child of p. The auxiliary function findNode(w, k) outputs the last internal (i.e., not NULL) node visited while searching for keyk in the subtree rooted at node w; or NULL if that subtree is empty (i.e., w = NULL). Algorithm 9 PUT(T, k, v) 1: 2: if p = NULL and p.key 3: 4: 5: 6: if p = p = NULL then 7: 8: else 9: 10: UPDATEINFO(p) 11: return w Statement 1 Statement 3 Statement 5 Statement 7 return p Statement 9 = k then [Choose ] [Choose] p.value <-v T.root <- w w<- Node(k,v,NULL,NULL.p) makeChild(p.w.k<p.key) p <- findNode(T.root,k) 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 Complete the pseudocode for the put function in Algorithm 9, given below. The auxiliary method makeChild(p, c, leftChild?) properly modifies the data structure so as to make node c the left child of node p if the leftChild? predicate is true; otherwise, it makes c the right child of p. The auxiliary function findNode(w, k) outputs the last internal (i.e., not NULL) node visited while searching for keyk in the subtree rooted at node w; or NULL if that subtree is empty (i.e., w = NULL). Algorithm 9 PUT(T, k, v) 1: 2: if p = NULL and p.key 3: 4: 5: 6: if p = p = NULL then 7: 8: else 9: 10: UPDATEINFO(p) 11: return w Statement 1 Statement 3 Statement 5 Statement 7 return p Statement 9 = k then [Choose ] [Choose] p.value <-v T.root <- w w<- Node(k,v,NULL,NULL.p) makeChild(p.w.k<p.key) p <- findNode(T.root,k) 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?
-
Write a program to Sort the list U,N,I,V,E,R,S,I,T,Y in alphabetical order by Bubble sort I want the complete solution steps with the solution to the question
-
Let the ordered sample observations be denoted by y1, y2, ..., yn (y1 being the smallest and yn the largest). Our suggested check for normality is to plot the (-1((i -.5) / n),yi) pairs. Suppose we...
-
The unadjusted trial balance for GLP Corporation appears on the next page. End-of-period analysis revealed the following: a. The market value of equipment had decreased by 30 percent of its original...
-
What role does cash play in the restructuring of a company through acquisitions and divestitures?
-
Northwestern Savings and Loan has a current capital structure consisting of $250,000 of 16% (annual interest) debt and 2,000 shares of common stock. The firm pays taxes at the rate of 40%. a. Using...
-
Match each definition with its related term by selecting the appropriate term from the dropdown options that follow each definition.
-
Prepare a December 31 trial balance for Jindal Company using the following information and fill in the missing amount for Equipment (assume all data are correct). Cash Accounts payable Services...
-
Looking at The Constitution of Athens' criticisms of democracy, and Pericles defense of Democracy, what are your thoughts? Is Democracy really just a dumb idea we've let get too far out of hand? Or is
-
Explain the role the judiciary plays in the checks and balances of government. What are the requirements to be appointed to the U.S. Supreme Court? Can the courts change a law and should judges make...
-
Windsor, Inc. has had 4 years of record earnings. Due to this success, the market price of its 350,000 outstanding shares of $2 par value common stock has increased from $6 per share to $52. During...
-
The Walton Toy Company manufactures a line of dolls and a sewing kit. Demand for the company's products is increasing, and management requests assistance from you in determining an economical sales...
-
The accountant of Swift Inc. was preparing for the audit of its financial statements for the year ended December 31, 2022, and discovered that an automobile was being incorrectly depreciated. The...
-
3. A lease agreement that qualifies as a finance lease calls for annual lease payments of $30,000 over a seven-year lease term (also the asset's useful life), with the first payment on January 1, the...
-
! Create a rational function with an x-intercept at (3,0) and a y-intercept at (0,-1). Explain your process. (You can switch between the math and text keyboard.) Next
-
Ex. (17): the vector field F = x i-zj + yz k is defined over the volume of the cuboid given by 0x a,0 y b, 0zc, enclosing the surface S. Evaluate the surface integral ff, F. ds?
-
Can any shortest-path weight from the new vertex 0 in a constraint graph be positive? Explain.
-
a. The incidence matrix for an undirected graph G D (V, E) is a |V| |E| matrix M such that M e = 1 if edge e is incident on vertex , and M e = 0 otherwise. Argue that a set of columns of M is...
-
Show that ANY-SEGMENTS-INTERSECT works correctly in the presence of vertical segments if we treat the bottom endpoint of a vertical segment as if it were a left endpoint and the top endpoint as if it...
-
Computing unit cost for department and for completed units} with beginning inventory Robert E. Lee Company has two production departments. Blending had 1,000 units in process at the beginning of the...
-
Identifying cost flows in process cost system} List in columnar form the transactions and the accounts debited and credited to reflect the flow of costs through a process cost accounting system for...
-
Departmental cost work sheet analysis; cost of production} summary, three departments, no beginning inventories Goode Manufacturing Co. has three departments and uses the process cost system of...
Study smarter with the SolutionInn App