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 |
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 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: | 05 Jun 2025 21:17 |
| DOI: | 10.1137/1.9781611975505.8 |
| Related Websites: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3058939 |
Altmetric
Altmetric