Median-of-k Jumplists and Dangling-Min BSTs

Nebel, Markus E, Neumann, Elisabeth and Wild, Sebastian ORCID: 0000-0002-6061-9177 (2016) Median-of-k Jumplists and Dangling-Min BSTs. .

Text
1609.08513v3.pdf - Author Accepted Manuscript
Download (1MB) | Preview

Official URL: http://dx.doi.org/10.1137/1.9781611975505.8

Abstract

We extend randomized jumplists introduced by Br\"onnimann et al. (STACS 2003) to choose jump-pointer targets as median of a small sample for better search costs, and present randomized algorithms with expected $O(\log n)$ time complexity that maintain the probability distribution of jump pointers upon insertions and deletions. We analyze the expected costs to search, insert and delete a random element, and we show that omitting jump pointers in small sublists hardly affects search costs, but significantly reduces the memory consumption. We use a bijection between jumplists and "dangling-min BSTs", a variant of (fringe-balanced) binary search trees for the analysis. Despite their similarities, some standard analysis techniques for search trees fail for dangling-min trees (and hence for jumplists).

Item Type:	Conference or Workshop Item (Unspecified)
Additional Information:	appears in ANALCO 2019
Uncontrolled Keywords:	cs.DS, cs.DS, E.1
Depositing User:	Symplectic Admin
Date Deposited:	21 Oct 2019 15:12
Last Modified:	19 Jan 2023 00:21
DOI:	10.1137/1.9781611975505.8
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3058939