An alternative to the 2-d tree is the quad tree. Figure 12.52 shows how a plane

Chapter 12, Problem 12.33

(choose chapter or problem)

An alternative to the 2-d tree is the quad tree. Figure 12.52 shows how a plane ispartitioned by a quad tree. Initially we have a region (which is often a square, butneed not be). Each region may store one point. If a second point is inserted into aregion, then the region is split into four equal-sized quadrants (northeast, southeast,southwest, and northwest). If this places the points in different quadrants (aswhen p2 is inserted), we are done; otherwise, we continue splitting recursively (asis done when p5 is inserted).a. For a given set of N items, does the order of insertion affect the final partition?b. Show the final partition if the same elements that were in the 2-d tree inFigure 12.39 are inserted into the quad tree.