[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 ?
-ap
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/03
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/04
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/04
- Re: Overlays as an AA-tree, Joakim Jalap, 2017/02/06
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/06
- Re: Overlays as an AA-tree, Joakim Jalap, 2017/02/06
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/06
- Re: Overlays as an AA-tree, Joakim Jalap, 2017/02/06
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/06