Re: Overlays as an AA-tree

[Andreas Politz <politza@hochschule-trier.de>]

Joakim Jalap <joakim.jalap@fastmail.com> writes:

> Andreas Politz <politza@hochschule-trier.de> writes:
>
>> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>>
>>>> If I'm right, we *could* use [two trees] [...]
>>>
>>> But I don't think this one is an efficient solution.[...]
>>
>> Yes, I'm not in favour of it either.
>>
> And here I thought it was rather an elegant solution :) (to the problem
> of one overlay's beg going past another's because of an insert).

I think the problem is that this would entail either having lots of ugly
code at places where this double-tree is accessed, or having to create
some kind of layer, hiding the fact that there are two trees.

> What's a better way? When adjusting for an insert at an overlay with
> front-advance non nil, first delete it from the tree, then reinsert it?
> Isn't there a risk the tree becomes unbalanced otherwise?

I think its safe (in a RB-Tree anyway, AA probably as well) to remove
the root node of the tree, given, that all other nodes are sorted.

When recursively applied, it tells us that before we are attempting to
remove an unsorted node, we need to make sure that its descendants are
in-order.  In order to do that we just need to collect them
appropriately while traversing the tree.

BTW. I don't think this would change the complexity of the algorithm,
since we're already in k*log(n) territory.

-ap