[Solved] CS 300- Homework 1-complex version of binary search trees.

CS 300Data StructuresHomework 1

In this assignment, you will implement a slightly more complex version of binary searchtrees. Remember that binary search trees typically work on one dimensional key spaces.The trees that you will work on in this homework let us search on two-dimensional spaces,and extensions to higher dimensional spaces should be obvious. These kind of treesare very useful in many graphics applications and in computer aided design tools forautomated design of VLSI (very large scale integration) circuits. Instead of each nodehaving at most 2 children, in such trees, nodes have at most 4 children. For reasons thatwill be clear in a moment, we will call these children as TopLeft, TopRight, BottomLeftand BottomRight. Before we go on any further, let us briefly discuss how you will usethese trees.You are given a (possibly very large) database of rectangles. You will represent each ofthese rectangles by objects which look like1class Rectangle {public:.private:int Top; // y coordinate of the upper edgeint Left; // x coordinate of the left edgeint Bottom; // y coordinate of the bottom edgeint Right; // x coordinate of the right edge.};

Figure 1: How a two-dimensional tree stores rectangles2Contrary to what you are used to in Cartesian geometry, the coordinate system in thisrepresentation is such that, as you go towards right and bottom, the x and y coordinates(respectively) increase, that is, for a rectangle, Bottom > Top and Right > Left. A listof such rectangles can be trivially represented using the LinkedList class you studiedearlier.1A point (x, y), on the Cartesian plane is considered to be inside a rectangle object R (orintersects R), if R.Left  x < R.Right and R.Top  y < R.Bottom, that is, the points onthe right and bottom boundaries of the rectangle are not considered to be in the rectangle.Given such a point, our tree data structure will enable us to find (hopefully in a veryfast way) all rectangles that contain that point. One can obviously do this by keeping allrectangles in a linked list and searching through the list by checking if the point is insidea rectangle or not, but when you have 1,000,000 or 50,000,000 rectangles2, that will notbe very efficient.The trees that you will design organize two-dimensional information in the following way: You will assume that each such tree covers a portion of the Cartesian plane andthat this portion is fixed. You will thus assume that the region covered by the treeis represented by some suitable (large) rectangle. Call this rectangle Extent. The center of the tree rectangle is located at the center point whose x coordinate is (Extent.Left + Extent.Right)/2and whose y coordinate is (Extent.Top + Extent.Bottom)/2where the / is interpreted as the integer division operator in C++. Note that, this center defines four additional smaller rectangles (called quadrants)at the top left, top right, bottom left and bottom right of the center point. So, ifyou are given a point (x, y) you only need to find which quadrant the point falls, andthen just search the rectangles that you know (may) overlap with that quadrant, notall rectangles. Note also that this can be extended recursively to smaller quadrantswithin a quadrant until a minimum rectangle size is reached. See Figure 1 for someof the details of how a two-dimensional tree stores rectangles.The class definition for a node of such a two-dimensional tree (the equivalent of theBinaryTreeNode class) will look like the following:1The source code for the linked list and related objects are available from the course web page.2For instance, when you are doing a VLSI circuit design3class TwoDimTreeNode {public:.private:Rectangle Extent;LinkedList<Rectangle> Vertical, Horizontal;TwoDimTreeNode *TopLeft, *TopRight,*BottomLeft, *BottomRight;};The two dimensional tree class will just contain a single private entry that points toa root node of the class TwoDimTreeNode just like the binary search tree definition wediscussed in the class. The rectangle Extent defines the region covered by the tree.Vertical and Horizontal are two linked lists of rectangles. Vertical keeps the listof rectangles which intersect the vertical line x = (Extent.Left + Extent.Right)/2and Horizontal keeps the list of rectangles which intersect the horizontal line y =(Extent.Top + Extent.Bottom)/2. If a rectangle intersects both lines, then it is put ononly one of these lists and not two. So in Figure 1, rectangles 1,2 and 3 would be onthe Vertical list for the root extent rectangle and rectangles 4 and 5 would be on theHorizontal list for the root extent rectangle.If a rectangle does not intersect any of these lines then, it is either in the tree pointed byTopLeft which covers the rectangular extent with3Top = Extent.TopLeft = Extent.LeftBottom = (Extent.Top + Extent.Bottom)/2Right = (Extent.Left + Extent.Right)/2or in one of the other 3 regions (pointed to by TopRight, BottomLeft, BottomRight)whose extents can be defined similarly. Thus, it is recursively inserted to the subtree ofthe relevant quadrant unless the width or the length of the extent is 1 so that it can not besubdivided any further. The important point to note is that a given rectangle is insertedto either the Horizontal or the Vertical lists associated with the subtree whose centerlines it intersects. Note also that the extents of the children subtrees do not intersect eitherof the center lines. An example can be of help here. Suppose the tree covers the extentTop = 0, Left = 0, Bottom = 4 and Right = 5.Then, the TopLeft quadrant of this extent is defined by Top = 0, Left = 0, Bottom = 2and Right = 2.3Again remember that the right and bottom boundaries are not part of the rectangles.4 the TopRight quadrant of this extent is defined by Top = 0, Left = 3, Bottom =2 and Right = 5. the BottomLeft quadrant of this extent is defined by Top = 3, Left = 0, Bottom= 4 and Right = 2. and the BottomRight quadrant of this extent is defined byTop = 3, Left = 3, Bottom = 4 and Right = 5.Also note that areas of the quadrants need not be equal but they are close.To search for the rectangles that a point (x, y) intersects with, you first checks if the pointfalls in any of rectangles on the Vertical and Horizontal lists of the root node. If so,these rectangles are output (or inserted to a result list of rectangles) and search continuesrecursively with the subtree covering the quadrant the point falls into. (No additionalsearch is needed if the point falls on the center lines of the tree.) For instance looking atFigure 1, for the given (x, y) point one would search the Vertical and Horizontal listsof the main root rectange and then only the subtree corresponding to the bottomrightquadrant. None of the other 3 quadrants need to be searched.2 WORK TO BE DONEAs a part of this homework, you should implement the necessary classes (some of whichwere sketched out above). Obviously you can reuse any other classes available (such asthe LinkedList class).You should then write a simple application program that uses these classes.1. In order to simplify certain matters, you will assume that the data for the rectangledatabase will be in a file called rectdb.txt. So, your program reads from a filecalled rectdb.txt four integers (in the order Top, Left, Bottom, Right) that definethe extent rectangle for the top main tree (you can assume that all the coordinatesof all the rectangles are nonnegative integers, and no rectangle has any portion thatfalls outside the extent of the whole tree).2. It then reads again from the same file, the Top value for a rectangle, if this valueis 1 (or any negative number) then the input of rectangles is over. The programproceeds to step 3. Otherwise the Left, Bottom, Right values are read and insertedthe rectangle to the right place in your two-dimensional tree. You then repeat thisstep.3. Your program then reads from the standard input, query points given as pairs ofintegers (in the order x, y) and then prints out to standard out, for each querypoint,5(a) the query point itself,(b) the number of rectangles found and then(c) the coordinates of the intersecting rectangles (with the order top, left, bottom,right) one rectangle on a line.4. If the program reads a query point with x = -1 the program exits.For example, a typical database file recdb.txt will be like:40 0 1000 1000 (extent rectangle of the whole tree)0 0 100 100 (first rectangle)650 700 750 800 (second rectangle) .. -1 (end of rectangles)The query data that will come from the standard input will look like:3 4 (first query point)700 800 (second query point)-1 70 (last query point)The output would be like3 4 (the query point)2 (assume there are two rectangles)0 0 100 100 (the first intersecting rectangle)2 1 10 12 (the second intersecting rectangle)700 800 (the query point)0 (so this point intersects with no rectangles)….4The text in the parentheses are provided as explanations they are not part of the file nor part ofthe input or output.