论文标题
拉链段树
Zipping Segment Trees
论文作者
论文摘要
通常使用片段树回答一组间隔的刺激查询。 Van Kreveld和Overmars提出了一种动态的细分树，它使用红色树木进行重新平衡操作。本文提出了拉链段树 - 基于拉链树的动态段树，最近由Tarjan等人引入。为了促进拉链段树，我们展示了如何在拉链树的操作过程中维护某些段树的性质。我们提出了基于红色树木，重量平衡的树木和新型拉链段树的几种变体的动态段树的深入实验评估和比较。我们的结果表明，拉链段树比基于旋转的替代方案更好。
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.
