NAMES:

LOGINS:

PRECEPTS:

COS 226 Exercises on Geometric Applications of BSTs


1. Draw the 2d-tree (both the binary tree and the subdivision of the plane) that results when the points (2,1) (5,6) (8,2) (6,3) (4,7) (3,9) and (1,4) are inserted in the order given into an initially empty 2d-tree. Start by subdividing on the x-coordinate of the root, as in the lecture slides.





2.

  1. Draw the interval search tree that results when the intervals (5, 8), (10, 11), (16, 18), (2, 7), (9, 11), (3, 13), and (1, 4) are inserted in the order given into an initially empty interval search tree. Be sure to indicate the auxiliary information associated with each node (maximum endpoint in its subtree).





















  2. List the interval search tree nodes that are examined to determine whether the query interval (12, 17) intersects an interval in the interval search tree? A node is examined if either its interval field or its auxiliary information is accessed.





  3. List the interval search tree nodes that are examined to determine whether the query interval (14, 15) intersects an interval in the interval search tree?