Re: Overlay tree. Stuck again

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

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

> Eli Zaretskii <eliz@gnu.org> writes:
>> [...] try removing them from the tree, and then re-adding them [...]
>
> Yes, that is the "big hammer" approach :) I hae thought about it, but I
> think the problem is that it will be too expensive. [...]

Joakim, I think that trying to somehow manually fix the disorder is at
least as expensive as a deletion and reinsertion.  Because if it weren't
you would have essentially discovered a better algorithm for balancing
trees then the one you've got.

The trick is probably to gather the dirty nodes in post-order and delete
them all at once. This way you're only removing a node, if its
corresponding sub-tree is in order.  After that you're free to reinsert
them again.

-ap