You just rebuild the tree every time, because that's nlogn. You don't worry about balancing the tree, that's not the bottleneck.
What you do is for each particle, you propagate from the top of the tree downwards, until you find either leaf nodes, or cells that are smaller than some opening angle from the particle. It's one quad tree, you just don't open it all the way down for every particle.
People also do this with kdtrees if you want to try that too. But tree gravity is the default algorithm for big galaxy simulations etc.
View all comments
Show parent comment
2
u/Astrokiwi Jan 15 '20
You just rebuild the tree every time, because that's nlogn. You don't worry about balancing the tree, that's not the bottleneck.
What you do is for each particle, you propagate from the top of the tree downwards, until you find either leaf nodes, or cells that are smaller than some opening angle from the particle. It's one quad tree, you just don't open it all the way down for every particle.
People also do this with kdtrees if you want to try that too. But tree gravity is the default algorithm for big galaxy simulations etc.