CODEWITHSUNDEEP
c++pointerstreeavl-tree
WIllJBD
WIllJBD

Reputation: 6164

Simple AVL tree delete is only working sometimes

I'm working on an AVL tree. It seems the my remove only works correctly some of the time. I built a tree that looks like this

          f
        /   \
       e     j
      /    /   \
     a    h     s

by inserting in the order f e h s j a. I know that it is working correctly on insert and balancing.

When I remove a, or j, or h, or s, or e, everything works fine. If I remove f, then it replaces f with h, which is correct, but I lose j and s.

This is the first function that is called.

    void remove(const ItemType& item)
    {
        if(root == NULL)
            return;
        else
        {
            remove(root, item);
        }
    };

The first function calls this one to recursively find the correct node.

    void remove(Node<ItemType>* & node, const ItemType& item)
    {
        if(item > node->item)
        {
            if (node->rightChild == NULL)
            {
                return; // there is nothing here to remove
            }
            else
            {
                // recurse to next node
                remove(node->rightChild, item);
            }
        }
        else if (item < node->item)
        {
            if (node->leftChild == NULL)
            {
                return; // there is nothing here to remove
            }
            else
            {
                // recurse to next node
                remove(node->leftChild, item);
            }
        }
        else if (node->item == item)
        {
            remove(node);
        }

        if (node != NULL)
            node->updateHeight();
    };

This is the last function to be called. This is where the deletion and swaps are done.

    void remove(Node<ItemType>* & node)
    {
        if (node->rightChild == NULL && node->leftChild == NULL)
        {
            delete node;
            node = NULL;
        }
        else if (node->rightChild == NULL)
        {
            Node<ItemType>* temp = node;
            node = node->leftChild;
            delete temp;
        }
        else
        {
            Node<ItemType>* & temp = node->rightChild;
            while (temp->leftChild != NULL)
                temp = temp->leftChild;

            node->item = temp->item;
            delete temp;
            temp = NULL;
        }

        if(node != NULL)
            node->initializeHeight();
    };

I am wondering if it has something to do with the lines

            Node<ItemType>* & temp = node->rightChild;
            while (temp->leftChild != NULL)
                temp = temp->leftChild;

            node->item = temp->item;
            delete temp;
            temp = NULL;

and the temp pointer is acting in a behavior I am not familiar with, or if my whole implementation is wrong. I know the missing nodes are out there somewhere because my memory leak shows me those two nodes that go missing are never deleted.

Upvotes: 1

Views: 793

Answers (1)

Daniel Fischer
Daniel Fischer

Reputation: 183858

I am wondering if it has something to do with the lines

Yes. Node<ItemType>* & temp = node->rightChild; says temp is an alias for node->rightChild. So the while loop modifies node->rightChild and you lose the handle to the original right child.

Take an ordinary pointer and walk it down the right subtree until you have gotten to the parent of its smallest member. Then get the value of the smallest member to copy it into node->item, and delete the parent's left child.

Upvotes: 2

Related Questions