want to guarantee getting the correct answer but if we are willing to accept near certainty instead of absolute certaintywe can gain lot in terms of speed as an alternativeconsider this probabilistic algorithm pick numbers and choose the greater this will be in the upper half with probability / (since it is not in the upper half only when both numbers we choose happen to be in the lower halfis probability of / not good enoughthen we simply pick more numbersfor numbersthe greatest is in upper half with probability - regardless of the number that we pick fromso long as is much larger than (otherwise the chances might become even betterif we pick ten numbersthen the chance of failure is only one in what if we really want to be surebecause lives depend on drawing number from the upper halfif we pick numberswe can fail only one time in billion if we pick enough numbersthen the chance of picking small number is less than the chance of the power failing during the computation picking numbers means that we can fail only one time in which is less chance than any disaster that you can imagine intervening skip lists in this section we will present probabilistic search structure called the skip list like bstsskip lists are designed to overcome basic limitation of array-based and linked listseither search or update operations require linear time the skip list is an example of probabilistic data structurebecause it makes some of its decisions at random skip lists provide an alternative to the bst and related tree structures the primary problem with the bst is that it may easily become unbalanced the - tree of is guaranteed to remain balanced regardless of the order in which data values are insertedbut it is rather complicated to implement presents the avl tree and the splay treewhich are also guaranteed to provide good performancebut at the cost of added complexity as compared to the bst the skip list is easier to implement than known balanced tree structures the skip list is not guaranteed to provide good performance (where good performance is defined as th(log nsearchinsertionand deletion time)but it will provide good performance with extremely high probability (unlike the bst which has good chance of performing poorlyas such it represents good compromise between difficulty of implementation and performance figure illustrates the concept behind the skip list figure (ashows simple linked list whose nodes are ordered by key value to search sorted linked list requires that we move down the list one node at timevisiting th(nnodes in the average case imagine that we add pointer to every other node that lets us