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)

Answers


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.


Need Your Help

Join Non ContentPart Table to ContentPart Table Using Orchard HQL API

asp.net-mvc hql orchardcms

I am trying to perform a simple join between two different tables using the Orchard HQL API. The problem is that one of the tables is not a ContentPartTable. Is this possible??

UILocalNotification alternative for iOS3

iphone objective-c cocoa-touch

I am building an iPhone application and I want to use UILocalNotification to schedule an alarm for an event. The problem is that UILocalNotification only works from iOS4, and I want to try and make...