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)