Optimal BST. A binary search tree (BST) is a data structure that contains n inte

Question

Optimal BST. A binary search tree (BST) is a data structure that contains n integers organized in a binary tree with the following properties:

Each node in the tree is associated with an integer (so there are n total nodes).

If a node contains a number y then all nodes in the left subtree, if there are any, must contain some number x such that x < y and all nodes in the right subtree, if there are any, must contain some number z such that y < z.

If a binary search tree has items x1 < x2 < ... < xn, define the cost to lookup an item x to be the number of comparisons made in searching for it in the tree (if the item is in the tree, this is always 1 plus the distance between the item and the root). Thus, the cost for looking up the root is 1. In this question we will only ever do lookups for items in the tree.

Given items x1 < x2 < . . . < xn, there are many BSTs that we can build on these numbers. If we have a sequence of requests, we can calculate the total cost of the requests of the different BSTs, and thus we can define an optimal BST for a request sequence.

(a) Observe that the cost of a sequence of requests does not depend on the order (since the tree is static), but only on the number of times each key is requested. If n = 4 and the request sequence is [2,4,3,6] (which means x1 is accessed twice, x2 is accessed 4 times, and so on), what is an optimal BST for this sequence?

(b) In the general case, if the optimal BST for a given request sequence has xi at the root, prove that the left subtree must be an optimal BST for the requests on x1,...,xi?1 and the right subtree must be an optimal BST for the requests on xi+1, . . . , xn.

(c) Use the above observation to give a general algorithm for constructing an optimal BST for a given sequence x1 < x2 < ... < xn and their counts c1,...,cn (where ci is the number of times xi is accessed). The running time of your algorithm should be O(n3).

Explanation / Answer

Answer-1 : for searching the element in the binary search tree log(n) time complexity will be there beacuse every time it will first compare it with the root element and then it will either go right or left , if the element is less than the root then it will go left otherwise right so the entire left or right subtree will be evaluated this reduces the complexity to half each time hence searching(i-e lookup) will be in log(n) .

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.