Is there a way to balance a binary tree continuously?

Question

In my game I have a tree of objects in 3D space, to which new objects are frequently added.

Over time, the binary tree becomes unbalanced which is a big problem for efficiency as the tree can become quite large. It might even be at risk of stack overflows from deep recursion.

At the same time, it is important to keep branches of the tree close together in 3D space. So I can't arbitrarily swap tree nodes around to balance the tree.

Is there an efficient algorithm that will do the following:

• Allow efficient additions to the tree (O(log n) max)
• Keep the tree approximately balanced as additions are made
• Ensure that branches of the tree contain objects that are close to each other in 3D space (i.e. it works at least approximately as a spatial subdivision tree)

Answer 1

It sounds like you need an octree, binary trees really only work for sorting stuff in one dimension. Note that you still will have to travel down multiple branches to find all objects within an arbitrary zone, no data structure can prevent that.

Of course, it would be possible to store items in a standard search tree according to their position on a 3D Hilbert curve, that would be kinda the same thing as an octree, just more convoluted to implement.

Answer 2

The need for nodes to be close to each other just rules out any efficient remodelling of your tree structure (otherwise you could use a Red Black Tree which is 'self balancing for example).

If you want a binary tree structure you can use a BSP structure or a KD-Tree.

Otherwise check out the Octree, the Loose Octree or why not the R-Tree