Introduction

Programming is many things to many people. As you become experienced as a programmer, the act of programming goes beyond simply getting the program to work. Many students who get to CMSC 214 can get a program to work. It might not be easy, it might not be pretty, but it can come close to working.

However, a good programmer often seeks a bigger goal than "getting it to work". Often, the way you approach a problem is to break it down into small tasks. Each small task is easy to understand, easy to debug, easy to read. It's amazing how such a wonderful idea is often underused.

The reason this happens, I believe, is due to a fear of writing functions. Yes, some people just don't like to write functions. Oh the hassle, they exclaim! You have to write a signature (prototype) into the header file, and you have to decide what parameters you need, and you have to comment it. Why not just write one large function, and avoid dealing with all those issues?

There are many reasons for avoiding this path to code bloat. Code is harder to read. Code is harder to debug. It also discourages you from thinking about a problem by breaking it into small tasks.

This is why locate() is such a wonderful function. First, it treats the problem of adding and removing a node as having a common starting point: locating the node.

Thus, adding a node consists of locating where the node should be added, then adjusting pointers to add the node. Removing a node consists of locating the node, and then removing it.

Notice that there's two things happening. First, both add and remove rely on the same locate() function. Second, each function, add and remove, can be thought of as having two distinct parts: locate() and the operation after the locate().

To think about how profound this idea is, think about the following: would you have used a locate() function if you hadn't been told to use it? It's not an idea that would come naturally to most people. In fact, few books that explain linked lists or binary trees even use a locate(). They believe the action of adding a node is, yes, locating the correct location and placing the node, but as one contiguous whole, not as two parts.

In fact, when I first saw locate(), I felt that it was an unnecessary function, and that there was no need to separate this function out. In fact, I just didn't think about adding a node in terms of a locate().

However, since then, I've liked the idea quite a lot for the reasons stated above. Plus, the idea of a locate() works in linked lists and binary search trees. It's nice when an idea works on more than one data structure.

Locating in a BST

The primary job of locate() is to locate a node. You want to determine whether a node is a data structure or not. If it's in a tree, you want a pointer to point to that node. But what happens if it's not in the tree? What should locate() do? It should still attempt to do something useful, so that a function like add() can proceed.

Let's look at a tree.

Suppose you want to locate 45. Since this is a binary search tree, you begin at the root. 45 is less than 50, so you go left to 40. 45 is greater than 40, so you go right. At this point, you've fallen off the tree (i.e., reached a NULL pointer).

What should locate() do? Should it return NULL? That's one possibility, but it makes much more sense to return a pointer to 40. Once you have a pointer to 40, then the add() function can attach a new node containing 45 as the right child of 40.

Thus, if locate() can't find the node in the BST, it should stop at the node just before it "fell off the tree". That's the most useful node that locate() can return.

The example above is quite important, because you should notice something about locate(). It stopped at node 40. 40 is NOT a leaf. locate() does not always find a leaf. It does, on the other hand, always find a node with zero or one child. It never finds a node with two children. If it stopped at a node with two children, then it wouldn't do its job locating the nodes (because it could always look down lower in the tree to find the node).

In the picture below, you see locate() set curr and also parent. parent is always set to curr's parent. The only time when this doesn't happen is when curr stops at the root. In that case, parent is set to NULL.

It's not that hard to implement locate() which sets curr and parent. You use the same technique to set parent as you do with prev when trying to use locate() in a singly linked list. You initialize parent to NULL, then set parent to curr and move curr.

Here's a version of locate() which uses loops.

// precondition: curr is at root (or root of a subtree), parent is NULL
bool BST::locate( int key, Node * & curr, Node * & parent )
{
   bool inTree = true ;
   while ( curr != NULL && curr->getData() != key && inTree )
     {
        if ( key < curr->getData() )
           if ( curr->getLeft() != NULL )
              {
                 parent = curr ;
                 curr = curr->getLeft() ;
              }
           else // about to fall off tree
              inTree = false ;
       else // key > curr->getData() 
           if ( curr->getRight() != NULL )
              {
                 parent = curr ;
                 curr = curr->getRight() ;
              }
           else // about to fall off tree
              inTree = false ;
     }
   return ( curr != NULL && curr->getData() == key ) ;           
}

An alternate way to locate()

There's a second way to locate(), which is simpler than the one posted above (it was suggested by Jason, the TA, and some of you probably noticed an easier version).

In this version,

• If key is in the tree, curr points to that node and parent points to curr's parent. (This part is the same as before)
• If key is NOT in the tree, then curr falls off the tree, and parent points to the node prior to falling off the tree. (This is different)

This makes the loop much simpler to write (although you will write a recursive version).

// precondition: curr is at root (or root of a subtree), parent is NULL
bool BST::locate( int key, Node * & curr, Node * & parent )
{
   while ( curr != NULL && curr->getData() != key )
     {
        parent = curr ; // parent trails curr 

        // Move curr left or right 
        if ( key < curr->getData() )
           curr = curr->getLeft() ;  // Move curr left
        else // key > curr->getData() 
           curr = curr->getRight() ; // Move curr right
      }
   return ( curr != NULL && curr->getData() == key ) ;           
}

This is much simpler, and you will probably want to base your recursion on this version.

Using parent for remove

parent isn't really necessary for add(). However, it becomes useful when you want to do remove(). That's a complicated enough topic that there's a separate tutorial for it. So read that one.

Web Accessibility