Previous Section
 < Free Open Study > 
Next Section


8.6 Iterative Insertion and Deletion

Searching a Binary Search Tree

In the recursive versions of the tree operations, we embedded the search task within the function that needed it. The other alternative is to have a general search function; let's take that approach here. The function FindNode receives a pointer to a binary search tree and an item with the key initialized. It sends back a pointer to the desired node (nodePtr) and a pointer to the node's parent (parentPtr) if an item with a matching key is found.

What do we do if no item has a key that matches item's, as is the case when we are inserting a new element? We set nodePtr to NULL. In this case, parentPtr points to the node into which the new element must be inserted as a right or left child. One other case arises: What if we find a matching key in the root node? Because no parent node exists, we set parentPtr to NULL.

Here is the specification for the internal tree function, FindNode:

Let's look at the search algorithm in detail. We use nodePtr and parentPtr (the outgoing parameters) to search the tree. Because we access the tree through its root, we initialize nodePtr to the external pointer, tree. We initialize parentPtr to NULL. We compare item and nodePtr->info. If the keys are equal, we have found the desired node. If item's key is less, we look in the left subtree; if item's key is greater, we look in the right subtree. This operation is exactly like a recursive search except that we change pointer values to move left and right rather than making recursive calls.

When does the loop terminate? Two terminating conditions are possible. First, we stop searching if we find the correct node. In this case, nodePtr points to the node containing the same key as item's, and parentPtr points to this node's parent. Second, if no element in the tree has the same key as item's, we search until we fall out of the tree. At this point, nodePtr = NULL, and parentPtr points to the node that would be the item's parent-if it existed in the tree. (We use this value of parentPtr when we insert an item into a tree.) The resulting loop condition is

while (nodePtr != NULL && !found)

The algorithm illustrates that the maximum number of comparisons in a binary search tree equals the height of the tree. As discussed earlier, this number may range from log2N to N (where N is the number of tree elements), depending on the shape of the tree.

The complete function follows.

Void FindNode(TreeNode* tree, ItemType item,
     TreeNode*& nodePtr, TreeNode*& parentPtr)
// Post: If a node is found with the same key as item's, then
// nodePtr points to that node and parentPtr points to its
// parent node. If the root node has the same key as item's,
// parentPtr is NULL. If no node has the same key, then
// nodePtr is NULL and parentPtr points to the node in the
// tree that is the logical parent of item.

{
  nodePtr = tree;
  parentPtr = NULL;
  bool found = false;
  while (nodePtr != NULL && !found)
  {
    if (item < nodePtr->info)
    {
      parentPtr = nodePtr;
      nodePtr = nodePtr->left;
    }
    else if (item > nodePtr->info)
    {
      parentPtr = nodePtr;
      nodePtr = nodePtr->right;
    }
    else
      found = true;
  }
}

Let's trace this function, using the tree in Figure 8.6 on page 471. We want to find the element with the key 18. nodePtr is initially set to tree, the external pointer. Because item's key (18) is greater than nodePtr->info (17), we advance the pointers. Now parentPtr points to the root node and we move nodePtr to the right; it then points to the node with the key 20. Because item's key (18) is less than this key (20), we advance the pointers. Now parentPtr points to the node with the key 20, and we move nodePtr to the left; nodePtr then points to the node with the key 18. Now 18 is equal to nodePtr-> info and found is true, so we stop looping. We exit the function with nodePtr pointing to the node with the desired key and parentPtr pointing to this node's parent.

Next, let's look at an example where the key is not found in the tree. We want to find the element with the key 7. nodePtr is initially set to tree. Because item's key (7) is less than nodePtr->info (17), we move to the left. Now nodePtr points to the node containing 9 and parentPtr points to the root node. Because item's key is less than nodePtr->info, we move again to the left. Now nodePtr - NULL; it has fallen out of the tree. Because no more is left to search in this subtree, we stop looping. We exit the function with nodePtr equal to NULL and parentPtr pointing to the node with the key 9. If we were calling FindNode with the intention of subsequently inserting a node with the key 7, we would now know two things:

  1. Because nodePtr = NULL, the tree does not include a node with the key 7.

  2. Because parentPtr points to the last node visited before we fell out of the tree, the new node, with a key value of 7, must be attached to the node at parentPtr. This information will prove very helpful when we develop the iterative InsertItem operation.

The Function InsertItem

The algorithm for the iterative InsertItem operation must carry out the same three tasks that any insert operation performs:

Creating a node works in the same way as in the recursive version. Finding the insertion point and inserting the node are different, however. Let's see how the function FindNode can perform the search for us. We call FindNode, asking it to find the node with the same key as item's:

FindNode(tree, item, nodePtr, parentPtr);

Suppose we want to insert an element with the key value 13 into the binary search tree pictured in Figure 8.18. In the function FindNode, nodePtr is initialized to point to the root of the tree, and parentPtr is initialized to NULL (Figure 8.18a). Because item's key (13) is larger than the key of the root node (7), we move nodePtr to the right, dragging parentPtr along behind it (Figure 8.18b). Now item's key is less than nodePtr->info, so we move nodePtr to the left, with parentPtr following (Figure 8.18c). Because item's key is greater than nodePtr->info, parentPtr catches up and nodePtr moves to the right (Figure 8.18d). At this point, nodePtr is NULL, so we exit FindNode with the pointers positioned as shown in Figure 8.18(d).

