Deleting a single point from a quadtree

Chidori chan

Hi- I have been trying to work out how to delete a single point from a quad tree and am having no luck at all. Below are the code snippets for delete the entire tree then my failed attempt at deleting a single point. If someone could explain what I am doing wrong I would appreciate it. Deleting the entire tree:

qnode *
deleteTree (qnode * root)
{
int i = 0; //not initalizing to 0 will create segmentation faults.
for (i = 0; i < 4; i++) //four loop must be here otherwise it will quit at the first quadrant if there is no point stored there.
{
if (root == NULL)

return root;		// Sub-tree is empty

  /\* Delete tree \*/
  if (root->children\[i\] != NULL)
{
  free (root->children\[i\]);
  deleteTree (root->children\[i\]);
  if (root->leaf == TRUE)
    {
      free (root);
      root->leaf = NULL;
    }
  root->children\[i\] = NULL;
  root->leaf;
  root->cx = NULL;	//returning cx, cy, and size to NULL so the blue cross will not be drawn
  root->cy = NULL;
  root->size = NULL;

}
}

}

Failed attempt to delete a single point:

qnode *
deleteP (qnode * root, int vx, int vy)
{
int i = 0;

if (root->px - 5 >= vx && vx <= root->px + 5 && root->py - 5 >= vy && vy <= root->py + 5) // gives a distance of five lee-way for the user to click on the point so they do not have to click exact
{
if (root == NULL)

return root;		// Sub-tree is empty

  if (root->leaf == TRUE)
{

  root->leaf = NULL;
  free (root);
}
  else
{
  root->leaf = TRUE;
  deleteP (root, vx, vy);
  root->px = NULL;
  root->py = NULL;
  free (root);
}
}

}

Thank you for your time

Avi Berger

First, you have bugs in your deleteTree implementation.

Chidori-chan wrote:

free (root->children[i]);
deleteTree (root->children[i]);

This is undefined behavior. Once you have freed the child node, it is no longer yours and you must not access it. Reverse the order of these two lines. There are more problems in your deleteTree implementation as well. I will let you work on finding them. Perhaps I am wrong here, but I would think that deleting a single point actually means deleting the entire subtree starting from that point. Otherwise, what do you do about all those would be orphaned nodes? So I expected to see a call to deleteTree somewhere in deleteP. I didn't find it. Also, I would think that you need to traverse the tree to locate the point to be deleted. I would expect that to be the first thing you would have to deal with, but don't see it in your code.

Please do not read this signature.

Lost User

Without fully understanding the code above I noticed a couple of things in the deleteTree() function:

  if (root->leaf == TRUE)
    {
      free (root);
      root->leaf = NULL;
    }

You then continue using the root pointer. The following statement is meaningless.

  root->leaf;

In the following block in the deleteP() function:

  if (root->leaf == TRUE)
{

  root->leaf = NULL;
  free (root);
}

there is no point in setting root->leaf to null, as you immediately free the object. Similarly in the else block you set two pointers to null immediately before freeing the object. Also both functions have paths that do not return values, and thus should not compile.

txtspeak is the realm of 9 year old children, not developers. Christian Graus

Chidori chan

Thank you all for your help, keeping your advice in mind I have come up with these functions and it kinda works. It will delete points only in a certain area of the screen..

int checkKids(qnode *parent)
{
int i;
for(i = 0; i < 4; ++i)
if(parent->children[i] != NULL)
return 0;
return 1;
}

void deletE(qnode *root)
{
if(checkKids(root) && !root->leaf)
{
root = NULL;
free(root);
}
else
{
int i;
for(i = 0; i < 4; ++i)
if(root->children[i] != NULL)
deletE(root->children[i]);
}
}

void deletePoint()
{
deletE(root);
}

void deletePointS (int sx, int sy, qnode *root)
{
int i;
for(i=0; i<4; i++)
{
if(root->children[i] != NULL)
{
if(root->children[i]->leaf == TRUE)
{
if(isIn(root->children[i]->px, root->children[i]->py, sx, sy, 5))
{
root->children[i] = NULL;
free(root->children[i]);

              if(checkKids(root))
              {
                 free(root);
                 root = NULL;
              }
              return;
           }
        }
        else
        {
           deletePointS(sx, sy, root->children\[i\]);
        }
     }

}

void deleteNode (int sx, int sy)
{
int deleting;
if(deleting == 1)
return;
deleting = 1;
deletePointS(sx, sy, root);
deletePoint();
deleting = 0;
}