Re: Overlays as an AA-tree

[Joakim Jalap <joakim.jalap@fastmail.com>]

Andreas Politz <politza@hochschule-trier.de> writes:

>
>>> I think if a tree is sorted by begin only [...] the tree can't possibly become
>>> disordered [...]
>>
>> But if the tree is sorted by begin only we can have multiple overlays in
>> the same position, how does that work? [...]
>
> Why should that be a problem ?  A search-tree may contain some key
> multiple times.  The question is whether this is useful.  I don't think
> it is in this case, because including end in the comparison does not
> help with finding all overlays intersecting some position or interval
> (i.e. it does not allow pruning some sub-trees).

Hm, that is true... I think I actually started like that, but then got
stuck in the mindset of having a total ordering. So, will there be a
linked list in each node for the overlays, or how will it work?

> It would be useful, e.g. if we were going to search for an overlay
> starting at B1 and ending at E1, but I don't see were we needed this.

I can confirm that we never need it :)

>> Hm I don't understand this. How would we use two trees?
>
> If I'm right, we *could* use one tree for front-advance overlays and one
> for non-front-advance ones, such that these tree won't ever become
> unordered by insertion/deletion of text.

Sounds like a good idea.