Thread: deletion of pointers do not "nullify" values.

  1. #1
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901

    deletion of pointers do not "nullify" values.

    I'm doing a binary search tree deletion algorithm but having problems with deletions. The constructors for my BinaryTreeNode class has to nullify the elements of the BinaryTreeNode[2] arrays because by default they are not null, otherwise it would mess up my insertions and searches. But when I delete, they do not revert to a null status. So if I delete one by using a pointer then the deleted one reains a value other than 0x0. Anyone know what's going on?

    Here's the incomplete function

    Code:
    void BSTree::Delete(int x)
    {
        if(root == NULL)
        {
            std::cout << "-- Tree is empty --" << std::endl;
            return;
        }
    
        BinaryTreeNode* rt = root;
        BinaryTreeNode* advance = NULL;
    
        while(true)
        {
            //delete based on deletion rules
            if(rt->data == x)
            {
                //if both children are empty, delete and return
                if(rt->child[0] == NULL && rt->child[1] == NULL)
                {
                    delete rt;
                    std::cout << "-- " << x << " has been deleted --" << std::endl;
                    return;
                }
                
                //..other deletion rules.
            }
            else
            {
                size_t dir = x < rt->data ? 0 : 1;
    
                if(rt->child[dir] == NULL)
                {
                    std::cout << "-- "<< x
                              <<" not found, cannot delete --" << std::endl;
                    return;
                }
                else
                    rt = rt->child[dir];
    
            }
    
        }
    }
    Last edited by indigo0086; 10-02-2007 at 10:55 AM.

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Uh, I'm confused. Is delete supposed to set memory to 0? I thought it was just supposed to free the memory, in a way similar to free(), and then call the destructor (if applicable).... am I missing anything?

  3. #3
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    I thought by freeing the memory, any reference to it had a null value ???

  4. #4
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Accessing memory after it has been deallocated has undefined behavior, I'm pretty sure. If you're deleting an object, you can do something in your deconstructor for that object (set something to null or whatever).

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    If you have, in various parts of the code, the equivalent of
    p = new int;
    q = p;
    delete q;

    Then there is nothing you can do which will affect what p is pointing to. It's obvious to see here that p is now pointing to deallocated memory, and dereferencing it would be "a bad thing".

    You need to add to the code a clear idea of who is responsible for tracking each block of memory. Because if you end up with multiple aliases, then you're always going to be stuck between a crash (any use after free) or a memory leak (not freeing it at all).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    Ok guys, I guess I'm doing too much C# that I mixed the two up. I would have known this a few months ago.

  8. #8
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    OK I got it to work. I just had to keep a front and back pointer too keep track of the nodes so when I deleted the forward, I could set any references to it to null appropriately.

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    I have no idea how you might get the idea that this would work from C#. C# doesn't even have explicit deletion in the first place.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. MergeSort with array of pointers
    By lionheart in forum C Programming
    Replies: 18
    Last Post: 08-01-2008, 10:23 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Pointers equal non--&-ed values
    By C++Child in forum C++ Programming
    Replies: 6
    Last Post: 07-31-2004, 07:06 PM
  4. Displaying pointer's actual values in inheritance
    By Poof in forum C++ Programming
    Replies: 14
    Last Post: 07-29-2004, 07:34 AM
  5. delete and delete[]
    By Hunter2 in forum C++ Programming
    Replies: 13
    Last Post: 06-26-2003, 04:40 AM