Question 4. (15 points) Uneven tree updates Given a tree with n nodes, where each node has a key, value, we want to perform the following operations on it: . Increment(k, v): Increase the value at all nodes in the subtree of the node with the key k by v, in O(log n) Find(k): Return the value of associated with the key k, in O(log n) Note 4.1. Note that this is not necessarily a binary tree nor is it a search tree The tree structure is not going to change throughout these procedures Each node has a unique kev associated with it An example of an input tree is: E:4 A 10 D 20 Note 4.2. For either of these operations we first need to locate a node with key k. As this is not a search tree the only way to search is to go through the whole tree. A workaround is to store the locations of the nodes in a dictionary (can be implemented using any data structure, e.g. AVL tree) and go straight to these locations After we locate k, to update the subtree, we need to go to each descendant and update them as well. A workaround for this is to store a carry as we did in the range update for the AVL tree. This makes the update operation O(1) But if we do this, then, together with the carry augmentation, to get the value associated with a key, we would need to travel all the way to the root to add the carry values. This is still O(n) as we are not guaranteed to have a height balanced tree. So these augmentations are not enough to do both operations in O(log n) 1. (5 points) Show how to convert this tree to a list, where each Increment(, -) operation of the tree corresponds to incrementing the values of a contiguous sublist. Question 4. (15 points) Uneven tree updates Given a tree with n nodes, where each node has a key, value, we want to perform the following operations on it: . Increment(k, v): Increase the value at all nodes in the subtree of the node with the key k by v, in O(log n) Find(k): Return the value of associated with the key k, in O(log n) Note 4.1. Note that this is not necessarily a binary tree nor is it a search tree The tree structure is not going to change throughout these procedures Each node has a unique kev associated with it An example of an input tree is: E:4 A 10 D 20 Note 4.2. For either of these operations we first need to locate a node with key k. As this is not a search tree the only way to search is to go through the whole tree. A workaround is to store the locations of the nodes in a dictionary (can be implemented using any data structure, e.g. AVL tree) and go straight to these locations After we locate k, to update the subtree, we need to go to each descendant and update them as well. A workaround for this is to store a carry as we did in the range update for the AVL tree. This makes the update operation O(1) But if we do this, then, together with the carry augmentation, to get the value associated with a key, we would need to travel all the way to the root to add the carry values. This is still O(n) as we are not guaranteed to have a height balanced tree. So these augmentations are not enough to do both operations in O(log n) 1. (5 points) Show how to convert this tree to a list, where each Increment(, -) operation of the tree corresponds to incrementing the values of a contiguous sublist