It does not do re-balancing, but in this type of application you talk about it may not be needed.

Funny part, is that implementation may be easier to read than algo description I read first time:

http://hackage.haskell.org/package/Octree-0.5.4.2/docs/src/Data-Octree-Internal.html.

It worked perfectly for my use cases (checking for collisions of 1000-100000 objects),

but (just in case) the initial creation from list structure make the octree balanced.

Note that balanced octree is supposed to be much faster than KD-tree, and may be also faster than R-tree in memory, since it is very shallow structure - log_8 between 10k and 1m changes only from below 5 to below 7!

I was also very happy with its cache behaviour, although in theory R-tree could be better.

I am also extremely interested in making sure that Haskell has a good choice of multidimensional metric data structures, so I am closely following maintenance of kd-tree, Ashley´s, and Gloss´ quadtrees.

And if you really want to have re-balancing, please contact me on my email.

--

  Best regards

    Michal