Introduction

Removing nodes from any dynamic data structure is generally considered more difficult than adding a node. This is especially true of trees.

The following is a "common" care for a tree.

This is a complicated diagram, but it's easier to understand once all the pointers are described.

• pCurr the node that will be removed from the BST.
• pParent the parent of pCurr
• pLeft left child of pCurr
• pRight right child of pCurr
• pMax the rightmost descendant of pLeft
• pMaxParent the parent of pMax (shown as pMaxPar in the picture).
• pMin the leftmost descendant of pRight

The unusual pointers are pMax, pMin, and pMaxPar. These will be explained soon enough.

By the way, all the pointers start with "p", to indicate they are pointers. This can be very convenient when deciding whether to use "." or "->" after the variable. If you see "p", you know it's a pointer, so you use "->" afterwards.

The goal is to remove the node at pCurr (which we'll just refer to as pCurr rather than "the node at pCurr" for brevity).

This is a "common" case, by which the following assumptions are made:

• None of the pointers are NULL pointers.
• No two pointers point to the same node. Thus, all pointers shown are distinct. Each points to a unique node.

There is an additional assumption which isn't so common. pCurr is the left child of pParent. Clearly, some choice had to be made about pCurr relative to pParent for the example above. In your code, however, you must be aware of whether pCurr is a left or a right child.

pMax and replacement node

The goal of remove is to remove pCurr. To do so, we want to find a suitable replacement node. In particular, we want to find a node that can take the place of pCurr and we want to pick that node from either the left or right subtree of pCurr.

Once we make the decision to pick the replacement node from pCurr's left or right subtree, this limits the choice of which node can serve as the replacement node.

The node picked needs to be larger than the keys in the left subtree and smaller than the keys in the right subtree to preserve the BST property (which states that all nodes of a BST must have the property that its value is greater than the keys of its left subtree and less than the keys of its right subtree, assuming we don't allow repeated keys in the BST).

If we pick the node from the left subtree, we must pick some node that must be less than the keys in the right subtree. Fortunately, this is true of all nodes in the left subtree. That is, all keys in the left subtree are guaranteed, by the BST property, to be less than all keys in the right subtree of pCurr.

However, the replacement node picked from the left subtree must also be larger than all nodes in the left subtree. Clearly, that's not possible (since the node with the largest key can't be larger than itself). Of course, that's not really a problem because we will remove that node from the left subtree, and therefore the node with the largest key value will be larger than all nodes that remain in the left subtree.

The question remains: how do we find the largest value node in the left subtree? The answer: start at pLeft and go as far right as possible, stopping just before we reach NULL. That's pMax.

Why does going as far right as possible work? We can prove this by contradiction. Suppose we don't go as far right as possible. There are two choices. Either we stopped at a node, even though there was a non-empty right child, but never went left. This makes no sense because going to the right child would produce a larger value.

The other choice was to go down to a left child. That too doesn't make sense. Once you go left, you are in the left subtree of a node. Every node in that left subtree is smaller than the node that you just turned left in (by the BST property). Thus, you'll never find a larger node by going into a left subtree.

Thus, you end up in the rightmost node, which has no right subtree (i.e., it's empty). That node has the largest value in the left subtree of pCurr.

There's an interesting property of pMax. The key value of pMax is the predecessor of pCurr. If you printed out the tree using inorder traversal, you'd discover that pMax would print out just before pCurr.

Right Standard Delete (successor delete)

We'll call the previous version of removing a node as: left standard delete. Alternately, it can be called predecessor delete (or left predecessor delete). The replacement node is the predecessor.

There is an alternative replacement node. Instead of picking the replacement node from the left subtree, you can pick the right subtree.

In particular, you want a node that's bigger than all the nodes in the left subtree. This is automatically satisfied by being a node in the right subtree. You also want to be the smaller than all other nodes in the right subtree. This node is pMin, the leftmost node in the right subtree.

This node also happens to be the successor of pCurr. That is, in an inorder traversal, you would see pCurr printed, then pMin immediately afterwards.

Everything mentioned with left standard delete can be done mirror-image with right standard delete.

What to Do: Part 1

You've found a replacement node pMax (or pMin). What do you do with it? There are two choices. pMax replaces pCurr, so you could ask the question, what node replaces pMax?

The answer to that question depends on whether pMax has a left subtree or not (we know it doesn't have a right subtree---why?). If it doesn't have a left subtree, then it's a leaf, and thus, you can simply set pMaxParent's right child to NULL, and be done with it.

If it has a left subtree and you're comfortable with recursion, then you can simply look for a replacement node for pMax in the left subtree (labeled L above) recursively. That is, you are finding a (different) pMax for pMax. Thus, you find a replacement node for the replacement node.

The recursion stops when the replacement node has no left subtree.

That's one solution, and a rather clever solution, and you can feel free to try it out, especially if you are confident with recursion.

However, there's a solution that doesn't involve recursion. That's the one we'll look at it.

We want to remove pMax from the left subtree. However, there's a catch. What do we do with pMax's left subtree (labeled 'L') above?

We can't leave this subtree dangling. We need to reattach it somewhere. This is where pMaxParent comes into play.

pMaxParent is just about to lose pMax as its right child, so it will have an empty right child. Thus, it can point to "L", the left subtree of pMax. After all, "L" was in the right subtree of pMaxParent and will still continue to be in the right subtree afterwards.

This is how the tree looks after you attach "L".

What to Do: Part 2

Next step. What do we do with pMax? We've done the first part: remove it from the pLeft subtree, and reattach pMax's left subtree as pMaxParent's right subtree.

What to do with pMax? There's two choices. You can copy the node and overwrite the value of pCurr. The reason for this is simple. pCurr has pointers pointing to it (most notably, pParent), and copying means not having to adjust those pointers.

But you have to be careful. When you copy a node, you copy everything (unless, you've defined operator=() in an unusual manner). That means, you copy the data and you copy the pointers from pMax.

Consider where pMax's left and right pointers were pointing. pMax's right pointer was NULL, so if you copy this over, then pCurr's right pointer is NULL, and you've lost pCurr's right subtree.

pMax's left pointer points to the "L" subtree. If you copy this to pCurr, then pCurr's left pointer will also point to "L", which will cause the "L" to have two pointers pointing to it (so you no longer have a tree).

In fact, you want to keep pCurr's left and right pointer the way it was before! You don't want to use pMax's left and right pointer.

This means, instead of copying the node, you must copy only the data. This turns out to be easy if you have a getData() method that returns a reference (if it doesn't you will need to do a little more work, in particular, you will need to copy the left and right pointers from pCurr to pMax, and then you can assign the entire node back to pCurr. This time, there's no problem with left/right pointers because pMax now has the same left/right pointers as pCurr's left/right pointers).

   pCurr->getData() = pMax->getData() ;

An Alternate Strategy

Instead of copying, you can actually replace pCurr by pMax. This means:

    pMax->setLeft( pLeft ) ;
    pMax->setRight( pRight ) ;
    pParent->setLeft( pMax ) ;  // careful! 

You need to be careful in the last step. While this is the "common" case, pCurr could be the right child of pParent, not necessarily its left child. The last statement really needs to be an "if" statement, determining which child pCurr is before attaching pMax.

This approach really replaces the node. This is slightly preferable because you get some practice with pointers, but either the overwrite method (copying pMax over pCurr) or the replacement method just described should work equally well.

Extreme Cases

It's deceptive to consider only the common case. There are a few extreme cases that don't fit the assumptions used in the common case.

In particular, consider the following exceptional cases. When considering these cases, ask yourself what the common case solution described does, and whether the common case solution actually does the right thing for the extreme cases. If so, you don't have to do anything!

Here are cases to consider:

• what if pParent is NULL? (that means, you are deleting the root)
• what if pRight is NULL, but not pLeft? (the common case still works)
• what if pLeft is NULL, but not pRight? (you can either look for pMin or make pParent point to pLeft. The second is slightly preferable, because it involves less code).
• What if "L" is empty? (Does common case solution still work?)
• What if pMax is the same as pLeft? (what happens to pMaxPar)?

Setting pointers

How do we get the values of all the pointers? First, declare them as local variables in the remove() method.

• pCurr and pParent. These are both found by calling locate().
• pLeft and pRight. Easy to assign once you have pCurr
• pMax and pMaxParent. You can write a loop to locate this, or you can use....locate(). Cleverly enough, you can set curr in locate() to pLeft and search for something (what?) which will set pMax and pMaxParent correctly. Declare local variables pMax and pMaxParent and pass it to locate() with the correct key value, and locate() magically does the work for you.

Single Subtree "Pullup"

There is an extreme case which can be handled simply. If pCurr has a single subtree, then let pParent point to the single subtree. It doesn't matter whether it's a left or right subtree. You are "pulling up" this subtree (i.e., the depth of all the nodes in the subtree decreases by one).

Easy Methods

We've described two ways to handle remove:

• left standard delete (predecessor delete). Use the predecessor as the replacement node.
• right standard delete (predecessor delete). Use the successor as the replacement node.

However, there is an "easier" method to remove a node, though it has some drawbacks.

Here is the picture of the tree after using "left easy delete".

In this version, pParent left will point to pLeft. Where will pRight go? We know that pRight has nodes whose key values are bigger than every node in the pLeft subtree. So, we must place this entire subtree to the right of the largest value in the left subtree, i.e., to the right of pMax.

It turns out this only requires adjusting two pointers. You don't even use pMaxParent.

Now you might wonder why we don't place the pRight subtree to the right of pParent. There are two reasons for this. First, and most obviously, it won't work! The pRight subtree was in the left subtree of pParent, so if you stick it in the right subtree, it violates the BST property.

The other reason is that you don't know that pParent doesn't have a right subtree. It could! And if you made this assignment, not only have you violated the BST property, you've also caused all the nodes in pParent's right subtree to be dropped off and thus created a memory leak.

Why use this method? It's easier to implement, adjusting fewer pointers.

Why avoid this method? It causes the tree to become unbalanced. In particular, every node in pRight has its depth increased by the distance from pMax to pLeft. Thus, searching in this subtree has now become more expensive. It's not a solution you see many textbooks covering for exactly this reason.

However, we leave it as an option if you are desperate. Hopefully, you won't be.

You should be able to figure out what "right easy delete" does.

Summary

There are four methods to remove a node.

• left standard delete
• right standard delete
• left "easy" delete
• right "easy" delete

In addition, there's the option of whether to use the "single subtree pullup" rule ALWAYS or only when the common case doesn't work on the single subtree (for example, common case works for right subtree empty in left standard, so there's no need to use single subtree pullup, if you don't want to).

All Are Trees are Different!

As you may know, you will be graded on your output, and this output may differ from one person to the next. How can we avoid havoc when grading your output?

First, realize that if you construct a tree only using add() operations, everyone should create the same tree. Second, all delete methods do the same thing when deleting a leaf---they ONLY delete the leaf. The remaining structure of the tree remains unchanged.

Finally, there are a few tricks one can use to ensure everyone gets the same tree, even when different students have implemented remove in their own way.

Web Accessibility