CSE 326, Spring 1995: Homework 7

Due 5/17/95

1. (20 points) Assume we have N points P in the plane organized in a quad tree. Assume the root of the tree represents the quadrant [0,1]x[0,1]. The nodes of the quad tree have the fields leaf: boolean, data.x, data.y, origin.x, origin.y, size: real, Q[0..3]: array of pointers to nodes. In this problem assume that reals are fully represented and there are no floating point errors.
   • Design a function "intersect" which takes arguments a,b,d,x,y,r and retruns true if the square with left-bottom corner (a,b) and side d intersects the circle with center (x,y) and radius r. The square and circle include their boundaries and interior.
   • Use the insersect function above to design a procedure which given a point (x,y) (not necessarily in P) and radius r prints out all the points in P within distance r of (x,y). Your procedure should only visit quadrants where there is some possiblity that there is a point in P within distance r of (x,y).
   • Suppose that the minimum distance between any two points in P is m. As a function of N, m and r give a good upper bound on the number of points output by your procedure. As a function of m, what is an upper bound on the height of the quad tree? What is the overall time complexity of your procedure as a function of the number of points output and m.
2. (10 points) Consider B-trees of order 3 which is also known as a 2-3 tree. In this case each internal node has 2 or 3 children and each leaf has either one or two keys.
   • Show the result of inserting 1,2,3,4,5,6,7,8,9,10,11,12 into an initially empty 2-3 tree. Show the tree after each insertion.
   • Consider the following 2-3 tree

                                   5                       
                              /         \
                         3                     7
                      /     \               /     \
                    2         4           6         8
                   / \       / \         / \       / \
                  1   2     3   4       5   6     7   8
                             
     

     Show the result of deleting 1,2,3,4,5,6,7. Show the tree after each deletion.