CS251- Winter 2000- Assignment 3

Third assignment--CS251--Winter 2000

Question 1	k-d trees. Given is a k-d tree with the following information in each node: left[u] is the left child of u, right[u] is the right child of u, X[u] is the X-coordinate value of a point, Y[u] is the Y-coordinate value of a point, d[u] is the direction of the cut through (X[u],Y[u]) (horizontal or vertical). The root of the tree T is root[T]. Write a simple recursive algorithm for locating all points u in the tree for which the X-coordinate is in the interval [a,b], and whose Y-coordinate is in the interval [c,d].
Question 2	BST with a cache. To "cache" something in a data structure means to move it to the front or the top so that it easily and quickly accessible. The guiding principle is that elements that are frequently searched for should be easily accessible. Applying this principle to a binary search tree, we may implement the operations insert and search in two phases: first perform an ordinary insert or search, and then move the inserted or searched element to the root, one level at a time, by consecutive rotations. Note that the resulting tree is as if that element were the first inserted element. Write the move-to-root algorithm, assuming that all nodes have left[.], right[.] and parent[.] pointers, as well as key[.] values.
Question 3	Random binary search tree. What is the expected depth of the minimum value node in a random binary search tree?
Question 4	Sorting with repeated values. Assume that we are given n numbers with very many repetitions, such that only k different values occur, where k is much smaller than n. Using comparisons only, show how you can sort them in worst-case time time O(n log k). Hint: use some form of tree search.
Question 5	Random binary search tree. What is the expected size of the subtree (root included) of the 99-th node inserted in a random binary search tree with 2000 nodes?
Question 6	Dual data structures. Assume data are given with two keys, key1 and key2. Describe a data structure that will allow in O(log n) expected time to perform the operations search-by-key1, search-by-key2, insert, delete-by-key1, delete-by-key2.