1. [12] Let a1, a2,..., an be a sequence of real numbers, for some n 1....

 

Transcribed Image Text:

1. [12] Let a1, a2,..., an be a sequence of real numbers, for some n 1. A SUM-BOX is an ADT that stores the sequence and supports the following operations (S is a given SUM-BOX): PARTIAL-SUM(S, m): return a, the partial sum from a to am (1mn). CHANGE(S, i, y): change the value of a; to a real number y. Design a data structure that implements SUM-BOX, using an augmented AVL tree. The worst-case runtime of both PARTIAL-SUM and CHANGE must be in O(logn). Describe your design by answering the following questions. (a) What is the key of each node in the AVL tree? What other attributes are stored in each node? (b) Write the pseudo-code of your PARTIAL-SUM operation, and explain why your code works correctly and why its worst-case running time is O(logn). Let S.root denote the root node of the AVL tree. (c) Describe in clear and concise English how your CHANGE operation works, and explain why it runs in O(logn) time while maintaining the attributes stored in the nodes of the AVL tree. 1. [12] Let a1, a2,..., an be a sequence of real numbers, for some n 1. A SUM-BOX is an ADT that stores the sequence and supports the following operations (S is a given SUM-BOX): PARTIAL-SUM(S, m): return a, the partial sum from a to am (1mn). CHANGE(S, i, y): change the value of a; to a real number y. Design a data structure that implements SUM-BOX, using an augmented AVL tree. The worst-case runtime of both PARTIAL-SUM and CHANGE must be in O(logn). Describe your design by answering the following questions. (a) What is the key of each node in the AVL tree? What other attributes are stored in each node? (b) Write the pseudo-code of your PARTIAL-SUM operation, and explain why your code works correctly and why its worst-case running time is O(logn). Let S.root denote the root node of the AVL tree. (c) Describe in clear and concise English how your CHANGE operation works, and explain why it runs in O(logn) time while maintaining the attributes stored in the nodes of the AVL tree.

Answer rating: 100% (QA)

a The key of each node in the AVL tree will be the index of the element in the sequence Each node wi... View the full answer