data structures

Zipping Segment Trees

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 …

Engineering Top-Down Weight-Balanced Trees

Weight-balanced trees are a popular form of self-balancing binary search trees. Their popularity is due to desirable guarantees, for example regarding the required work to balance annotated trees. While usual weight-balanced trees perform their …