[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: Fri, 03 Feb 2017 16:02:24 +0100
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)

Joakim Jalap <address@hidden> writes:

> Hm, that is true... I think I actually started like that, but then got
> stuck in the mindset of having a total ordering. 

No you're right, the comparison function needs to implement a total
ordering, but this just means, simply put, that any pair of nodes x, y
needs to be comparable, i.e. x <= y OR y <= x .  But this does not
exclude the case where both these statements are true, i.e. x = y.

> So, will there be a linked list in each node for the overlays, or how
> will it work?

Well, imagine your AA-Tree, with <= as relation and where you keep
inserting 1s and nothing else.  How will it look ?


reply via email to

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