CS136 Study Guide - 5,6,7,8, Trie, Pseudocode
Document Summary
Tutorial 10 problems: describe (in english, not pseudo-code) an algorithm to do a range-query in a b-tree t of order. Thus, given two integers x , x , the algorithm must output all keys x that satisfy x x x . Each node stores its keys and references to children in sorted arrays of size m. the whole tree fits into internal memory. Your algorithm should have worst-case run time o(log n) + o(# keys in output). Hint: we recommend that you test your algorithm on the b-tree of order 6 below. Each part of this question describes a query operation on s. For each part, describe how to preprocess s and create a data structure that will allow queries of the given form to be answered efficiently. You do not need to give details of the preprocessing algorithm, only the data structure itself and the query algorithm.