Click To expand
Figure 8.18: Using the function FindNode to find the insertion point

Of course, a node with item's key is not supposed to be found, for we are just now inserting its node. The good news is that nodePtr has fallen out of the tree just at the spot where the new node should be inserted. Because parentPtr trails immediately behind nodePtr, we can simply attach the new node to the node pointed to by parentPtr (Figure 8.18e).

Now we're ready for the third task: to fix the pointers in the node pointed to by parentPtr so as to attach the new node. In the general case, we compare the key of the new element to the key of parentPtr->info. Either parentPtr->left or parentPtr->right must be set to point to the new node:

When we are inserting the first node into an empty tree, however, parentPtr still equals NULL and dereferencing parentPtr is illegal. We need to make inserting the first node into the tree become a special case. We can test for parentPtr = NULL to determine whether the tree is empty; if so, we change tree to point to the new node.

Taken together, the pieces of the insertion operation design can be coded as the function InsertItem, with the interface described in the Binary Search Tree ADT specification.

void TreeType::InsertItem(ItemType item)
// Post: item is in tree.
{
  TreeNode* newNode;
  TreeNode* nodePtr;
  TreeNode* parentPtr;
  newNode = new TreeNode;
  newNode->info = item;
  newNode->left = NULL;
  newNode->right = NULL:

  FindNode(root, item, nodePtr, parentPtr);

  if (parentPtr == NULL)         // Insert as root.
    root = newNode;
  else if (item < parentPtr->info)
    parentPtr->left = newNode;
  else parentPtr->right = newNode;
}

The Function DeleteItem

The same three cases exist for the iterative DeleteItem operation that existed for the recursive Delete: deleting a node with no children, one child, or two children. We can use FindNode to locate the node (pointed to by nodePtr) to delete and its parent node (pointed to by parentPtr).

The actual deletion in the recursive version occurs in DeleteNode. Can we use it to delete the node pointed to by nodePtr? DeleteNode takes only one parameter, the place in the tree where the pointer to the node to be deleted resides. We can use the DeleteNode function developed for the recursive version if we can determine the place in the structure to pass to DeleteNode. That is, given nodePtr and parentPtr, we must determine whether the node pointed to by nodePtr is the right or left child of the node pointed to by parentPtr. If the value of nodePtr is the same as the value of parentPtr->left, then we pass parentPtr->left to DeleteNode; otherwise, we pass parentPtr->right.

void TreeType::DeleteItem(ItemType item)
// Post: There is no node in the tree whose info member
//       matches item.
{
  TreeNode* nodePtr;
  TreeNode* parentPtr;

  FindNode(root, item, nodePtr, parentPtr);

  if (nodePtr == root)
    DeleteNode(root);
  else
    if (parentPtr->left == nodePtr)
      DeleteNode(parentPtr->left);
    else DeleteNode(parentPtr->right);
}

It is very important to recognize the difference between passing nodePtr to DeleteNode and passing either parentPtr->right or parentPtr->left. See Figures 8.19 and 8.20.

Click To expand
Figure 8.19: Pointers nodePtr and parentPtr are external to the tree
Click To expand
Figure 8.20: Pointer parentPtr is external to the tree, but parentPtr-> left is an actual pointer in the tree

Test Plan

Because we use the Binary Search Tree ADT to represent items in a list, we can employ the same strategy that we have used to test the other list ADTs for it. However, testing the traversals is much more difficult than testing a simple linear traversal. The tree in Figure 8.17 is a good tree to use as a test because we already have the answers. We need to insert the items, retrieve items found and not found in the tree, print the tree, reset the tree for each traversal, use GetNextItem to get each of the items in each traversal, delete all the items, and call each of the other functions where appropriate.

On the Web, the program TreeDr.cpp contains the driver for the test. The recursive version of TreeType is located in file TreeType.cpp; the iterative version is found in file ITreeType.cpp. The input file is TreeType.in and the output files are TreeType.out and TreeType.screen for the recursive version and ITreeType.out and ITreeType.screen for the iterative version.

Recursion or Iteration?

Now that we have looked at both the recursive and the iterative versions of inserting and deleting nodes, can we determine which approach is better? In Chapter 7, we gave some guidelines for determining when recursion is appropriate. Let's apply these guidelines to the use of recursion with binary search trees.

Is the depth of recursion relatively shallow?

Yes. The depth of recursion depends on the height of the tree. If the tree is well balanced (relatively short and bushy, not tall and stringy), the depth of recursion is closer to O(log2N) than to O(N).

Is the recursive solution shorter or clearer than the nonrecursive version?

Yes. The recursive solutions are certainly shorter than the combination of the non-recursive functions plus the supporting function FindNode. Is it clearer? Once you accept that in every recursive execution, the parameter tree is actually a pointer member within a node of the tree, the recursive version becomes intuitively obvious.

Is the recursive version much less efficient than the nonrecursive version?

No. Both the recursive and the nonrecursive versions of inserting and deleting are O(log2N) operations, assuming a well-balanced tree. The only efficiency issue of concern relates to space, item is a value parameter; our functions pass a copy of it on each recursive call. If item is a large struct or class object, these copies may cause an overflow of the run-time stack. (It would be better to make item be a const reference parameter if ItemType is large and the tree has great height.)

We give the recursive versions of the functions an "A"; they represent a good use of recursion.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)