利用者:Atirow/スキップリスト

説明

Let us prove these two claims. First, to prove that the search time is guaranteed to be logarithmic. Suppose we search for and find node n where n is the position of the found node among the nodes of level 1 or higher. If n is even, then there is a 50/50 chance that it is higher than level 1. This time, though, if it is not higher than level 1 then node n-1 is guaranteed to be higher than level 1. If n is odd, then there is a 50/50 chance that it is higher than level 1. Given that it is not, there is a 50/50 chance that node n-1 is higher than level 1. Given that this is not either, we are guaranteed that node n-2 is higher than level 1. We repeat the analysis for nodes of level 2 or higher, level 3 or higher, etc. always keeping in mind that n is the position of the node among the ones of level k or higher for integer k. So the search time if constant in the best case (if the found node is the highest possible level) and 2 times the worst case for the search time for the totally derandomized skip-list (because we have to keep moving left twice rather than keep moving left once).

Next, let's prove something about the probability of an adversarial user's guess of a node being level k or higher being correct. First, the adversarial user has a 50/50 chance of correctly guessing that a particular node is level 2 or higher. If he/she knows the positions of two consecutive nodes of level 2 or higher, and knows that the one on the left is in an odd numbered position among the nodes of level 2 or higher, he/she has a 50/50 chance of correctly guessing which one is of level 3 or higher. So, his/her probibility of being correct, when guessing that a node is level 3 or higher, is 1/4. Inductively continuing this analysis, we see that his/her probability of guessing that a particular node is level k or higher is 1/(2^(k-1)).