Section 2 - Binary Search Tree Completed

4B.2.1 Finding a Node

picWe have actually implemented a find algorithm implicitly in both of our prior methods, insert() and remove(). The recursive step, where we went left or right down the tree, was the basic idea of find. However, we might like a find() that does not actually do anything to the tree other than return the Comparable object found.

Once we have a Comparable find(Comparable &x) that returns the object found, we can add a trivial encapsulation of it viz-a-viz a bool contains(Comparable &x) which returns a bool (true or false), stating whether or not x is in the tree. Often, contains() is all we need.

considering an int tree, find() seems superfluous. After all, why not just provide contains()? If I want to know if 6 is in the tree, and contains(6) tells me, "yes it is", why do I need the actual "found 6"? I have the "searched-for 6" already, and both 6s are identical. The answer to this question has to do with non-primitive data. Normally, we have a tree that contains user-defined objects, and we are looking for an object that has a particular search key (say a social security number). What we want, then, is the entire object (the Employee or iTunesEntry) because that has other information we will need to look a

The actual use of this find() will require first building an empty object around the search key, and then passing that object to find(). find() will then return the one that was in the tree with the same search key.

As usual, find() is a pair of public/private overloads. here is the public one:

template <class Comparable>
const Comparable &FHsearch_tree<Comparable>::find(
   const Comparable &x) const
{ 
   FHs_treeNode<Comparable> *resultNode;
   
   resultNode = find(mRoot, x);
   if (resultNode == NULL)
      throw NotFoundException();
    return resultNode->data;
}

As you see, we are going to throw an exception if the object is not found, since otherwise we would have to decide on some sort of default "not-found" object to return. That's not to say we could not do it: we might have returned the same object passed in from the client in the case of a not-found condition, and let the client test the returned object to see if it was the same as what it passed in (not-found) or different (found). But this is too demanding. A simple try/catch can be used by the client to do the same thing. NotFoundException() is a bare user-defined exception in our FHsearch_tree class.

Now the private version:

template <class Comparable>
FHs_treeNode<Comparable>* FHsearch_tree<Comparable>::find(
   FHs_treeNode<Comparable> *root, const Comparable &x) const
{
   if (root == NULL)
      return NULL;

   if (x < root->data)
      return find(root->lftChild, x);
   if (root->data < x)
      return find(root->rtChild, x);
   return root;
}

By now you should be getting very comfortable with this same recursion which we have seen five or six times.

As promised, we have our trivial contains() that uses the private find():

  bool contains(const Comparable &x) const 
     { return find(mRoot, x) != NULL; }

It is an interesting exercise to see if you can implement either insert() or remove() more simply by having either call find(). You can't. In fact, even if you add extra machinery to find() to have it return a putative parent of a not-found node, it still does not help simplify insert() or remove(). We have find() because it is useful in its own right, not because it makes other methods easier to implement.

4B.2.2 An Alternative find()

It might seem awkward to build an object at the client level containing the key field that we are searching for, just so we can call find(). It would be more natural to search the tree by simply passing the value for the key field. For example, if I were looking for a StarNearEarth object whose CNS name was "GJ 244", then rather than constructing a dummy object and mutating the name to "GJ 244", all in preparation for calling find(), wouldn't it be nice to just pass "GJ 244" to find, directly, and get back the object?

   sought_star = find("GJ 244");

Details aside, this is a perfectly reasonable thing to want, and even more reasonable to provide to our client as an option. It takes a little work though, and we won't be doing that just yet. Briefly, we'll need a few things to make this happen:

  1. We'd need a second type parameter to your tree template that tells the template what the key field type is. In the example just given, that would be string. So, when we created a tree, we might do it like this: FHsearch_tree<StarNearEarth, string> star_map;
  2. We must call the static method setSortType() on the underlying class, so that our "key field" is properly established. We have to be careful to make sure that whatever type we pass as the key field type, it is the same type of the key field selected in setSortType().
  3. We must make sure that the < operator is defined for the key field we have established. This, however, is already part of item 2, above, because of how we have written setSortType() to work with the < operator.
  4. We have to throw an exception in case there is no object found.

All of this is child's play, but we are busy with other things at the moment, so we'll table the effort. In a week or two, however, you'll have the opportunity to do this in another data structure called a quadratic-probing hash table, when you provide a find() that works on key value, rather than a pre-built object.

