Computers and Technology, 10.03.2020 01:33 ctyrector

Procedure TreeSearch (x, K) i if (x = NIL) or (K = x. key) then 2 return (x); 3 else if (K < x. key) then 4 | TreeSearch (x. left, K); 5 else 6 TreeSearch (x. right, K); 7 endConsider 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 which returns the sum of all the keys in the tree whose values are less than or equal to K.

(a) Describe an algorithm, SumLE(K), which returns the sum of all the keys in the tree whose values are less than or equal to K. Give pseudo-code for your algorithm. Your algorithm should take the same time as operation TreeSearch from slide 7.12.

(b) Explain why your algorithm is correct, i. e., why it returns the sum of all the keys whose values are less than or equal to K.

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

Answers: 3

Show answers

Other questions on the subject: Computers and Technology

Computers and Technology, 22.06.2019 10:30, ilovepickles930

What can tanya do now to start preparing for the college and scholarship application process? think about her grades, activities in which she can get involved, possible part-time jobs at which she can work, and standardized tests she can take. (10 points) apex

Answers: 2

continue

Computers and Technology, 23.06.2019 03:10, kyleereeves2007

Acomputer has a two-level cache. suppose that 60% of the memory references hit on the first level cache, 35% hit on the second level, and 5% miss. the access times are 5 nsec, 15 nsec, and 60 nsec, respectively, where the times for the level 2 cache and memory start counting at the moment it is known that they are needed (e. g., a level 2 cache access does not even start until the level 1 cache miss occurs). what is the average access time?

Answers: 1

continue

Computers and Technology, 23.06.2019 04:00, china236

In a word processing program, such as microsoft word, which feature to you choose the desired picture enhancement?

Answers: 2

continue

Computers and Technology, 23.06.2019 07:00, schvox

1. you have a small business that is divided into 3 departments: accounting, sales, and administration. these departments have the following number of devices (computers, printers, etc.): accounting-31, sales-28, and administration-13. using a class c private network, subnet the network so that each department will have their own subnet. you must show/explain how you arrived at your conclusion and also show the following: all available device addresses for each department, the broadcast address for each department, and the network address for each department. also, determine how many "wasted" (not usable) addresses resulted from your subnetting (enumerate them).

Answers: 3

continue

You know the right answer?

Procedure TreeSearch (x, K) i if (x = NIL) or (K = x. key) then 2 return (x); 3 else if (K < x. k...