1. Give algorithms for implementing the following operations on a binary search
ID: 3862245 • Letter: 1
Question
1. Give algorithms for implementing the following operations on a binary search tree:
(a) Average-Keys: Given a node x, returns the average value of the keys in the subtree rooted at x. (Hint: Separately compute the number of nodes and the sum of the keys). For full credit your procedure should run in O(n) time.
(b) Range-Search: Given an interval [a,b] and a tree T, returns a list of all the nodes with keys in the range a, b.
There is an easy (n) solution, but for credit your algorithm should run in time O(k+h) where k is the number of nodes in the range and h is the height of the search tree. Analyze the running time of your algorithm carefully. Remember that some of the homework grade is for the clarity of your explanation.
Explanation / Answer
a) run inorder traversal from given node, pass two variable by reference to add value of node at each step and a counter for nodes added so far.
At the end of inorder traversal we have sum of nodes and number of nodes. Return sum/(number of nodes).
This will run in (n) as inorder traversal take (n) time.
(b) Range-Search: Given an interval [a,b] and a tree T, returns a list of all the nodes with keys in the range a, b.
Traverse the given binary search tree starting from root.
For every node being visited, check if this node lies in range, if yes, then add that node to result list and recur for both of its children. If current node is smaller than low value of range, then recur for right child, else recur for left child.
This will run in O(h + k) where h is height of tree and k is number of nodes
Analysis of complexity
If no node has a value that lie in given range, we will recur on left or right child but not both. So algorithm will reach the bottom of the tree exactly by traversing through each child , so o(h).
Now lets assume that there are some nodes that fall in the given range , and for those nodes , you will have to additionally recur on both the children instead of just one as in previous case , so for every node that lies in the given range you are recurring on one extra node , so additional k recurs which makes the total time complexity o(h + k)
If that extra child that we are recurring on might in addition cause more nodes to traverse .
Case 1: Lets assume the extra child falls in the range , then this child calls both of its children , so for every node that lies in the given range , or for every extra child we recur , we must go down till the base , that is for every additional child that we are calling the function , i.e for every node that lies in the range , we are traversing additional o(h) nodes twice , for each of its child, so now if k nodes lie in the given range , the in the worst case scenario , we might end up traversing many more nodes , so in the worst case since each of the two children can produce n other nodes (worst-case) so this model is as bad as (worst case again) producing the same result on a tree that has no element in the given range but has the number of nodes = n * 2^k . We have just replicated the model on a large scale.
now the time complexity is o(h) for this model.
o(log(n*2^k)) ~ o(log(n) + log(2^k)) ~ o(h + k)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.