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

Vaginismus

I'm guessing that this is a highly specialized discipline, so probably not many people here with experience. And a lot would depend on the data structure you choose. But I'd observe that you probably have to traverse the tree to locate the node to remove, so you could pass in the parent pointer as you traverse, vs needing to store a parent pointer in each node. – Birch

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.

Samaniego