Interval Tree from a multimap

[ricardomatias]

It's hard to come by an interval tree which works without allocations. I wonder if a multimap could be used as the base for one. I'm not entirely sure of how much effort is involved in one. Does anyone have any opinions about it or other recommendations?

[jwellbelove]

I sure it should be possible to create one from a map type.
I've not looked at interval trees before, so I don't really know how complex a task they may be.

[ricardomatias]

According to wikipedia:

An augmented tree can be built from a simple ordered tree, for example a binary search tree or self-balancing binary search tree, ordered by the 'low' values of the intervals. An extra annotation is then added to every node, recording the maximum upper value among all the intervals from this node down. Maintaining this attribute involves updating all ancestors of the node from the bottom up whenever a node is added or deleted. This takes only O(h) steps per node addition or removal, where h is the height of the node added or removed in the tree. If there are any tree rotations during insertion and deletion, the affected nodes may need updating as well.

The key takeaways are:

• keys are comprised of low, high and max
• max needs to be updated when tree changes
• searching algorithm would need to check max value as well