bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful

[Stefan Monnier]

>> The following code in `interval_tree_insert`:
[...]
>> suggests that N->left are <= and N->right are > but my reading of the
>> comment is that the only thing we can rely on is that N-<left is <= and
>> N->right is >=
>
> Phew.  I'm not sure but I get the feeling that makes implementing a
> successor function, let's say, challenging.

I don't think it makes any difference in that respect, no.  The notion of
"successor" is just "the successor in the in-order traversal of the
tree" and while rotations change the initial property that "N->right are >",
they don't change the in-order traversal output (they don't re-order
nodes w.r.t in-order traversal (or in reverse order for that matter)).

As alluded to at the end of my previous email, while RB trees are
typically used for your usual binary tree which comes with some notion
of ordering that makes lookup O(log N), the RB trees ensure balance
without relying on any notion of ordering since the rotations just
blindly preserve the order as a side effect but they don't themselves
need to call the ordering function to decide how to do their job.


        Stefan