Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2020.25
URN: urn:nbn:de:0030-drops-120990
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12099/
Barth, Lukas ; Wagner, Dorothea
Zipping Segment Trees
| pdf-format: |
|
Abstract
Stabbing queries in sets of intervals are usually answered using segment trees. A dynamic variant of segment trees has been presented by van Kreveld and Overmars, which uses red-black trees to do rebalancing operations. This paper presents zipping segment trees - dynamic segment trees based on zip trees, which were recently introduced by Tarjan et al. To facilitate zipping segment trees, we show how to uphold certain segment tree properties during the operations of a zip tree. We present an in-depth experimental evaluation and comparison of dynamic segment trees based on red-black trees, weight-balanced trees and several variants of the novel zipping segment trees. Our results indicate that zipping segment trees perform better than rotation-based alternatives.
BibTeX - Entry
@InProceedings{barth_et_al:LIPIcs:2020:12099,
author = {Lukas Barth and Dorothea Wagner},
title = {{Zipping Segment Trees}},
booktitle = {18th International Symposium on Experimental Algorithms (SEA 2020)},
pages = {25:1--25:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-148-1},
ISSN = {1868-8969},
year = {2020},
volume = {160},
editor = {Simone Faro and Domenico Cantone},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12099},
URN = {urn:nbn:de:0030-drops-120990},
doi = {10.4230/LIPIcs.SEA.2020.25},
annote = {Keywords: Segment Trees, Dynamic Segment Trees, Zip Trees, Data Structures}
}
| Keywords: | Segment Trees, Dynamic Segment Trees, Zip Trees, Data Structures | |
| Seminar: | 18th International Symposium on Experimental Algorithms (SEA 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 12.06.2020 | |
| Supplementary Material: | https://github.com/tinloaf/ygg/releases/tag/version_sea2020 |