4B.2.3 Testing FHsearch_tree

Most of the remaining methods are not worth discussing since you have already seen how they work in earlier lessons. Here, I'll show you the full public interface of FHsearch_tree minus the externally implemented definitions:

template <class Comparable>
class FHsearch_tree
{
protected:
   int mSize;
   FHs_treeNode<Comparable> *mRoot;

public:
   FHsearch_tree() { mSize = 0; mRoot = NULL; }
   FHsearch_tree(const FHsearch_tree &rhs) 
      { mRoot = NULL; mSize = 0; *this = rhs; }
   ~FHsearch_tree() { clear(); }

   const Comparable &findMin() const;
   const Comparable &findMax() const;
   const Comparable &find(const Comparable &x) const;

   bool empty() const { return (mSize == 0); }
   int size() const { return mSize; }
   void clear() { makeEmpty(mRoot); }
   const FHsearch_tree & operator=(const FHsearch_tree &rhs);

   bool insert(const Comparable &x);
   bool remove(const Comparable &x);
   bool contains(const Comparable &x) const { return find(mRoot, x) != NULL; }

   template <class Processor>
   void traverse(Processor func) const { traverse(mRoot, func); }
   int showHeight() const { return findHeight(mRoot); }

protected:
   FHs_treeNode<Comparable> *clone( FHs_treeNode<Comparable> *root) const;
   FHs_treeNode<Comparable> *findMin(FHs_treeNode<Comparable> *root) const;
   FHs_treeNode<Comparable> *findMax(FHs_treeNode<Comparable> *root) const;
   FHs_treeNode<Comparable> *find(FHs_treeNode<Comparable> *root,
      const Comparable &x) const;
   bool insert(FHs_treeNode<Comparable> * &root,
      const Comparable &x);
   bool remove(FHs_treeNode<Comparable> * &root, const Comparable &x);
   void makeEmpty(FHs_treeNode<Comparable> * &subtreeToDelete);
   template <class Processor>
   void traverse(FHs_treeNode<Comparable> *treeNode, 
      Processor func, int level = 0) const;
   int findHeight(FHs_treeNode<Comparable> *treeNode, int height = 0) const;
   
public:
   // for exception throwing
   class EmptyTreeException {};
   class NotFoundException {};
};

Next, we show a little main() which tests our BST generic.

// FHsearch_tree main
// CS 2C, Foothill College, Michael Loceff, creator

#include <iostream>
#include <string>
using namespace std;
#include "FHsearch_tree.h"

template <typename Object>
class PrintObject
{
public:
   void operator()(Object obj)
   {
      cout << obj << " ";
   }
};

int main()
{
   int k;
   FHsearch_tree<int> searchTree;
   PrintObject<int> intPrinter;

   searchTree.traverse(intPrinter);

   cout << "initial size: " << searchTree.size() << endl;
   searchTree.insert(50);
   searchTree.insert(20);
   searchTree.insert(30);
   searchTree.insert(70);
   searchTree.insert(10);
   searchTree.insert(60);
   cout << "new size: " << searchTree.size() << endl;
   cout << "traversal: \n";
   searchTree.traverse(intPrinter);

   FHsearch_tree<int> search_tree2 = searchTree;

   cout << "\n\nAttempting 100 removals: \n";
   for (k = 100; k > 0; k--)
      if (searchTree.remove(k))
         cout << "removed " << k << endl;

   cout << "\nsearch_tree after deletes:\n";
   searchTree.traverse(intPrinter);

   cout << "\nsearch_tree2 after deletes:\n";
   search_tree2.traverse(intPrinter);
   cout << endl;

   cout << (search_tree2.contains(30)? "30 found\n" : "30 not found\n");
   cout << (search_tree2.contains(65)? "65 found\n" : "65 not found\n");

   return 0;
}

/* ------------------ RUN -------------
initial size: 0
new size: 6
traversal:
10 20 30 50 60 70

Attempting 100 removals:
removed 70
removed 60
removed 50
removed 30
removed 20
removed 10

searchTree after deletes:

search_tree2 after deletes:
10 20 30 50 60 70
30 found
65 not found
Press any key to continue . . .
-------------------------------------------- */