《作业问题5解答》由会员分享，可在线阅读，更多相关《作业问题5解答（18页珍藏版）》请在金锄头文库上搜索。
1、Introduction to AlgorithmsNovember 4, 2005 Massachusetts Institute of Technology6.046J/18.410J Professors Erik D. Demaine and Charles E. LeisersonHandout 21 Problem Set 5 Solutions Problem 5-1.Skip Lists and B-trees Intuitively, it is easier to fi nd an element that is nearby an element youve alread
2、y seen. In a dynamic-set data structure, a fi nger search from ? to ? is the following query: given the node in the data structure that stores the element ? , and given another element ? , fi nd the node in the data structure that stores ? . Skip lists support fast fi nger searches in the following
3、sense. (a) Give an algorithm for fi nger searching from ? to ? in a skip list. Your algorithm shouldrun in ? ? ? ? ? rank ? ? rank ? ? timewithhighprobability,where rank ? ? denotes the current rank of element ? in the sorted order of the dynamic set. When we say “with high probability” we mean high
4、 probability with respect to rank ? ? rank ? ? . That is, your algorithm should run in ? ? ? ? time with probability $ $ ) , for any + , $ . Assume that the fi nger-search operation is given the node in the bottommostlist of the skip list that stores the element ? . Solution: For the purposes of thi
5、s problem, we assume that each node ? in the skip list has the following fi elds: key / ? 1 the key associated with node ? next / ? 1 the next element in the linked list containing ? level / ? 1 the level of the linked list containing ? up / ? 1 the element in the linked list of level level / ? 1 $
6、containing the same key as ? down / ? 1 the element in the linked list of level level / ? 1 $ containing the same key as ? We present code for the case where key / ? 1 6 7 . The case where k 6 key / ? 1 is sym- metric. We also assume that level / ? 1 9 , i.e., the search starts at the lowest level o
7、f the skip list. (If the search starts at level ? ? ; , then the fi nger search may take ? ? ? ? ; time.) The algorithm proceeds in two phases. In the fi rst phase, we ascend levels as rapidly as possible, until we fi nd a level that does not allow forward motion. 2Handout 21: Problem Set 5 Solution
8、s FINGER-SEARCH ? ? ? k ? Search for 7 in skip list containing node ? . 1while key / next / ? 1 1 ? k 2do while up / ? 1 ? NIL 3do ? ? up / ? 1 4 ? ? next / ? 1 5while level / ? 1 , 9 6do while key / next / ? 1 1 6 k 7do ? ? next / ? 1 8if level / ? 1 9 9then ? ? down / ? 1 10return ? (Notice that t
9、he search climbs higher than it needs to. A better solution is to examine the next point at each level, and only continue up if the next key is smaller than the target key. As we prove, though, the simpler algorithm above succeeds as well.) We fi rst establish the highest level reached during the fi
10、 nger search. The proof is exactly the same as the proof that a skip list has at most ? ? ? ? ; levels. Lemma 1 While executing FINGER-SEARCH, level / ? 1 6 ? ? ? ? , with high proba- bility, where rank ? key / ? 1 rank ? 7 . Proof.Notice that there are at most $ elements in the skip list in the (cl
11、osed) interval / key / ? 1 ? 7 1 . We calculate the probability that any of these $ elements exceeds height ? ? ? . / any element in M is in more than ? ? ? $ levels 1 6 ? $ $ 6 ? 6 $ ? “ Since none of the elements in the interval are promoted past level ? ? ? , with high probability, and key / ? 1
12、is always in the interval , the result follows.Notice that in the case of this proof, the high probability analysis is with respect to , not ; . We now consider the cost of the two phases of the algorithm: fi rst the cost of ascend- ing, and then the cost of descending. Recall the lemma proved in cl
13、ass: Lemma 2 The number of coin fl ips required to see ? ? heads is ? ? ? ? with high probability. Using this lemma, we can see that the fi rst phase, ascending levels, completes within ? ? ? ? steps as there are only ? ? levels to ascend and each heads results in mov- ing up a level. This lemma als
14、o shows that the second phase completes in ? ? ? ? steps: as in the analysis of a SEARCH, we calculate the cost in reverse, ascending Handout 21: Problem Set 5 Solutions3 from the node containing 7 to the level reached during the fi rst phase; since there are only ? ? levels to ascend, and each head
15、s results in moving up a level, the cost of the second phase is also ? ? ? ? . Hence the total running time is ? ? ? ? ? $ as desired. To support fast fi nger searches in B-trees, we need two ideas: B ? -trees and level linking. Through- out this problem, assume that ? ? ? $ . A B ? -tree is a B-tre
16、e in which all the keys are stored in the leaves, and internal nodes store copies of these keys. More precisely, an internal node ? with 7 $ children “ ? ? ? ? ? ? ? ? ? “ stores 7 keys: the maximum key in “ s subtree, the maximum key in ? s subtree, ., the maximum key in ? s subtree. (b) Describe how to modify the B-tre
