Re: Overlays as an AA-tree

[Andreas Politz]

Joakim Jalap <address@hidden> writes:

> Andreas Politz <address@hidden> writes:

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

and ordered as well.

> The problem is when we need to delete one of those nodes which has 1
> as key. 

Well, you just delete the first node you find, which is the root.  Since
they are all equal it doesn't matter.

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

Neither, since you already found what your looking for.  Yes, its an
exaggerated example.

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

But if you know the memory address of an overlay, then what are you
looking for ?

I think its dawning in me what you are talking about.  You seem to think
of nodes as a distinct entity without any ties to the overlays they are
representing ?  And then you want to solve the problem of matching an
overlay with its corresponding node, by searching for it in the tree.
Does that sound familiar ?

-ap