Some observations on skip-lists

Sen , Sandeep (1991) Some observations on skip-lists Information Processing Letters, 39 (4). pp. 173-176. ISSN 0020-0190

Full text not available from this repository.

Official URL:

Related URL:


The Skip-list data-structure was proposed by Pugh as an alternate to balanced binary search trees. This remarkably simple data-structure uses randomization and Pugh proved that the expected performance is comparable to the balanced trees. In this note we prove that the performance can be further guaranteed in the following sense: the probability of the search time or space complexity exceeding their expected values, approaches 0 rapidly as the number of keys increases.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
Keywords:Analysis of Algorithms; Data Structures
ID Code:53427
Deposited On:08 Aug 2011 12:08
Last Modified:08 Aug 2011 12:08

Repository Staff Only: item control page