A tree data structure can store the quad tree. We maintain the bounds of the original regi...

A 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 a leaf that stores an inserted item, or has exactly four children, representing four quadrants. To perform a search, we begin at the root and repeatedly branch to an appropriate quadrant until a leaf (or nullptr) is reached.

a. Draw the quad tree that corresponds to Figure 1.

---

b. What factors influence how deep the (quad) tree will be?

---

c. Describe an algorithm that performs an orthogonal range query in a quad tree.

Figure 1: The plane partitioned by a quad tree after the insertion of p1 = (53, 14), p2 = (27, 28), p3 = (30, 11), p4 = (67, 51), p5 = (70, 3)