C++ - removal of a node in an AVL Tree

I'm currently trying to implement an AVL tree in C++, so far I've done pretty much everything except a node removal.

1) Can someone confirm that my algorithm for removing a node is correct?

• Find the node to delete in the tree
• if the node has 0 child : delete the node
• else, if the node has 1 child: delete the node, and re-link his child
• else (2 children): find its successor, and swap the node to delete with its successor. then repeat the steps to delete the node (which is now where its successor 开发者_运维技巧was).
• Rebalance the tree after the insertion (it'll rebalance the tree recursively...)

I've done this, but the part where I'm not sure, is the step where I delete the node. Do I have to delete the reference to the node also, or it'll be managed? (Because I've passed in parameter a Node*&, but the successor is only a Node* in the function...)

I'm not sure I'm being super clear, let me know if you need more details.

(I would post some code, but unfortunately I speak french, so you won't understand much from it, I guess)

If the node was created using 'new' than it needs to be explicitly deleted, absolutely. They question will be where. If you are deleting the node, (the assumption is nobody else needs the contents of the node) then you should also delete the node itself after completing the nodes removal from the tree.

Now, the reference to the node is another matter. If the reference is an artifact of a method argument definition, you don't have to do anything with it. The reference was created on the stack to help with the method call. If I remember my C++, references can never be null, which means never having to say you're sorry(bad joke), er never having to delete them.

[EDIT] The OP says, "Because I've passed in parameter a Node*&, but the successor is only a Node* in the function...)" so I assumed you meant something like:

void removeNode(Node*& node) 

which is then called using

void foo()
{
    Node* n = new Node();
    // for example
    removeNode(n);
}

My C++ is a bit rusty but the idea here is that 'n' is a pointer but the argument type of removeNode() is a reference to a pointer. The caller doesn't know that a reference is involved, it just passes 'n' expecting the arg type to be pointer-to-node (Node*). The compiler is creating the reference as a wrapper around the argument so only the callee is aware of the reference. Since the reference is created on the stack, it will be 'managed' properly when removeNode() returns. The node pointed to by 'n' still needs to be deleted, the question is which code should handle it.

First thought would be for 'removeNode()' to do it. One problem is that it only has a reference to it and if you delete the pointer (the target of the reference) the reference will be null which is a bad idea / not allowed. Just thinking of the syntax to attempt it made me cringe.

So, have the client code to do it, like so:

void foo()
{
    Node* n = new Node();
    // for example
    removeNode(n);
    delete n;
}

Basically, you need to have a plan for the scope of your node pointers. As long as it is consistent, you could do it in several different ways. If you wanted removeNode() to handle the deletion, then change the argument type to a pointer instead of a reference and document the call so the expectation is it both removes the node from the tree and deletes the memory as well.

The tricky part with your question is that "deleting the reference to the node" is actually rather vague: depending on what you consider "deleting the reference", the answer can be 'yes' or 'no'.

As I see it, you are going to "delete the reference to the node" as part of relinking the tree. The crucial part is the fact that your method receives the node pointer as Node *&: with this, your method doesn't just get the pointer to the node under scrutiny, it receives a reference to where this pointer is stored in the parent node. You have to modify this reference in order to keep the tree linkage intact.

So if your method does something like this:

void deleteNode (Node*& node) {
    if (node is the right one to delete) {
        Node * tmp = node;
        node = node->successor;
        delete node;
    }
    else
        deleteNode(node->successor);
}

the assignment node = node->successor actually modifies the previous nodes' successor field. Without this assignment, your tree structure would be damaged, as the previous nodes' successor field would point to a now-deallocated Node.

I you are coding in standard C++ then nothing will be "managed" for you. If you use smart pointers then they will take care of the deallocations for you though.

As for your interface, I suggest the remove() function takes a pointer to the node to delete. Then you don't need to bother with finding the node, as it is given. Do write a find() function though, so clients can find the node themselves.

Finally, I am not sure I follow your third case, where a node to delete has two children. In an AVL tree when a node to delete as two children you can swap it with the right-most child of the left subtree of the node to delete. Once swapped, the node to remove has exactly one or zero children, so you essentially reduced the problem to these two cases.

For example:

            20
     40            15
  60    35     18       10
80    38  30 19  17   13   8

In the above tree if you wish to remove node 20 then you swap it with node 30 (the child of node 35):

            30
     40            15
  60    35     18       10
80    38  20 19  17   13   8

And then remove node 20 as a child-less node. If there were no node 30 then the right-most child of the left subtree would be node 35, and you'd swap node 20 with that. Then you'd have to remove a node with a single child, which you know how to do.

Do note that until you're done with the deletion the tree is in an inconsistent state. This is important if you're working concurrently.