CSCI 161 lab exercise 4: binary search trees

Lab exercise 4 is to be submitted electronically by 10a.m. Mar. 18th, and covers the work from the lab sessions of Mar. 4-6, and 11-13, suitably cleaned up to adhere to standards. The submission mechanism is detailed below, and must be followed to obtain credit for the lab.

The exercise will be marked out of 10, and is worth 5% of your total grade.

Late submissions will be penalized 2.5 marks per day late or part thereof.


Exercise details:

For lab exercise 4 you will be working with a binary search tree class (defined in BSTree.h)

You will be creating a file called BSTree.C, and in it you will implement the six protected binary search tree methods:

You will see that the public binary search tree methods have already been implemented inside BSTree.h, and each of them simply calls one of the protected methods that you are implementing.

The code below is available in files labex4.C, and BSTree.h
// BSTree.h
#ifndef BSTREE_H
#define BSTREE_H
#include <string>
using namespace std;

// ====================================================================
// ====== Binary search tree class ====================================

class BSTree {
   protected:
      // define the structure of internal tree nodes
      struct tNode {
         string key, value;
         tNode *left, *right;
      };

      // root will point to the root node of the tree
      tNode *root;

      // return the size of a subtree rooted at t
      int  getSize(tNode *t);

      // insert the key/value pair in the subtree t
      bool insert(string key, string value, tNode* &t);

      // lookup the key in the subtree t
      bool lookup(string key, string &value, tNode *t);

      // remove the specified item from subtree t
      bool remove(string key, string &value, tNode* &t);

      // print the contents of subtree t
      void printSubtree(tNode *t);

      // delete all nodes in the subtree t
      void deleteSubtree(tNode* &t);
      
   public:
      // the public routines are simply implemented with
      //     inline calls to the internal protected routines
      BSTree() 
         { root = NULL; }
     ~BSTree() 
         { deleteSubtree(root); }
      int  getSize() 
         { return getSize(root); }
      bool insert(string key, string value) 
         { return insert(key, value, root); }
      bool lookup(string key, string &value)
         { return lookup(key, value, root); }
      bool remove(string key, string &value)
         { return remove(key, value, root); }
      void printAll()
         { printSubtree(root); }
};

#endif
// labex4.C
#include "BSTree.h"
#include <iostream>
using namespace std;

// ====================================================================
// ====== Constants and data types ====================================

// enumerated type to list valid user commands
enum Command {
   HelpCmd    = 'H',    
   InsertCmd  = 'I',  
   LookupCmd  = 'L', 
   PrintCmd   = 'P',   
   QuitCmd    = 'Q',
   RemoveCmd  = 'R',
   SizeCmd    = 'S',
   InvalidCmd = '-'
};

// constant to specify maximum length of a line of text
const int MaxTextLen = 256;

// ====================================================================
// ====== Function prototypes =========================================

string getKey();
string getValue();
Command getCommand();
void processCommand(Command cmd, BSTree* s);
void printCommands();

// ====================================================================
// ====== Main routine ================================================

int main()
{
   // try creating a BSTree to store the data,
   // exit if unsuccessful
   BSTree *database = new BSTree;
   if (!database) {
      cout << "Exiting: unable to allocate storage" << endl;
      return 0;
   }

   // process user commands, updating the tree,
   // until the user decides to quit
   printCommands();
   Command cmd;
   do {
      cmd = getCommand();
      processCommand(cmd, database);
   } while (cmd != QuitCmd);

}

// ====================================================================
// ====== Function implementations ====================================

string getKey()
{
   char text[MaxTextLen];
   cout << "Enter the desired key value\n";
   cin.getline(text, MaxTextLen);
   string key = text;
   return key;
}

string getValue()
{
   char text[MaxTextLen];
   cout << "Enter the desired data value\n";
   cin.getline(text, MaxTextLen);
   string value = text;
   return value;
}

