1993 · 26 citations · 26 references
ComputingComputer ScienceAlgorithmsCombinatoricsData StructuresAlgorithm AnalysisApproximation AlgorithmsRandomized AlgorithmsSearching AlgorithmsSkip ListsBalanced Search TreesDeterministic Skip ListsProbabilistic AnalysisSearch Complexity AnalysisSkip List VariantsTrie Data StructuresTrie StructuresUpper Bounds
This thesis is concerned with various forms of skip lists, and with probabilistic analyses of algorithms. We investigate three topics; one topic from each of these two areas, and another topic common to both of them. First, we consider Pugh's skip list. We derive exact and asymptotic expressions for the average search cost of a fixed key and of an average key. Our results improve previously known upper bounds of these two average search costs. We also derive exact and asymptotic expressions for the variance of the search cost for the largest key. Next, we propose several versions of deterministic skip lists. They all have guaranteed logarithmic search and update costs per operation, they lead to an interesting bridge structure between the original skip list and standard search trees, they are simpler to implement than standard balanced search trees, and our experimental results suggest that they are also competitive in terms of space and time. Finally, we consider the elastic-budget trie, a variant of the standard trie, in which each external node (bucket) has precisely as many key slots as the number of keys stored in it. We examine the number of buckets of each size, and we derive exact and asymptotic expressions for their average values, as well as asymptotic expressions for their variances and covariances under the closely related Poisson model of randomness. Our experimental results suggest that maintaining only two bucket sizes may be a very reasonable practical choice.
26
Self-adjusting binary search trees
Daniel D. Sleator, Robert E. Tarjan · Journal of the ACM · 1985 · 1.2K citations · Full text
Skip lists: a probabilistic alternative to balanced trees
William Pugh · Communications of the ACM · 1990 · 1.2K citations · Full text
Edward Fredkin · Communications of the ACM · 1960 · 1.1K citations · Full text
Extendible hashing—a fast access method for dynamic files
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger et al. · ACM Transactions on Database Systems · 1979 · 669 citations · Full text