GO程序留学生写作、辅导go编程语言、写作go程序设计

” GO程序留学生写作、辅导go编程语言、写作go程序设计Lab4: 2D-TreeIn this assignment, you will implement a special data structure called a 2D-Tree (short for 2-dimensionaltree) that efficiently supports to search what value in the container is X most similar to?.1. StoryAt a high level, a kd-tree(short for k-dimensional tree) is a generalization of a binary search tree thatstores points in k-dimensional space. That is, you could use a kd-tree to store a collection of points in theCartesian plane, in three-dimensional space, etc. You could also use a kd-tree to store biometric data, forexample, by representing the data as an ordered tuple, perhaps (height, weight, blood pressure,cholesterol). However, a kd-tree cannot be used to store collections of other data types, such as strings.Also note that while its possible to build a kd-tree to hold data of any dimension, all of the data stored ina kd-tree must Have the same dimension. That is, you cant store points in two-dimensional space in thesame kd-tree as points in four-dimensional space.Its easiest to understand how a kd-tree works by seeing an example. Below is a kd-tree that stores pointsin three-dimensional space:Notice that in each level of the kd-tree, a certain component of each node has been bolded. If we zeroindexthe components (i.e. the first component is component zero, the second component is componentone, etc.), in level n of the tree, the (n % 3)-th component of each node is shown in bold. The reason thatthese values are bolded is because each node acts like a binary search tree node that discriminates onlyalong the bolded component. For example, the first component of every node in the left subtree is lessthan the first component of the root of the tree, while the first component of every node in the right subtreehas a first component At least as a large as the root nodes. Similarly, consider the kd-trees left subtree.The root of this tree has the value (2, 3, 7), with the three in bold. If you look at all the nodes in its leftsubtree, youll notice That the second component has a value strictly less than three. Similarly, in the rightsubtree the second component of each node is at least three. This trend continues throughout the tree.Given how kd-trees store their data, we can efficiently query whether a given point is stored in a kd-treeas follows. Given a point P, start at the root of the tree. If the root node is P, return the root node. If thefirst component of P is strictly less than the first component of the root node, then look for P in the leftsubtree, this time Comparing the second component of P. Otherwise, then the first component of P is atleast as large as the first component of the root node, and we descend into the right subtree and next timecompare the Second component of P. We continue this process, cycling through which component isconsidered at each step, until we fall off the tree or find the node in question. Inserting into a kd-tree issimilarly analogous to inserting into a regular BST, except that each level only considers one part of thepoint.GO作业留学生写作、辅导go作业语言2. Lab RequirementYou should implement the TreeNode and BinaryDimonTree(2D-Tree) classes.TreeNode is a class which is used to store the binary dimension data. You should provide the followingfunctions (at least):1. int getX(): return x(the first value in the tree node);2. int getY(): return y(the second value in the tree node);BinaryDimonTree is a Class for the Tree which supports the following functions (at least):1. BinaryDimonTree(): the construct function of class BDT;2. istream operator(istream in, BinaryDimonTree tree): input a 2D-Tree and the rule isgiven below;3. TreeNode* find_nearest_node(int x, int y): search the 2D-Tree and find the point whosedistance is smallest to the Point(x, y), and output the result to the console;p.s. the distance between Point(x1, y1) and Point(x2, y2) is equal to [(x1-x2)^2 + (y1-y2)^2]^(1/2);p.s. If there are two Points that have the same distance to the Point(x, y), then you are supposedto choose the point whose x is smaller. If their xs are also the same, then choose the pointwhose y is smaller;4. ~BinaryDimonTree(): the deconstruct function which is used to reclaim all the data in the 2DTree,and you should explain your implementation to us when your lab is examined.You must implement the Tree completely by yourself. And the names of the classes and their functionsmust be same with the above.We have provided the main function and the test cases, you should just run the main.cpp and check if youcan pass through All the test cases.3. GuidanceThe algorithm to find the nearest node in the 2D-Tree:Let the test point be (a0, a1).Maintain a global best estimate of the nearest neighbor, called guess.Maintain a global value of the distance to that neighbor, called bestDistSet guess to NULL.Set bestDist to infinity.Starting at the Root, execute the following procedure:if curr == NULLreturn/** If the current location is better than the best known location,* update the best known location.*/if distance(curr, Guess) bestDistbestDist = distance(Curr, guess)guess = curr/** Recursively search the half of the tree that contains the test point.* i means the dimension index which is used to discriminate in the currentlevel,* for example: the i = 0 when curr is the root*/if ai currirecursively Search the left subtree on the next axiselserecursively search the right subtree on the next axis/** If the vertical distance between the points is smaller than the bestdistance,* look on the other side of the plane by examining the other subtree.*/if |curri ai| bestDistrecursively search the other subtree on the next axis4. TestInput Output Format:The test file is divided into two parts.The first part is For constructing a 2D-tree.The first line contains an integer M which represents the number of nodes in the tree.Next, there are M lines following, each contains two integers divided by a space. The two integers at thesame line represent the values on two Dimensions respectively for the corresponding node.The second part contains the test cases for find_nearest_node method.The first line contains an integer N which represents the number of test cases.Next, there are M lines following, each contains four integers divided by spaces. In each line, the first twointegers represent the node to search and the other two integers are correct answer of the search.The code for the second part has been already completed in main.cpp. Please refer to the rules andconstruct your Own 2D-tree.Coding format：1. Please add your own functions and variables in file Tree.h and do not change or delete thosefunctions with tag /* DO NOT CHANGE */. Do not include other headers or libraries.2. Please write your code in Tree.cpp and do not include other headers or libraries.3. Do not modify main.cppSubmission：1. Please compress your source Code into a 7z file and rename it to lab4.7z.2. Only Tree.h and Tree.cpp are supposed to be submitted.3. Upload it to canvasHint：1. 1000 = M = 5000, 30000 = N = 100000。2. In real-world cases, search time is more important, so you are supposed to reduce the executiontime of find_nearest_node.5. ExampleTestcase 1:In this case, M=7 and N=1. You can construct a 2D tree with 7 nodes like this:We have only one testcase, that is to find the point whose distance is smallest to Point(3,6).As both Point(3,5) and Point(3,7) have the same distance to Point(3,6), we choosePoint(3,5) as it has smaller y.如有需要，请加QQ：99515681 或邮箱：99515681@qq.com

“