Let's say I have a quadtree. Let's say I have a moving object inside it.
I understand a quadtree auto sorts itself when you add and delete nodes, but what happens when a node, let's say in his update function moves to the left of another unrelated node? Or basically this node teleports?
What happens to the quadtree? Do I need to rebuild it?
I just can't understand in my mind if quadtrees do automatically self sort when you just update a node data, or if I need to rebuild the entire tree when updating the nodes.
There are many ways I've seen people implement quad-trees for objects which move every frame, including using loose quad-trees for that purpose where the nodes are even allowed to have overlapping AABBs which expand and shrink as objects stored in the leaves move around.
That said, I've found it simple enough to update non-loose versions reasonably cheaply (not as cheap as a spatial hash or grid, however, but cheap enough to maintain steady frame rates with a boatload of entities moving around with collision detection).
Simple way is just remove the element from the tree prior to moving it, move it, then reinsert it to the tree. When you remove an element, check the node(s) to which it belongs. If they become empty (no elements stored, no children), then remove them from the parent. If the parent becomes empty (no child nodes stored in that node and, if you store elements in the branches, then no elements in that node), then remove the parent from the grandparent, and repeat.
Trick to making this fast is to avoid excessive memory allocations. It helps if you use a free list for the nodes, e.g. Another way to potentially speed things up is to detect when an object will not move from one node to another.
For example, you can expand an entity's bounding box or sphere by the time step multiplied by its speed and test if that expanded bounding box/sphere overlaps new nodes. If not, you don't need to remove the element from the tree, move it, and reinsert. You can just go ahead and simply move it. Or you can just store its previous position, move it, and then see if it would belong in different nodes. If so, remove the element as though it had the previous position and then reinsert with the new position. I haven't really found this necessary though with the way I can do most of this stuff with just index manipulation and no heap allocations/deallocations.