CSCI 161 Summer 2023: lab 5

161 Lab 5 exercises

See the main lab page for submission deadlines and late penalties.

It is assumed you are keeping up to date with the lectures and labs.

The focus for this lab is on the implementation of a variety of class features (inheritance, copy and move constructors, operator overloading) using a binary search tree class derived from a basic tree class.

The sequence for obtaining the lab will be much the same as previous labs, and the commands are briefly summaried below (see the lab1 discussion for explanations and any troubleshooting needed):

ssh -x csci fork csci161/lab5 csci161/$USER/lab5
cd csci161
git clone csci:csci161/$USER/lab5
cd lab5

Repository contents

The repository contains the usual makefile (this time to build executable lab5x) and readme, plus a collection of three pairs of .h/.cpp files:

tree.h/.cpp:
This contains the definition of a basic tree class (in the .h) and the implementation of its methods (in the .cpp).
Both of these files are already completed.
bstree.h/.cpp:
The .h file contains the definition of a binary search tree class derived from the tree class, while the .cpp file is currently empty.
Your task for the lab is to implement all the bstree methods, putting the implementations in this file.
lab5.h/.cpp:
The .h file contains the definition of two functions used by the main routine, while the .cpp files contains the main routine itself and the implementations of the two functions.
Both of these files are already completed.

The base tree class

The basic tree class provides:

the definition for a tree node struct (with pointers for left/right children and string data fields to represent a key and a value)
a public constructor for an empty tree
a public destructor for a tree
a public print method (doing an inorder traversal of the tree)
a protected pointer for the root of the tree (null when the tree is empty)
a protected recursive print routine (used by the public one)
a protected recursive deallocate routine (used by the destructor)

The base tree class is already complete and should not be altered.

The main routine

The lab5x main routine is set up to exercise the various binary search tree methods we are implementing.

