Re: Fixing problems

[martin f k. <ma...@ma...>]

also sprach Paul <ele...@ya...> [2004.11.04.1040 +0100]:
> Why do you need to follow an erase() with an optimise() call?  Is
> it possible to keep the tree correct when erasing?  Is this a bug
> or by design?

It is not necessary to call it after every erase, but since an erase
must do a search, subsequent erases are going to be increasingly
slower.

I don't think it is a bug, nor did I make this a design choice. The
KDTree algorithm does not provide for maintaining a balanced tree
(e.g. like a red-black tree). In addition, I have been unable to
come up with an efficient means to keep the tree balanced.

> Is optimise() always required, even after an insert() ?

No, but before the first search. I usually insert thousands of items
and then optimise once before using the tree.

> This is a huge problem if you want to remove a bunch of items...

I know. I would be happy to discuss possible solutions, but I don't
think it's going to be trivial. The algorithm exists since 1975 and
so far, no solution has been found.

--=20
martin;              (greetings from the heart of the sun.)
  \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck
=20
invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver!
spamtraps: mad...@ma...
=20
"montag, why do you burn books?"
"it's a job like any other, pay is good and there is a lot of variety."
                                                -- ray bradbury (f451)