First, some background is in order to explain why linked lists are relevant to the topic

of binary trees. In this module we discussed the basic binary tree, in which items are added

without regard to their relative ordering. In the next module we will talk about ordered binary

trees, where the items are stored in a binary tree in sorted order; the resulting trees are called

$$search trees$.$ As we will discuss in modules $10$ & $11,$ the implementations of search trees

can be complicated, but the advantage is that searches can be performed in O$($log N$)$ time,

something that cannot be accomplished with a standard linked list $($although it is possible for

an array$-$based list$).$ One alternative to the binary search tree that more closely resembles a

linked list is known as a skip list. A skip list has as its base a linked list structure, but overlays

this linked list with one or more levels of indexing. The indexes consist of nodes that skip over

one or more nodes of the linked list, as shown in the diagram below:

One prerequisite for the skip list is that the items must be stored in sorted order, or

the indexing won$$t work. With a skip list, to find an item one begins with the first node at the

highest index level $($level $2$ in the diagram above$),$ and traverses the nodes in that index level.

As long as the item indexed is less than the item being searched for, the traversal continues

at that index level. If an item is greater than the item being searched for, or the last node in

that index level has been reached, it is necessary to back up to the previous index node on

that level, then go down to the corresponding index node on the next lowest level, and begin