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