[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Overlays as an AA-tree

From: Andreas Politz
Subject: Re: Overlays as an AA-tree
Date: Tue, 07 Feb 2017 13:35:39 +0100
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)

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

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


reply via email to

[Prev in Thread] Current Thread [Next in Thread]