Depth Of A Node And Distance Between Two Nodes In A Skip List

Abstract

The skip list was introduced as a data structure for dictionary operations. Using a binary tree representation of skip lists, we obtain the limit law for the path lengths of the leaves in the skip list, and Distance between two nodes. In our study we will study some parameters about the skip lists as a random graph. We are essentially interested in the depth of a node, the distance between two no[1]des. The techniques used are very wide: moment generating functions, techniques used in random trees, central limit theorem...etc. A precise average case analysis is performed for the parameter number of left- to-right maxima. Some additional results are also given. Due to their poor cache behavior when compares with e.g. B-trees, but fear not, a good implementation of skip lists can easily outperform B-trees while being implementable in only a couple of hundred lines. There are many problems related to skip list that are studied. We plan to continue this study in order to better characterize the very useful objects in computer Science.