title: Find k-th element in skiplist - explanation needed
body: <p>We're learning about skiplists at my university and we have to find k-th element in the skiplist. I haven't found anything about this in the internet, since skiplist in not really a popular data structure. W. Pugh in his original article wrote:<br>
  <em>Each element x has an index pos(x). We use this value in our invariants but do not store it. The index of the header is zero, the index of the first element is one and so on. Associated with each forward pointer is a measurement, fDistance, of the distance traversed by that pointer:<br>
  x→fDistance[i] = pos(x→forward[i]) – pos(x).<br>
  Note that the distance traversed by a level 1 pointer is always 1, so some storage economy is possible here at the cost of a slight increase in the complexity of the algorithms.</em>  </p>
  
  <pre><code>SearchByPosition(list, k)
  if k &lt; 1 or k &gt; size(list) then return bad-index
      x := list→header
      pos := 0
      -- loop invariant: pos = pos(x)
      for i := list→level downto 1 do
          while pos + x→fDistance[i] ≤ k do
              pos := pos + x→fDistance[i]
              x := x→forward[i]
  return x→value
  </code></pre>
  
  <p>The problem is, I still don't get what is going on here. How do we know positions of elements without storing them? How do we calculate fDistance from pos(x) if we don't store it? If we go from the highest level of the skiplist, how do we know how many nodes on level 0 (or 1, the lowest one anyway) we skip this way?</p>