Command getCommand()
{
   char cmd;
   char junk[MaxTextLen];
   do {
      cout << "Enter a command" << endl;
      cin >> cmd;
      cin.getline(junk, MaxTextLen);
      switch (toupper(cmd)) {
         case HelpCmd:   return HelpCmd;
         case InsertCmd: return InsertCmd;
         case LookupCmd: return LookupCmd;
         case PrintCmd:  return PrintCmd;
         case QuitCmd:   return QuitCmd;
         case RemoveCmd: return RemoveCmd;
         case SizeCmd:   return SizeCmd;  
         default:
            cout << "Invalid command entered: " << cmd;
            cout << ", please try again" << endl;
            cmd = InvalidCmd;
            break;
      }
   } while (cmd == InvalidCmd);
   return (Command)(cmd);
}

void printCommands()
{
   cout << "Enter " << (char)(HelpCmd) 
        << " for help" << endl;
   cout << "   or " << (char)(InsertCmd) 
        << " to insert a new key/value pair" << endl;
   cout << "   or " << (char)(LookupCmd) 
        << " to lookup the value associate with a key" << endl;
   cout << "   or " << (char)(PrintCmd)  
        << " to print all the key/value pairs" << endl;
   cout << "   or " << (char)(RemoveCmd)
        << " to remove a key/value pair" << endl;
   cout << "   or " << (char)(SizeCmd)
        << " to lookup how many key/value pairs are stored" << endl;
   cout << "   or " << (char)(QuitCmd)  
        << " to quit" << endl;
}

void processCommand(Command cmd, BSTree* s)
{
   if (!s) {
      cout << "Cannot process an uninitialized database" << endl;
      return;
   }
   string key, value;
   switch (cmd) {
      case HelpCmd:
         printCommands();
         break;
      case InsertCmd:
         key = getKey();
         value = getValue();
         if (s->insert(key, value)) {
            cout << "Inserted (" << key << "," << value << ")\n";
         } else {
            cout << "Unable to insert (" << key << "," << value << ")\n";
         }
         break;
      case LookupCmd:
         key = getKey();
         if (s->lookup(key, value)) {
            cout << "Looked up (" << key << "," << value << ")\n";
         } else {
            cout << "Unable to lookup (" << key << ")\n";
         }
         break;
      case PrintCmd:
         cout << "Current database contents:\n";
         s->printAll();
         break;
      case QuitCmd:
         cout << "Bye!\n";
         break;
      case RemoveCmd:
         key = getKey();
         if (s->remove(key, value)) {
            cout << "Removed (" << key << "," << value << ")\n";
         } else {
            cout << "Unable to find (" << key << ") to remove\n";
         }
         break;
      case SizeCmd:
         cout << "There are " << s->getSize();
         cout << " key/value pairs currently stored\n";
         break;
      default:
         cout << "Invalid command supplied, please try again\n";
         break;
   }
}



Recommended development sequence As always, I advise you follow a well-thought out sequence of development steps in completing the exercise.

    PHASE 0 setup the files

  1. Copy labex4.C and BSTree.h to your labex4 directory.

  2. Create a file called BSTree.C and make sure it #include's "BSTree.h"

    PHASE I insert and print

  3. The two basics you'll need to figure out if anything else works are the ability to put things in the tree and to print the tree contents. As such, get insert and printSubtree working first.

    PHASE II searches

  4. The lookup routine is the next most useful, and relatively simple to implement.

    PHASE III the rest

  5. The getSize and deleteSubtree routines are relatively independent of one another, so can be implemented in any order you prefer.

  6. The remove routine is perhaps the most convoluted, so I would recommend tackling it last. When you do tackle it, I would recommend adding and testing the functionality in stages:

    PHASE IV testing

  7. Testing is a bit more involved, as you need to be sure the various routines are correct when they need to operate on a root node, when they need to operate in the left vs right subtrees, when they are operating on leaf nodes, etc.


Submission mechanism

All the code for the BSTree methods must be in file BSTree.C
(correct spelling and capitalization is essential for the submission to work correctly).

To submit the assignment, cd to the directory that contains your BSTree.C file and type the following command:

   /home/faculty/wesselsd/bin/submit  161  BSTree.C
Note that each submission overwrites any previous submission you have made.


Marking guidelines:

Marks will be based on:

Code standards:

The submission must follow the code standards for labex3,