Need help with mah BSTree (aka jumbled mess)

This is a discussion on Need help with mah BSTree (aka jumbled mess) within the C++ Programming forums, part of the General Programming Boards category; Okay, I'm finishing up my Binary Search Tree implementation that I'm doing out of boredom. The one thing that I'm ...

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

    Unhappy Need help with mah Binary Search Tree (aka jumbled mess)

    Okay, I'm finishing up my Binary Search Tree implementation that I'm doing out of boredom. The one thing that I'm having trouble on is a delete algorithm that isn't recursive. Most cases work great. When the deleted node has only one subtree (left or right), deleting a leaf, and for the most part deleting a node with two subtrees works alright. Here is my implementation. If it's too messy, tell me, I'll clean it up and repost it . But I'll hilight the problem area

    Code:
    template <typename T>
    void BSTree<T>::Delete(T x)
    {
        if (root == NULL)
        {
            std::cout << "-- Tree is empty --" << std::endl;
            return;
        }
    
        BinaryTreeNode<T>* prev = root;    //points to previous node
        BinaryTreeNode<T>* next = root;    //points ahead
        size_t dir = 0;                 //globally stores pointer direction
    
        while (true)
        {
            if(next == NULL)
            {
                std::cout << "-- " << x << " not found --" << std::endl;
                return;
            }
            else if (next->data == x)    //if the data has been found and...
            {
                //...both children are null
                if (next->child[0] == NULL && next->child[1] == NULL)
                {
                    if (next == root)   //delete if data is at root
                        root = NULL;
                    else
                        prev->child[dir] = NULL;
    
                    delete next;
                }
                else if (next->child[0] == NULL)    //...the left child is null
                {
                    if (next == root)
                    {
                        root = next->child[1];  //point root to it's only child
                    }
                    else
                        prev->child[dir] = next->child[1];
    
                    next->child[1] = NULL;
                    delete next;
                }
                else if (next->child[1] == NULL)    //...the right child is null
                {
                    if (next == root)
                        root = next->child[0];
                    else
                        prev->child[dir] = next->child[0];
    
                    next->child[0] = NULL;
                    delete next;
                }
                else    //...neither child is null
                {
                    //pointers to right subtree
                    BinaryTreeNode<T>* prevR = next->child[1];
                    BinaryTreeNode<T>* nextR = prevR;
    
                    //find the smallest node in right subtree and replace
                    while (true)
                    {
                        if (nextR->child[0] == NULL)
                        {
                            //Connect smallest node's parent
                            //with smallest node's right child
                            //will be null if no right child exists
                            prevR->child[0] = nextR->child[1];
    
                            //replace node
                            next->data = nextR->data;
    
                            //if the rightmost node has no children
                            //set next's right child to NULL
                            if (prevR == nextR && nextR->child[1] == NULL)
                                next->child[1] = NULL;
                            else
                                next->child[1] = nextR->child[1];
    
                            //nullify node's children array
                            nextR->child[0] = nextR->child[1] = NULL;
                            delete nextR;
                            break;
                        }
                        else
                        {
                            prevR = nextR;
                            nextR = nextR->child[0];
                        }
                    }
                }
    
                std::cout << "-- " << x << " has been deleted --" << std::endl;
                return;
            }
            else
            {
                prev = next;
                dir = x < next->data ? 0 : 1;
                next = next->child[dir];
            }
        }
    }
    If my tree/subtree is in the form

    ------O
    -----/-\
    ----O---O


    nd I need to delete the root of that tree, I have a problem with the getting the root of that tree to have their right child nulled. What I'm basically saying is that is there a more "modular" way to implement this without being recursive, and without confusing myself by trying to find clever ways to make use of as few pointers as possible.

    Edit: Okay new and improved BST deletion, if there's anything missing which I can't tell at the moment please advise me on some ways to improve it.
    Last edited by indigo0086; 10-05-2007 at 10:52 AM.

  2. #2
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    was it this easy
    Code:
                            if(prevR == nextR)
                                next->child[1] = NULL;

    NO, DO NOT WORK!
    Last edited by indigo0086; 10-05-2007 at 10:08 AM.

  3. #3
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    Never mind, fixed it. The problem was with my BinaryTreeNode destructors, they destroy their left and right child, so I had to go back and re-route all the references the node to be deleted had with any node that was to stay in the tree.

    And the above code did work, the destructors were the problem.

  4. #4
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    Ok the above code didn't work, if the tree was in the form:

    [FONT=Courier New]------(x)
    -----/---\
    ----O-----O
    ---/-------\
    --O---------O

    where I am to delete x then there is a problem, so I changed it to.

    Code:
                            //if the rightmost node has no right children
                            //set next's right child to NULL, otherwise, point
                            //next's right child to nextR's right child.
                            if (prevR == nextR && nextR->child[1] == NULL)
                                next->child[1] = NULL;
                            else
                                next->child[1] = nextR->child[1];
    [/code]

    it just seems like I'm building a state machine rather than intuitively making routines for the damn thing.

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

  6. #6
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    Now I'm goign to work on the traversals. What I want to know is there a nonrecursive method to this, or are the walks pretty much only practical using recursion?

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21