Lab 08 - BST (11/01/2021)

---

Binary Search Tree

To find a node in a binary tree:

1. if node is NULL, return false.
2. if node.value == value, return true.
3. if value < node.value, return search(node.left, value).
4. if value > node.value, return search(node.right, value).

Node Removal

To remove a node with value of data from a binary tree:

1. if node is NULL, return false.
2. if data < node.data return delete(node.left, data).
3. if data > node.data return delete(node.right, data).
4. exchange node.data with (in-order) predecessor.data.
5. return delete(node.data, data).

Deep vs. Shallow Copy

The Gang of Three rule states that if a class defines one (or more) of the following, it should probably explicitly define all three:

1. Destructor – call the destructors of all the object's class-type members.
2. Copy constructor – create new object members from corresponding member constructors.
3. Copy assignment operator – assign corresponding members from existing members.

Default constructors, destructors, and assignment operators do shallow copies. You need to explicitly create user constructors, destructor, and assignment operators when a deep copy is needed (class contains pointers to dynamically allocated resources).

• The copy constructor is called when a new object is created from an existing object, as a copy of the existing object. Such is the case when passing an object as an argument to a function (by value) or returning an object (by value) from a function:

  MyClass t1, t2;       // default constructor
  MyClass t3 = t1;      // copy constructor (t3 is new)

• The assignment operator is called when an already initialized object is assigned a new value from another existing object.

  t2 = t1;              // assignment operator (t2 exists)
  t2.operator=(t1);     // assignment operator (equivalent)

• A deep destructor is needed if a class contains pointers to dynamically allocated resources. Otherwise a memory leak occurs.

Note: You will need a deep copy constructor, destructor, and assignment operator to use your BST in an ordered set implementation.

Destructor

Destructors contain code that is run whenever an object is destroyed. Each class has a default destructor, which effectively invokes the destructor for each data field. If the object references a dynamically allocated object, the memory allocated to that object must be freed.

Be sure to add a deep destructor to your BST class to avoid memory leaks.

Copy Constructor

We want a copy of an object to be an independent copy, which means we should be able to modify one of the objects without affecting the other. Copying of primitive types is straightforward—the values are duplicated and placed in the target locations. Without a deep copy constructor, destructing an object that was shallow copied would run the destructor twice on the same object (once for the original and once for the copy) - a source for trouble!

For class types, copying is done by a class's copy constructor:

MyClass(const MyClass& other);

The copy constructor is invoked automatically:

• when an object is passed to a function by value.
• when an object is returned from a function.
• when an object is initialized with another object of the same class.
• when the compiler generates a temporary object.

Be sure to add a deep copy constructor to your BST class.

Copy Assignment Operator

The assignment operator (operator=) is called when an already initialized object is assigned a new value from another existing object. For class types, the assignment operator signature looks like:

MyClass& operator=(const MyClass& other);

Every class has a default assignment operator which makes a copy of each source data field and places it into the corresponding data field of the target. The default assignment operator makes a shallow copy of an object, so we must override it if we want truly independent copies.

Be sure to add a deep assignment operator to your BST class.

BST Iterator

Iterators open the door for expression, readability, maintenance and reusability. How do I create a custom iterator?

• First, you have to decide how to define the state of your iterator and how to define begin and end conditions.
• Then, you have to decide what the contents of the iterator will be. In other words, you have to decide on the value type, when the iterator is dereferenced.

How many functions must a custom iterator implement?

• Iterators should have a constructor and destructor.
• Iterators should be comparable. (When have I reached the end of the container items?)
• Iterators should dereference to a data item.
• Iterators should increment (and decrement if possible).
• Iterators should be instantiable with begin() and end() functions.

Iterates are generally implemented as a nested class. Nesting a class within another class does not give special access privileges to member functions of the nested class. Similarly, member functions of the enclosing class have no special access to members of the nested class.

An outline of the BST class with an iterator could look like:

#include "BSTInterface.h"
template<typename T>
class BST : public BSTInterface<T>
{
private:
   struct Node { ... };
   Node* root_;
public:
   BST() { this->root_ = NULL; }
   ~BST() { clearTree(); }
   /** BST iterator */
   class Iterator
   {
   private:
      // private iterator state...
      Node* root_;
   public:
      Iterator(Node* root) : root_(root),... {}
      ~Iterator() {}
      bool operator!=(const Iterator& rhs) const { ... }
      Iterator operator++(T) { ... }
      T operator*() const { ... }
   };
   Iterator begin() const { ... }
   Iterator end() const { ... }
};

The BST iterators may be used as follows:

if (item1 == "find")
{
   BST<int>::Iterator iter = intBST->begin();
   BST<int>::Iterator end_iter = intBST->end();
   while (iter != end_iter)
   {
      if (*iter == stoi(item2))
      {
         out << "found";
         break;
      }
      ++iter;
   }
   if (iter == end_iter) out << "not found";
}
else if (item1 == "tree")
{
   out << endl << "iterate: ";
   BST<int>::Iterator iter = bst.begin();
   BST<int>::Iterator end_iter = bst.end();
   if (iter == end_iter) out << " empty";
   for (; iter != end_iter; iter++)
        out << " " << *iter;
}

Lab Requirements:

1. The BST class must publicly inherit from the BSTInterface template interface class.
2. Use commands from the input file to add (add {node}), remove (remove {node}), clear (Clear), and output tree in level-order (print).
3. Report results of add, remove, and clear commands with OK if successful or Error if command failed. Also report "empty" when outputting an empty tree.
4. There are multiple correct methods for removing nodes from a tree, which may result in different trees. When removing nodes, use the method described on page 476 of the course text (i.e. when removing a node with only one child, replace that node with its child and use the in-order predecessor when removing nodes with two children).
5. Remember to disallow adding duplicate entries and removing nodes not in the tree. (Both cases are reported as Error.)
6. NO STL CONTAINERS MAY BE USED IN THIS LAB!

