if it is possible, please send the text solution instead of handwriting. if hand
ID: 3863684 • Letter: I
Question
if it is possible, please send the text solution instead of handwriting. if handwriting, please make it clear as possible as you can.
Problem 5 (3 points). (Textbook Exercise 5.6) Consider an n-node complete binary tree T, where n 2d 1 for some d. Each node v of T is labeled with a real number ru. You may assume that the real numbers labeling the nodes are all distinct. A node v of T is a local minimum if the label r is less than the label cu, for all nodes w that are joined to v by an edge. You are given such a complete binary tree T, but the labeling is only specified in the following implicit way: for each node v, you can determine the value ru by probing the node v. Show how to find a local minimum of T using only O(log n) probes to the nodes of T.Explanation / Answer
Since all the labels of the tree are distinct real numbers and the tree is a finite one, we are guranteed that there exists a smallest element in this tree. In a complete binary tree, every node has atmost three neighbours, one parent and two sibilings. In case of a root node, the parent doesn't exists and in case of leaf nodes children doesn't exists, but that is not of any concern to us. So, in order to know that if a given node is minimum, we have to compare it with it's parent and two child nodes. In case of root node, we have to just compare it with it's children. Use the below algorithm to find the local minimum.
1. set root node as current node
2. compare the label of current node to the label of it's children
3. If the current node is smaller, then return it as local minimum
4. Otherwise, pick the smallest of the children nodes and repeat from step-2
Here we are picking smallest of the children to optimize the performance in step-2. There you don't have to compare again with the parent node as this is already assured to be smaller one. However you can pick any node and check with three neighbouring (parent + 2 children) nodes every time, but that costs a bit more. Now, coming to the time complexity, it's going to be O(logn) because we are going from top of the tree to the bottom only once, which is nothing but the depth of the complete binary tree (<logn+1). For every iteration, we are reducing the search space to half of it's current [i.e., we are picking one child and recursively searching in it]. This works, because that subtree is guranteed to have a smallest element in it as all the numbers are distinct and real.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.