Question: Consider a binary search tree where each tree node v has a field v.sum which stores the sum of all the keys in the subtree

Consider a binary search tree where each tree node v has a field v.sum which stores the sum of all the keys in the subtree rooted at v.

(a) Modify the Insert operation (given below) to insert an element so that all the .sum fields of the tree are correct after applying the Insert operation. (Assume that all the .sum fields were correct before the Insert operation.) Your modified algorithm should take the same time as the original Insert operation. Explain your modification and give pseudo-code for the modified algorithm.

function Insert(T,z)

y <-- LocateParent(T,z)

z.parent <-- y

if (y = NIL) then T.root <-- z ;

else if (z.key< y.key) then y.left <-- z

else y.right <-- z

(b) Argue for the correctness of your algorithm. Explain why all the .sum fields are correct after running your modified Insert operation.

(c) Analyze the running time of your modified algorithm in terms of the size n and the height h of the binary search tree.

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

Consider a binary search tree where each tree node v has a field v.sum which stores the sum of all the keys in the subtree rooted at v. (a) Modify the RightRotate operation(given below) to properly...

Consider a binary search tree where each tree node v has a field v.sum which stores the sum of all the keys in the subtree rooted at v. We wish to add an operation SumLE(K) to this binary search tree...

Consider a binary search tree where each tree node v has a field v . size which stores the size of the binary search tree rooted at v ( size is the number of nodes in the subtree ) .

2. Finding all vs. counting all. Assume that an ordered dictionary is implemented using a binary search tree and, for each node v in the tree, the field 1. size equal to the num ber of items in the...

Problem 2. (10 points) Suppose you have an augmented binary search tree where at each internal node v, we also store the number of keys of the subtree rooted at v. Complete the following recursive...

Please explain the process and use the BST functions given, thank you. Problem 2. (10 points) Suppose you have an augmented binary search tree where at each internal node v, we also store the number...

Consider a binary search tree that stores a list of values. In addition to a value from the list, each tree node also stores an integer value called subtreeCount that is the number of nodes in the...

Problem 4: Consider a binary search tree augmented with the following information. At each node x we also store m(x): the number of nodes in the subtree rooted at x (including x). Show how to use the...

Barbara Trading Company has used the LIFO method of inventory accounting since its inception in 1990. At December 31, 2006, the ending inventory was: Base layer 10,000 units @ $ 7 $ 70,000 2000 layer...

What public policies are furthered by this law? To what extent are there conflicts among the policies served and how will they affect the way the law in this area is interpreted, applied, and changed?

Most businesses use the petty cash fund to pay for Multiple Choice office lunches. internal expenses. accounts payable. small expenditures.

Compared with half a century ago, adoption has become _ _ _ _ _ _ _ _ _ common, but it is more open and acceptabl e , so we probably discuss it _ _ _ _ _ _ _ . fill in the blanks more or much less or...

How are Work Breakdown Statements Built and how do they appear in a Project Plan?

What is the most important part of any HCM Project Map and why?

What is the Phase that begins after Project rollover and what activities are part of the Phase?