Yggdrasill
0.2

This page roughly explains what a RedBlackTree, an Interval Tree, an Interval Map or a Dynamic Segment Tree can do for you.
A redblack tree is a balanced binary search tree. It allows you to insert elements (nodes) into it, which are associated with some key. Inside the redblack 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 redblack tree, see RedBlack Tree Example .
A zip tree is a balanced binary search tree, just as the redblack 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 .
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 .
An interval tree is an extension of (in this case) a redblack 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 .
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:
For an example on how to use the interval map, see IntervalMap Example .
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 redblack 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.