3. Let A = [a1, a2, · · · an] be an integer array consisting of n integers. (a)
ID: 3889846 • Letter: 3
Question
3. Let A = [a1, a2, · · · an] be an integer array consisting of n integers.
(a) Design an algorithm that constructs a Binary Tree T such that the leaves of T from left to right are a1, a2, · · · , an. I.e, left most leaf of T is a1, second from left is a2, and so on, and the rightmost leaf is an. Derive the asymptotic run time of your algorithm in terms of n.
(b) Design a data structure that supports the following operations in O(log n) time. • increment(i, val): Updates the value of ai to ai + val. • SS(`): Returns Pn i=` ai Describe the data structure, algorithms to perform above operations, and the derive the time bounds
Explanation / Answer
Solution:
a) Algorithm to construct a binary tree T that contains a1 as leftmost and an as rightmost.
Step1: Let the array A= [a1, a2, ... an]. Get the size of the array.
Step2: Find the middle element in the array A.
Step3: Use the middle value as to insert in the binary tree.
Step4: Create a newNode with given value and set its left and right to NULL.
Step5: Check whether the tree is empty or not.
Step6: If tree is empty set newNode as root.
Step7: Otherwise check whether the node contains left or not, if no left node present then insert the newNode to the leftmost otherwise to the rightmost.
Step8: Now go to the Step2 to insert a new node in the binary tree. If all the nodes are inserted in the tree then go to step 9.
Step9: Display the binary tree containing a1 as leftmost and an as rightmost node.
Complexity: The time complexity of the algorithm will be O(nlog n). Here, O(n) is the complexity to insert a node in a binary tree and O(log n) is the complexity to insert the leftmost and rightmost nodes.
b) Algorithm to construct a binary tree T that contains a1 as leftmost and an as rightmost.
increment(i,val):
Step1: Traverse the tree in inorder and update the value of each node.
Step2: Visit the leftmost node a1 of the tree T and update the value as a1 + val.
Step3: Visit the leftmost node a2 of the tree T and update the value as a2 + val.
Step4 Visit the right node a3 of the tree T and update the value as a3 + val.
Step5: Go to step2 until you update rightmost node an.
Step6: Display the updated tree.
SS(l): Returns sum from i=l to n ; a[i]
Step1: Search for the location l. Declare Sum = 0.
Step2: Compare the location l to the root node of the tree. If both are matching then go to step 6.
Step3: If not matching, then check whether the location of the searched element is less than the
node or greater.
Step4: If location l is smaller than the node, search for the location to the left sub-tree otherwise to the right sub-tree.
Step5: Go to step2 until find the location l.
Step6: Start the for loop i from l to n.
Step7: Sum = Sum + a[i].
Step8: Display the sum.
Complexity: The time complexity of the algorithm will be O(log n).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.