7. The following summarizes the commands used in the BST lab:

COMMAND	DESCRIPTION	OUTPUT
INT	Instantiates a BST object for subsequent commands.	OK
STRING	Instantiates a BST object for subsequent commands.	OK
add <data>	Add data node to BST. Return Error if duplicate.	OK
remove <data>	Remove node from BST.	OK
clear	Delete all nodes from the BST.	OK
size	Output the number of nodes in the BST.	Number of BST nodes
print	Print BST (using insertion operator) in level-order. Return empty if BST contains no elements.	Level-order listing of BST empty
find <data>	Find node in BST. Return "found" or "not found".	found not found
copy	Make a deep copy of the current BST.	OK
printcopy	Print the deep BST copy (created by the copy command) in level-order.	Level-order listing of BST empty
tree	Output the in-order contents of the BST using begin() and end() iterators with iterator operators ++, *, and !=.	In-order listing of BST empty

NOTE: Return "Error" on all commands except "INT" and "STRING" if no BST has been instantiated.

Steps to Success._(collapse)

Note: Code examples come from readily available, public websites (ie., stackoverflow.com, cplusplus.com, etc.)

Online BST Visualization._(collapse)

Level Order Traversal of a BST._(collapse)

Understanding Valgrind Output._(collapse)

Instructions for submitting your lab:

• Zip all your lab source files (.cpp, .hpp, .h) into one folder. DO NOT INCLUDE YOUR WHOLE PROJECT!
• Submit your zipped lab source using the "Labs" tab on the class website.
• Your submitted lab source will be compiled and executed using a lab gcc compiler.
• Both input and output files will be specified by command line arguments.
• An auto-grader will compare your output files with expected results and you will shortly receive an accumulative score.
• The auto-grade process may abort on the first error. If so, correct the error and try again.
• You may re-submit your zipped source as many times as you like.

While you are encouraged to develop your own test cases, you may use the following input and resulting output files in testing the BST lab.

	Input File	Output File
Test #1	lab08_in_01.txt	lab08_out_01.txt
Test #2	lab08_in_02.txt	lab08_out_02.txt
Test #3	lab08_in_03.txt	lab08_out_03.txt
Test #4	lab08_in_04.txt	lab08_out_04.txt
Test #5	lab08_in_05.txt	lab08_out_05.txt
Test #6	lab08_in_06.txt	lab08_out_06.txt

The auto-grader will be expecting to find in your output file the following sections:

Fail	Pass	Auto-graded Section Requirements (50 + 10 points)	Score = 0
		BST commands "INT" and "STRING" set the BST template type mode to int and string respectively. BST command "add" adds an int or string element to the BST. (Attempt to add a duplicate node outputs "Error".) BST command "print" outputs the BST in level order. (If the BST is empty, "empty" is output.) (lab08_in_01.txt)	15 points
		BST commands "size" and "clear" are correctly implemented for types int and string. (lab08_in_02.txt)	5 points
		Nodes are correctly removed from the BST using the "remove" command. (Attempt to remove a non-existent node outputs "Error".) (lab08_in_03.txt)	10 points
		The BST "find" command outputs "found" if the value is in the BST and "not found" if the node is not found. (lab08_in_04.txt)	10 points
		The BST "copy" command makes a deep copy of the current BST and outputs "OK". BST command "printcopy" outputs the deep BST copy in level order. (If the BST is empty, "empty" is output.) (lab08_in_05.txt)	10 points
		BONUS: The "tree" command displays the tree nodes in in-order using BST iterators instaniated by begin() and end() functions as well as iterator operators ++, +, and !=. (If the BST is empty, "empty" is output.) (lab08_in_06.txt)	10 points +2 w/Peer Review
		Memory leaks, g++ compiler warnings, array out-of-bounds, or use of STL container detected.	-10 points

 

The lab source will be peer reviewed using the following rubric:

No	Partial	Yes	Peer Review	Score = 0
			A BST class is derived from the abstract BSTInterface interface class.
			All classes (including the iterator) have public toString and friend insertion member functions. The insertion operator function is used to send the contents of the BST container and iterators to the output stream.
			BONUS: The bonus "tree" command is implemented using an iterator implemented as a BST inner class with ++, *, and != operators. The BST class has public begin() and end() functions that return instantiated iterators.
			Header Files #define header guards used to prevent multiple inclusion in all .h files. (No "#pragma once" directives.) Class member functions of 10 or less lines of code are implemented in the function declaration. Member functions of more than 10 lines of code are implemented outside the class declaration (.h or .cpp file.) No global variable or object definitions (instantiations) in .h files.
			Objects and Classes Upper CamelCase (or Underscore_Case) class names. Member functions that don't mutate data members declared const. All class data members and helper functions private (getter's and setters's for private data members only as needed.) All derived classes have public toString and friend insertion member functions.
			Functions and Variables Descriptive lower camelCase (or underscore_case) function and variable names. Constant and #define names all capital letters. "Reasonable" documentation (pre- and post- conditions) precede function declarations / definitions.
			Program Format One statement per line. Consistent usage of braces with 3 or 4 space indention per scope. One space around binary operators and other appropriate items. "Reasonable" comments used to document program flow.
Overall Rating			Easy to follow, readable, organized, and well commented.  Excellent       Good       Average       Poor
***NOTE: Any attempt to circumvent any lab requirement (ie, hard coding output, using loops instead of iterators where required, modifying a class interface, etc.) will be reported by peer reviewers and result in a zero score for the lab.