The problem is that at each level, the set of items has to be resorted and divided according to a different key, so rebalancing is (IIRC) non-trivial.<br><br>However, there are sure to be ways to improve its performance. I was thinking of sorting the items once for each key, and then using tags to eliminate or mark off uninteresting items at each level. Trading scanning O(n) for lots of extra sorting O(nlogn).<br>
<br>there are sure to be other ways too<br><br>i have a problem where i have to search a tree and then remove items from the tree. instead of using erase etc, i use find_nearest_if() and pass it a functor that checks that the node hasn't been tagged as 'removed'. so it'll effectively ignore items that I want erased.<br>
<br><div class="gmail_quote">2008/5/3 Eric Fowler <<a href="mailto:eric.fowler@gmail.com">eric.fowler@gmail.com</a>>:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Well I have noticed that running optimise() on a tree of half a million points seems to take twice as long (or more) than building the tree from zero. <br><br>So why run it? I was under the impression that removal of elements from a tree with erase() or erase_exact() left the tree in a undefined condition so further searches might miss points. Is that right? Or is optimise() just about performance, not correctness?<br>
<br>If that is the case, perhaps the tree could be extended so when an item is removed, the tree flags the highest node that is above everything in need of optimisation, so optimise() can search the tree only for subtrees that really need the treatment, thus saving time. <br>
<br>Just my $0.02. <br><font color="#888888"><br>Eric<br>
</font><br>_______________________________________________<br>
libkdtree-devel mailing list<br>
<a href="mailto:libkdtree-devel@lists.alioth.debian.org">libkdtree-devel@lists.alioth.debian.org</a><br>
<a href="http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel" target="_blank">http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel</a><br>
<br></blockquote></div><br>