Re: intervals.c: About interval tree

[Stefan Monnier]

> It seems the tree that is used is "mostly balanced tree".  I am
> wondering what sort of "balancedness" we are talking about i.e.. what
> invariant does the tree satisfy?

If you look at balance_an_interval, I think it's just "balanced" in the
sense that the left and right subtrees cover (as much as possible) the
same text-size.

So it's different from the usual literature, where "balanced" refers to
the depth of the tree.


        Stefan "who replaced it with a splay-tree at some point"