Be sure to specify what information is stored at each node. Just give high-level sketches the algorithms, emphasizing the similarity and differences with algorithms for ordinary 2-3 trees. You don't have to give detailed pseudocode. List maintenance (II). Extending the previous exercise, suppose we also want to an operation that reverses a given list L. Show how this operation can be implemented in constant time, while the other operations can still be performed within the time bounds of the previous exercise. Hint: this should be a modification to your solution to the previous exercise, making use of the "lazy evaluation" trick that was used in AddRange example from class. However, for this problem, you should have each internal node store a "reverse bit", which means that the list represented by the subtree rooted at each node is to be treated as the logical reverse of the list it would ordinarily represent. To reverse a list, all you have to do is flip the "reverse bit of the root. However, all of the other operations become a bit more complicated. For example, after a sequence of concatenation, split, and reverse operations, you can easily end up with a tree with many internal nodes "reverse bits set to 1. For example, consider the following tree, where the black nodes have their "reverse bits" set to 1: The subtree rooted at c represents the list (7,63), which is the reverse of (63, 7). The subtree rooted at d represents the list (8,6,7,63). The subtree rooted at a represents the list (21, 69), which is the reverse of (69, 21). The subtree rooted at b represents (69, 21, 10,5), which is the reverse of (5,10, 21, 69). The entire tree represents the list (69, 21, 10,5, 8, 6, 7, 63). A useful subroutine you should design is the following: given a tree T representing a list L of length n and an index k = 1,..., n, trace a path from the root to the leaf v in T representing kth element in L, so that the path from the root to the leaf gets cleared of any "reverse bits", and moreover, T gets restructured so that all the leaves that are to the left of v in T represent elements whose position in L is in {1,...,k - 1}, and all the leaves that are to the right of v in T represent elements whose position in L is in {k +1,...,n}. Be sure to specify what information is stored at each node. Just give high-level sketches the algorithms, emphasizing the similarity and differences with algorithms for ordinary 2-3 trees. You don't have to give detailed pseudocode. List maintenance (II). Extending the previous exercise, suppose we also want to an operation that reverses a given list L. Show how this operation can be implemented in constant time, while the other operations can still be performed within the time bounds of the previous exercise. Hint: this should be a modification to your solution to the previous exercise, making use of the "lazy evaluation" trick that was used in AddRange example from class. However, for this problem, you should have each internal node store a "reverse bit", which means that the list represented by the subtree rooted at each node is to be treated as the logical reverse of the list it would ordinarily represent. To reverse a list, all you have to do is flip the "reverse bit of the root. However, all of the other operations become a bit more complicated. For example, after a sequence of concatenation, split, and reverse operations, you can easily end up with a tree with many internal nodes "reverse bits set to 1. For example, consider the following tree, where the black nodes have their "reverse bits" set to 1: The subtree rooted at c represents the list (7,63), which is the reverse of (63, 7). The subtree rooted at d represents the list (8,6,7,63). The subtree rooted at a represents the list (21, 69), which is the reverse of (69, 21). The subtree rooted at b represents (69, 21, 10,5), which is the reverse of (5,10, 21, 69). The entire tree represents the list (69, 21, 10,5, 8, 6, 7, 63). A useful subroutine you should design is the following: given a tree T representing a list L of length n and an index k = 1,..., n, trace a path from the root to the leaf v in T representing kth element in L, so that the path from the root to the leaf gets cleared of any "reverse bits", and moreover, T gets restructured so that all the leaves that are to the left of v in T represent elements whose position in L is in {1,...,k - 1}, and all the leaves that are to the right of v in T represent elements whose position in L is in {k +1,...,n}