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. .

[thumbnail of 1609.08513v3.pdf] Text
1609.08513v3.pdf - Author Accepted Manuscript

Download (1MB) | Preview


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: 06 Jun 2024 21:25
DOI: 10.1137/1.9781611975505.8
Related URLs: