CSE 326, Spring 1997: Homework 6

Due 5/14/95

1. (20 points) Top down splaying does not need parent pointers as described in the book. In this problem you will give the details of a the top down splaying algorithm. Below is an informal description of recursive top down splaying algorithm. Your job is to describe it in detail using pseudocode. There are other top down splaying algorithms that do not use recursion, but they are more complicated.

   Given a splay tree T and a key x, top down splaying will move x (or if x is not in the tree, the node just before or just after x) to the root two levels at at time except for possibly one time moving one level. To splay T at the key x there are three cases. Case 1: x or the node where x would be inserted is at the root of T. In this case there is nothing to do, just return. Case 2: x or the node where x would be inserted is one level from the root of T. In this case simply rotate that node to the root. Case 3: x or the node where x would be inserted is at least two levels from the root. Now there are four subcases depending on the direction from the root the path to x follows. We consider just one of the four subcases, as the others are similar. Suppose the path to x or where x would be inserted is first right, then left. Replace T.right.left with the result of recursively top down splaying T.right.left at the key x. Now, double rotate to move x to the root (a zig-zag subcase).

   You can assume that you have functions that rotate and double rotate in all directions.

   Show the result of both bottom up and top down splaying at 14 on the following tree.

                               20
                           /        \
                        10           30
                      /    \       /   \
                     5     15    25     35
                   /      /  \           
                  3      13  18          
                        /
                      11
   
   

2. (10 points) Using the K-d tree data structure as described in the notes design an algorithm to output the result of a circular range query. A circular range query is given a point (x,y) and radius r, find all points (u,v) in the K-d tree such that (x-u)^2 + (y-v)^2 < r^2. Note that in our implementation of the K-d tree we do not maintain the current search rectangle. Your pseudocode should be as simple and elegant as possible.