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.
  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.