CSC 3102 Chapter : 3102 Hw2
Document Summary
Due october 7, 2014 (in class: (20 points) your friend, john (whoever he is! ), gives you an array b[1n] of numbers. He wants to obtain the smallest k numbers in b, in sorted order. One way to solve this is: sort b and the output the k smallest numbers. Show that height of such an avl tree having n nodes is. O(log n): (10+10+20 = 40 points) range queries. Given an avl tree show (using pseudocode) how to support the following queries: Rangecount(k1, k2): count the number of keys in the avl tree which are between k1 and k2 in o(log n) time (hint: recall the size eld). Rangereport(k1, k2): list all the keys in avl tree which are in between k1 and k2 in. Rangemin(k1, k2): consider the eld data stored in each node to be an integer. Find the key with minimum data values among all the keys which are between k1 and k2 in.
