AW's kd-tree
The subject of this thread was changed from "gilgalad's kd-tree" to "AW's kd-tree".
I suggest you stop worrying about how fast a particular kd-tree is and just use one of them. The top few kd-trees are all very similar in performance and I am sure each have their pro's and cons. I personally still use Rednaxela's Gen 2 tree because of how self contained it is (vs his Gen 3 which has more structure).
I'm not sure if Andrew Wells wrote a Kd-Tree. Perhaps if you tell us which tree you're actually talking about it might help?
If you were using it for Robocode I don't think you'd be worrying about which one. What are you using the tree for?
The tree that I have, is approximately as fast as rednaxela's 2nd gen. (slightly faster in my tests). Are you trying to write a kd-tree or just looking for one to use? As far as I know, jk's tree, rednaxela's tree, and my tree are all quite similar. Bucket kd-tree. No recursive search methods. Use a MBR (minimum bounding rectangle). Use a heap to store the points. I think rednaxela was the first to introduce most of those ideas to robocode, but in my tests, mine was slightly faster and presumable the same can be said of JK's tests.
