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

[img] Text
1609.08513v3.pdf - Accepted Version

Download (1MB) | Preview

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: 28 Apr 2022 21:12
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3058939