Quadtree Removal

Question

I am writing a removal method for a quad tree.

Now when you remove an item in a node, you will need to check its siblings to see if you need to collapse the nodes and merge them into one.

For checking the siblings, should I store a pointer to the parent node, or is there a way to do this recursively and better?

Thanks

Answer 1

For removal in a quadtree you'll need to basically do the following:

1. Find the object's leaf, then remove it from that list (the node that contains the leaves)
2. Check if the removal of the leaf leaves the node empty, if it does, then remove the node itself.
3. Check if the surrounding nodes are empty as well, and if so, collapse this node into the parent by "unsubdividing" (this can get recursively tricky to do). The trick is to just check if the adjacent nodes have anything in them. If not, you're safe to throw the whole quadrant away and step up one level. Doing this recursively will collapse the tree back up to where an adjacent node with a leaf exists.

After step 1, you're basically done. If you want to save memory and keep the tree efficient then you should do steps 2 and 3.

And yes, you should retain a parent node reference to made reverse traversal efficient.