figure the plane partitioned by - tree after the insertion of ( ) ( ) ( ) ( ) ( when viewed graphicallyeach node in - tree partitions the plane into regions for instancefigure shows the first five insertions into the - tree in figure the first insertionof splits the plane into left part and right part the second insertionof splits the left part into top part and bottom partand so on for given set of itemsdoes the order of insertion affect the final partitionb if two different insertion sequences result in the same treeis the same partition producedc give formula for the number of regions that result from the partition after insertions show the final partition for the - tree in figure an alternative to the - tree is the quad tree figure shows how plane is partitioned by quad tree initiallywe have region (which is often squarebut need not beeach region may store one point if second point is inserted into regionthen the region is split into four equal-sized quadrants (northeastsoutheastsouthwestand northwestif this places the points in different quadrants (as when is inserted)we are doneotherwisewe continue splitting recursively (as is done when is inserteda for given set of itemsdoes the order of insertion affect the final partitionb show the final partition if the same elements that were in the - tree in figure are inserted into the quad tree tree data structure can store the quad tree we maintain the bounds of the original region the tree root represents the original region each node is either leaf that stores an inserted itemor has exactly four childrenrepresenting four quadrants to perform searchwe begin at the root and repeatedly branch to an appropriate quadrant until leaf (or nullptris reached figure the plane partitioned by quad tree after the insertion of ( ) ( ) ( ) ( ) (