The data we are storing/accessing is a collection of key value pairs, where both the keys and values are strings. The idea is that a user can store a variety of keys, each having a unique value associated with it (e.g. a user might be storing colours as the keys and their RGB values as the associated values, or storing usernames as keys and the users' passwords as the associated values).

Currently the main routine declres a variety of bstree variables, uses the supplied fillTree function to fill one of them with user data, then tests out the various bstree methods (the copy and move constructors, the overloaded = operator, the search method, the print method, etc).

The main routine and supporting functions are already complete and should not be altered.

The bstree definition

The bstree.h provides the definition for a bstree class derived from the basic tree class, with a variety of public and private methods.

The bstree is for a binary search tree of key,value pairs (both strings) where the tree is organized based on the keys following our usual binary search tree rules: smaller values go in the left subtree, larger values go in the right subtree.

(Note: the < == and > operators have been overloaded for the string class, so you can use them normally to compare keys.)

In this tree we won't allow duplicate keys: if someone tries to insert a new key,value pair and that key is already in the tree then we'll treat it as if they want to update the value for that key, not generate a new additional pair.

#pragma once

#include "tree.h"

// tree represents a binary search tree of key-value pairs
//    keys and values are both strings)
class bstree: public tree {
   public:
       bstree(); // constructor for empty tree
      ~bstree(); // destructor (delete all tree nodes)
      string lookup(string k);  // searches tree for the specified key k,
                                // returns the associated string, returns "NOT FOUND"
                                // if no such key is found
      void insert(string k, string v); // if a node with key k already exists then insert
                                       //    replaces its associated value with v,
                                       // otherwise inserts a new node with the given key/value
      bstree(const bstree& orig); // copy constructor
      bstree(bstree&& orig); // move constructor
      bstree& operator=(const bstree& rhs); // overload the assignment operator (makes deep copy)

   private:

      tnode* lookup(string k, tnode* t);  // searches subtree t for a node whose key matches k
                                          // and returns a pointer to the node (if found)
                                          // or nullptr (if no such node is found)
      void insert(string k, string v, tnode* &t); // performs insert within subtree t

      void copy(tnode* &t, tnode* origt); // make t a deep copy of subtree origt

};

The bstree.h file is already complete and should not be altered.

The bstree method implementations (your task)

The bstree.cpp file is intended to include all the bstree method implementations and needs to be completed by you.
(Initially it is nearly empty, consisting of just the #include.)

Details and recommended approaches for the various methods are discussed below:

The public methods:

the default constructor
This is meant to initialize the tree as empty, but since that is done correctly by the base tree's constructor we don't actually need to do anything inside this constructor.
the destructor
This is meant to deallocate the tree, but as that is taken care of by the base tree's destructor we don't actually need to do anything inside this destructor.
the lookup method
This is meant to search the tree for the given key, k, and return its associated value (if found) or the string "NOT FOUND" (if no such key is found).
Much of the work can be passed along to the private lookup routine, which expects to be given a key and a pointer to the top node of a subtree to search. The private routine returns nullptr if the desired key is not found, otherwise it returns a pointer to the node containing the key.
Thus we can call the private lookup, passing k and the root and storing the returned value in a tnode* pointer.
If the private lookup returned null then the lookup failed and we can return "NOT FOUND", otherwise we can use the pointer to lookup and return the actual value field.
the insert method
Much like with the lookup, we can pass most of the work along to the private version of insert.
The private insert expects to be given a key, value, and a pointer to the node at the top of the subtree to insert into, thus we can simply call the private insert, passing along the k and v values and the tree root.
the copy constructor
Again, most of the work can be passed along to a private method, this time the copy method.
We can simply call the private copy method, passing along the root of the current tree and orig's root.
the move constructor
For the move constructor we want to set the our tree's root to point to the same place as orig's root, and once that is done we can set orig's root to null. (Thus our current tree is now the only one pointing to the stored tnodes, and we have effectively moved the storage from orig to our tree.)
the overloaded = operator
Since we're already creating a private copy method to help the copy constructor, we can call that same function here (again passing our root and rhs's root).
Once we've done the copy we also need to return the current tree, done by dereferencing the implicit "this" pointer as discussed in lectures:
return *this;
The private methods: much of the heavy lifting is done within these methods, each of which takes an extra tnode* parameter representing the top node in the portion of the tree we're currently working on.
the insert method
This method is meant to recursively search down through the tree, going to the left or right as appropriate for our binary search tree rules, and eventually either (a) update the value associated with k if that key is already in the tree, or (b) create and insert a new node into the tree, giving the new node key k and value v.
If t is null then we've reached the location where we need to insert the new node, so:
- allocate a new tnode and make t point to it
  (remember to use nothrow and error check in case new returns null)
- set t's key to k (e.g. t->key = k), t's value to v, and t's left and right to null
If t isn't null then we need to compare t's key to the key, k, we're trying to insert:
- if they're equal then v is a replacement for the current value associated with k, so set t's value to v
- if k is less than t's key then we need to call insert recursively, passing k, v, and t's left
- if k is greater than t's key then we need to call insert recursively, passing k, v, and t's right
the the lookup method
For this method we're again searching down through the tree, looking for a node with key k and going left/right following the rules of our search tree (smaller keys down the left side, larger keys down the right side).
If we find a node whose key matches k then we return a pointer to the node, but if we reach the bottom of the tree (a null node) without finding a match then we return null.
Thus our algorithm can essentially be:
- if t is null then return null
- otherwise if t's key matches k then return t
- otherwise if k is less than t's key then call recursively passing k and t's left
- otherwise call recursively passing k and t's right
the copy method
This method assumes we're creating a full duplicate of an existing tree of tnodes, and so we're passed two pointers: one for a node t in the new copy (passed by reference so we can change it), the other for the corresponding node in the original, origt.
If origt is null then we can simply set t to null, but otherwise we want to do a full copy:
- use new (with nothrow and doing error checking) to allocate a new tnode and make t point to it
- copy the left child of origt to the left child of t by making a recursive call, e.g. copy(t->left, origt->left)
- do similarly to copy the right child of origt to the right child of t
- copy origt's key and value to t's key and value

Sample run
A sample run showing what main does and the output produced, with some notes added explaining what's happening where.
(User input has also been highlighted in bold italics for clarity.)


 user enters some initial key/value pairs for tree T1, DONE when done 
Enter a key (single word) or the word DONE (all caps) if you're finished 
me 
Enter a value (single word)  to go with key me 
mnop 
Inserted new node me:mnop 
Enter a key (single word) or the word DONE (all caps) if you're finished 
whoever 
Enter a value (single word)  to go with key whoever 
bbb 
Inserted new node whoever:bbb 
Enter a key (single word) or the word DONE (all caps) if you're finished 
anyone 
Enter a value (single word)  to go with key anyone 
blahblah 
Inserted new node anyone:blahblah 
Enter a key (single word) or the word DONE (all caps) if you're finished 
someone 
Enter a value (single word)  to go with key someone 
xyz 
Inserted new node someone:xyz 
Enter a key (single word) or the word DONE (all caps) if you're finished 
who 
Enter a value (single word)  to go with key who 
abc 
Inserted new node who:abc 
Enter a key (single word) or the word DONE (all caps) if you're finished 
DONE 

 program tries the move constructor to move T1 content into T2 then prints both
Running move constructor 

The original tree content (should be empty) is: 
The tree is currently empty 

The content of the tree we've moved it into is: 
The current tree contents are: 
anyone:blahblah 
me:mnop 
someone:xyz 
who:abc 
whoever:bbb 

 program tries the copy constructor to copy T2 to T3 and prints T3 
Running copy constructor 

The content of a copy of the second tree is: 
The current tree contents are: 
anyone:blahblah 
me:mnop 
someone:xyz 
who:abc 
whoever:bbb 

 user enters additional key/value pairs to add to T3
Enter a key (single word) or the word DONE (all caps) if you're finished 
anyone 
Enter a value (single word)  to go with key anyone 
notblah 
Updated node anyone's value to notblah 
Enter a key (single word) or the word DONE (all caps) if you're finished 
foo 
Enter a value (single word)  to go with key foo 
moreblah 
Inserted new node foo:moreblah 
Enter a key (single word) or the word DONE (all caps) if you're finished 
DONE 

 program shows contents of T3 and T2 
The content of the modified copy is now: 
The current tree contents are: 
anyone:notblah 
foo:moreblah 
me:mnop 
someone:xyz 
who:abc 
whoever:bbb 

The content of the second tree (should be unchanged by the modifications to the copy) is: 
The current tree contents are: 
anyone:blahblah 
me:mnop 
someone:xyz 
who:abc 
whoever:bbb 

 program tries T4 = T3 then prints T4 to check overloaded = operator 
Running copy constructor 
The content of the copy made using = is: 
The current tree contents are: 
anyone:notblah 
foo:moreblah 
me:mnop 
someone:xyz 
who:abc 
whoever:bbb 

 program gets user to search for a key in T4 
Enter the key you would like to search for 
someone 
The search result for key someone is:  
   xyz 
T3 and T4 are identical in content and structure 
T2 and T3 differ 

 program ends, all the destructors run 

Deallocating tree 
Deleting node foo:moreblah 
Deleting node anyone:notblah 
Deleting node who:abc 
Deleting node someone:xyz 
Deleting node whoever:bbb 
Deleting node me:mnop 
Deallocation complete 

Deallocating tree 
Deleting node foo:moreblah 
Deleting node anyone:notblah 
Deleting node who:abc 
Deleting node someone:xyz 
Deleting node whoever:bbb 
Deleting node me:mnop 
Deallocation complete 

Deallocating tree 
Deleting node anyone:blahblah 
Deleting node who:abc 
Deleting node someone:xyz 
Deleting node whoever:bbb 
Deleting node me:mnop 
Deallocation complete 

Deallocating tree 
Deallocation complete