讲解python程序、辅导 tree Tpython留学生

Exercise 2We are again interested in lists of pairs of integers. However, this time, wewant to store these pairs into a rooted tree T. More precisely, each node of Twill store a pair of l. This tree T will have the property that for each inner nodek that stores a pair (a,b), the pair (c,d) stored at a node in the subtree of ksatisfies (a,b)≤(c,d). Furthermore, the pairs stored at sibling nodes must benon-comparable.We will suppose that the root of the tree is a dummy pair (−1,−1).You need to provide a unit test for each question in this exercise where codeis required. Each question is evaluated on the correctness of your code andthe thoroughness of your unit tests.Question 2.1Define a class that stores the tree T for any given list of pairs. The __init__()function must take a list as input and build the tree accordingly. An insert()function must allow the insertion of a pair to an initialised tree. In O(), what isthe running time complexity of the functions you defined?Question 2.2In the class you have defined in Question 2.1, can there be multiple trees thatstore the same list of pairs? (including after insertions?). Prove your answer.(write your answer here).Question 2.3We now relax the constraint that T must be "exactly" a tree. A child nodewhich stores a pair (c,d) must now have as a parent all the nodes that have apair (a,b) such that (a,b)≤(c,d).Design a class (it may be based on the previous one) to allow and build thisrepresentation.Question 2.4 Using the class written in Question 2.3, design and code an algorithm thattraverses all the nodes in that data structure and outputs the stored pairs insorted order (as defined in Question 1.2).Exercise 3You are given a tree T with an integer value (negative or positive) at eachnode. We want to select a subtree of T (with the same root) that maximisesthe sum of the values at its nodes. Note that the answer is trivially T if allnodes have a non-negative value.Question 3.1Define a data structure to store TQuestion 3.2Design and code a dynamic programming algorithm that solves this problem.Question 3.3Write and run unit tests and performance tests.