W Karas wrote:
> wade wrote:
>
> The algorithm is based on the recursive reduction:
>
> intersections = intersections with chord with min(end - start) +
> remaining intersections
>
> It doesn't matter if the chord with min(end - start) is the shortest
> chord or not.
I missed that. I didn't catch the fact that your algorithm works
correctly, if I name a chord (0,10), or if I name it (10,360).
> > The AVL tree is perhaps more complex than necessary. You can build
> > your tree balanced to begin with (its contents are the integers from 0
> > to N-1). Each node contains its "descendant" count.
>
> So you mean sort all the points, then construct a fully balanced
> tree? I think this might be slower than building an AVL tree
> insert by insert, but that may be more than canceled out by
> the faster searches.
>
> > When logical
> > deletions occur, don't actually remove any nodes. Just update the
> > "descendant" counts so that they reflect only living descendants.
>
> This would reduce deletion time, but increase average search time.
> I would guess you are right that, at least in the average case,
> it would be an optimization. But it would take some complex
> analysis to prove this.
But with a full tree you don't need to store or update pointers.
Consider the full balanced tree with three levels. The logical
structure is:
3
1 5
0 2 4 6
Define the "level" of a node as its distance from the leaves. (So
0,2,4,6 are at level zero).
The "level" of a node is also the number of trailing '1' bits in its
binary representation (something you can obviously compute in log n
time). The parent of a node, k, is
k + parent's level, if k/2 is even
k - parent's level if k/2 is odd.
So I can actually store my "tree" in an array, indexed by
endpoint-number. The only contents of each node are the population of
that node, and its children.
void DeleteEndpoint(unsigned int k)
{
unsigned int t = k;
int level = 0;
while(t & 1)
{
++level;
t >>= 1;
}
while(k < N)
{
--tree[k];
++level;
k += level - ((k>>1)&1)*2*level;
}
}
which, I believe, will be fast compared to AVL deletion, except for the
last few deletions, where the AVL tree has gotten quite small.
Building my tree is a fast (O(N)), but I've also got to sort the
endpoints. However, I'd expect a heapsort to be faster than an AVL
build from unsorted data.
I may need some extra nodes (if there are 9 elements, I need node 11,
which is 8's grandparent). On the other hand, each node holds only a
count. In an AVL tree, each node will hold a count, two pointers, and
a flag.
Anyway, your algorithm is fine. You were lamenting about the need for
a complex AVL tree, so I was presenting an alternative, which I felt
was simpler. Of course if you "know" AVL, and you have to learn my
structure, the simplicity is debatable.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
