2. This problem is concerned with range queries (a topic discussed in class) on a normal...

Transcribed Image Text:

2. This problem is concerned with range queries (a topic discussed in class) on a normal binary search tree T whose keys are real numbers. The range queries are generalizations of the normal search(key) operation. The range of a range query on T is an interval specified by a pair [a, ar] of query input, where x and z, are real numbers and a ≤ r. Note that the input numbers ay and z, that define a query range need not be keys stored in the tree T. You are asked to design a binary search tree T that supports the normal search, insert, and delete operations, each in O(h) time, where h is the height of T. In addition, your binary search tree T must also support the following two range queries, each in O(h) time. (a) range-count(a, a,): Given any range [, ,] for a range query on T, report the number of keys of T in the range of [, 2]. (15 points) (b) range-sum(x, x): Given any range [a, r] for a range query on T, report the sum of keys of T in the range of (a, a,). (15 points) Note: You are asked to present the design of your data structure and the two operations in (a) and (b). 2. This problem is concerned with range queries (a topic discussed in class) on a normal binary search tree T whose keys are real numbers. The range queries are generalizations of the normal search(key) operation. The range of a range query on T is an interval specified by a pair [a, ar] of query input, where x and z, are real numbers and a ≤ r. Note that the input numbers ay and z, that define a query range need not be keys stored in the tree T. You are asked to design a binary search tree T that supports the normal search, insert, and delete operations, each in O(h) time, where h is the height of T. In addition, your binary search tree T must also support the following two range queries, each in O(h) time. (a) range-count(a, a,): Given any range [, ,] for a range query on T, report the number of keys of T in the range of [, 2]. (15 points) (b) range-sum(x, x): Given any range [a, r] for a range query on T, report the sum of keys of T in the range of (a, a,). (15 points) Note: You are asked to present the design of your data structure and the two operations in (a) and (b).

Answer rating: 100% (QA)

To support the operations described efficiently we can augment the traditional binary search tree BST with additional information at each node Well us... View the full answer