Re: Overlays as an AA-tree

[Joakim Jalap]

Andreas Politz <address@hidden> writes:

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

Hm, OK. I interpreted total ordering as always being able to sort the
nodes unambiguously.

>> 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 ?

It will be a bunch of 1s, but balanced, I think... :) The problem is
when we need to delete one of those nodes which has 1 as key. How do we
find it? When we're at the root (which also has key 1), do we go to the
right or to the left?

In the tree I have now, we can find the right node, since even if every
overlay starts and ends at 1, they will still be sorted according to
their address. Well that was the plan anyway, turns out it wasn't so
easy to keep this ordering.

So I think (but obviously most of my thinking so far has been wrong :))
that it might be easiest to keep a linked list of overlays which start
at that position in the node. In the example above, there would then
only be one node, containing a linked list of all the overlays.