[Top][All Lists]

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

Re: Overlay tree. Stuck again

From: Andreas Politz
Subject: Re: Overlay tree. Stuck again
Date: Fri, 03 Feb 2017 09:27:36 +0100
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)

Joakim Jalap <address@hidden> writes:

> Eli Zaretskii <address@hidden> 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.


reply via email to

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