algorithm design techniques along with this typedef that yields the random-number generator (the "minimal standard"described earliertypedef linear congruential engine minstd rand the library also provides generator based on newer algorithmknown as the mersenne twisterwhose description is beyond the scope of the bookalong with typedef mt that uses its most common parametersand third type of random-number generatorknown as "subtract-with-carrygenerator figure illustrates how random-number generator engine can be combined with distribution (which is function objectto provide an easy-to-use class for the generation of random numbers skip lists our first use of randomization is data structure that supports both searching and insertion in (log nexpected time as mentioned in the introduction to this sectionthis means that the running time for each operation on any input sequence has expected value (log )where the expectation is based on the random-number generator it is possible to add deletion and all the operations that involve ordering and obtain expected time bounds that match the average time bounds of binary search trees the simplest possible data structure to support searching is the linked list figure shows simple linked list the time to perform search is proportional to the number of nodes that have to be examinedwhich is at most figure shows linked list in which every other node has an additional link to the node two ahead of it in the list because of thisat most  / nodes are examined in the worst case we can extend this idea and obtain figure hereevery fourth node has link to the node four ahead only  / nodes are examined the limiting case of this argument is shown in figure every th node has link to the node ahead of it the total number of links has only doubledbut now at most log nnodes are examined during search it is not hard to see that the total time spent for search is (log )because the search consists of either advancing to new node or dropping to lower link in the same node each of these steps consumes at most (log ntotal time during search notice that the search in this data structure is essentially binary search the problem with this data structure is that it is much too rigid to allow efficient insertion the key to making this data structure usable is to relax the structure conditions slightly we define level node to be node that has links as figure showsthe ith link in any level node ( >ilinks to the next node with at least levels this is an easy property to maintainhoweverfigure shows more restrictive property than this we thus drop the restriction that the ith link links to the node aheadand we replace it with the less restrictive condition above when it comes time to insert new elementwe allocate new node for it we must at this point decide what level the node should be examining figure we find that roughly half the nodes are level nodesroughly quarter are level andin generalapproximately / nodes are level we choose the level of the node randomlyin