Re: Overlays as an AA-tree

[Andreas Politz]

Andreas Politz <address@hidden> writes:

> 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.

Well, this assumption was a little bit short-sighted, since deleting a
node may restructure the tree in way which changes this ancestor
relationship.  

I thought about adding the front-advance property into the key-function,
but that just moves the problem to the deletion stage.

What I ended up doing was removing all nodes with front-advance set and
starting at the insert position before doing the normal operation on the
other nodes, and then reinserting the front-advance ones with
incremented begin (according to length of the "inserted text").

-ap