This page roughly explains what a Red-Black-Tree, an Interval Tree, an Interval Map or a Dynamic Segment Tree can do for you.

Red-Black-Tree

A red-black tree is a balanced binary search tree. It allows you to insert elements (nodes) into it, which are associated with some key. Inside the red-black tree, the elements will be held sorted according to their key. This makes two operations very efficient: Iterating all keys in sorted order, and finding a certain element by key.

For an example on how to use the red-black tree, see Red-Black Tree Example .

Zip Tree

A zip tree is a balanced binary search tree, just as the red-black tree. It is a randomized data structure that has some nice expected guarantees. For details, refer to the article by Tarjan et al..

For an example on how to use the zip tree, see Zip Tree Example .

Weight Balanced Tree

A weight balanced tree (also known as BB[α]-tree) is a balanced binary search tree. It balances subtrees based on the number of nodes in the respective subtrees.

For an example on how to use the weight balanced tree, see Weight Balanced Tree Example .

Interval Tree

An interval tree is an extension of (in this case) a red-black tree. It allows you to insert elements (nodes) into it which are associated with an interval instead of a key. It stores the intervals sorted by their lower interval border plus some meta information. This makes two operations very efficient: Iterating all intervals by their lower border, and finding (iterating) all intervals that overlap with a given query interval.

For an example on how to use the interval tree, see IntervalTree Example .

Interval Map

An interval map stores intervals associated with a certain value. It is somewhat like an interval tree, but aggregates the intervals' values on overlap. For example, let's say you insert the interval [0, 10) with value 1, the interval [5, 15) with value 10 and the interval [15, 20) also with value 10. The interval map will now contain three Segments:

A segment from 0 to 5 having the (aggregated) value 1 (only the first interval participates in this segment)
A segment from 5 to 10 having the aggregated value 11 (both the first and the second interval participate here)
A segment from 10 to 20 having the aggregated value 10. Note that this segment spans two intervals (the second and third), but since they have the same value, there is no segment border at 15.

For an example on how to use the interval map, see IntervalMap Example .

Dynamic Segment Tree

The dynamic segment tree is something between a classic segment tree and Boost ICL's interval_map. It needs an underlying balanced binary search tree, for which you can either use the supplied red-black tree, the weight balanced tree or the Zip Tree. You can find a more detailed description at Introduction to the Dynamic Segment Tree and an example of its usage at DynamicSegmentTree Example.