Read Drozdek, Chapter 6 and make sure you understand the basic properties of binary search trees. In this assignment you will implement the basic "insert" and "find" operations, as well as the iterator pattern, using concepts from the C++ Standard Template Library.
Assuming you have successfully completed part 1, you will have your repository that contains the provided code for this assignment. In it you will find the following files:
BST.hpp BSTIterator.hpp BSTNode.hpp Makefile test_BST.cpp
You will modify the three *.hpp files, providing
full definitions of member functions marked with // TODO,
and turn them in. In completing the implementation, you shouldn't remove
anything from those files (except the // TODO comments!).
If design considerations dictate it, you can add
additional functions or variables, but they should be in a
private: section, indicating that those additions are
part of the implementation, and not part of
the public or protected interface to these classes.
The test_BST.cpp file is a simple C++ application which
partially tests some aspects of the BST class. You should
add code here, in order to test your program as thoroughly as you can (We will
test it as thoroughly as we can when grading it!).
The Makefile is provided for your convenience. Running
make in the directory will compile the
test_BST.cpp application, creating an executable named
bst which can be run from the command line.
Modify this Makefile as needed, or create your own,
to support your development process.
Of course, it is possible that the provided
Makefile works perfectly fine for your purposes, and won’t need to be
changed.
Your first task is to understand the code. Do not attempt to start writing code until you have a firm grasp of what the provided code does and what you are supposed to do with it. Nearly all the required functionality is specified in the code and the comments, so you'll need to read everything carefully. Unlike in previous classes (such as certain offerings of CSE8A and 8B) we are not providing a lot of scaffolding to walk you through what this code does, outside of what we have already provided in class. This is a gateway course, and in the upper division you will at times be given vague assignment specifications and expected to make sense of them. We've tried to provide some guidance, but not as much as you may have received in previous classes. We also encourage test-driven development here. Make sure you can understand the provided test file, and then add your own tests before you start implementing any code of your own.
If you have any questions about the assignment, please come to the lab during tutor hours, visit a TA during their office hours, or post on the discussion forum. Tutor and TA hours are posted on the main course website.
If you do not understand what you are doing, you will not learn anything from this assignment and the whole point of it will be lost. We are happy to help, but you must seek this help. And START EARLY. Read the code RIGHT NOW!
October 17 @ 11:00 PM
This means your solution to the assignment must be turned in by the due deadline. The turn-in procedure is described below in the section Turning in your assignment. It is highly recommended that you start this assignment immediately; terminals and tutors can get very busy at the last minute. The files that contain your solution to the assignment must be turned in by the due deadline. NO EXCEPTIONS! You may develop your code anywhere, but you must ensure it compiles and runs correctly on ieng6, because that’s where we’ll be testing it.
In doing this assignment, it's your responsibility to understand the course rules for integrity of scholarship.
You must follow these steps to acquire the starter code and prepare for the assignment. Do not directly copy files from any directory that you find on ieng6, as may have been the procedure in previous offerings of this course!
Instead, see Using Gitlab for the proper steps.
The bst.hpp file will be used to maintain the binary search tree structure and functionality.
In the bst.hpp file, you will notice the line template<typename Data> preceding
the class BST { (the start of the class definition). This may be something you have never
seen before and is referred to as a template class. Templates in C++ are a powerful feature allowing you to
define a pattern which the compiler can turn into actual code, essentially allowing the class to work with
generic types. REMEMBER: A template is a pattern, not the actual implementation. At compile time, the compiler
will translate the pattern into actual code for each unique type used with the pattern. A BST that holds doubles
and a BST that holds integers will result in two separate BST classes, one for each type. Without features like
templates, one would have to create a new class for each data type to be stored in the BST manually.
The word Data following typename is the type identifier. When reviewing
the source code, you will see Data used everywhere the object type to be stored in or retrieved
from the BST is referred to.
Note: Since the BST class is a template class, instantiation requires some special notation. The compiler
needs to know the type to be used with the object being created. Creating an instance of the BST template
class is done as follows: class_name<data_type> identifier. For example, to create an
instance of a BST class that will hold integers, you would type the following: BST<int> myIntBst;
When reviewing the code, you will notice the following in several places: std::pair<iterator, bool>.
The :: characters separating std and pair is known as a scope resolution operator. In C++, the
functionality that is part of the standard template library is defined inside the std namespace.
Doing some searching on C++ scope resolution operator will provide plenty of information on its usage.
Returning to std::pair<iterator, bool>, this is an example of a C++ template class, except that
it supports two unique types, unlike the BST which only supports one. For template classes having support for
multiple types, separate them with a comma. The pair, defined in the std namespace, is
defined inside the utility header (part of the standard template library). For more information on the pair
class, see: C++ std::pair.
What you need to know for this assignment is that a pair object is created via std::make_pair and
its members are referred to as first and second. For example, if you created a pair named myPair, then to refer
to the first and/or second values, you would type myPair.first and myPair.second, respectively. Note, if myPair was a
pointer, you would use myPair->first and myPair->second instead.
Another part of the source code needing some explanation is virtual ~BST(). C++ is not a managed
programming language like Java, Python, C#, etc. In other words, it does not have a garbage collector responsible
for cleaning up resources. This means YOU are the garbage collector. To facilitate this, C++ introduces
the destructor. Note: the virtual keyword is not part of the destructor. For this assignment,
virtual serves no purpose. When an object created on the stack goes out of scope, the destructor
is automatically invoked. However, when an object is created on the heap with the new keyword, the memory must
be freed with the delete keyword. Not only will delete free the memory used, but it will also
invoke the destructor. In this area of the code, you will be responsible for deleting each of the nodes
created and stored in the tree. Nodes will be explained in the bstnode.hpp section.
The bstiterator.hpp file shall be responsible for providing forward iteration from any point in the BST.
Note: Concepts already discussed in the other sections will not be mentioned again. If anything was not explained, it was probably covered in a previous section.
The first part of the source code to note: class BSTIterator : public std::iterator<std::input_iterator_tag,Data> {.
C++ supports private, protected, and public inheritance. For understanding the differences, see:
C++ class inheritance. The main area of
interest is the access permissions of subclasses. Essentially, this line is sub-classing from the
std::iterator class defined in the C++ standard template library.
See: std::iterator.
Sub-classing from std::iterator ensures we do this in a way common with built-in C++ containers.
Also see: Input Iterator.
When looking at the functions defined in this file, you will see operator++() and operator++(int), which overload the pre-increment and post-increment operators respectively.
C++ supports operator overloading, allowing the programmer to define the behavior of operators such as pre- and
post-increment. Note the int parameter in the second version above. The function does not require an int as
an argument, this is the convention used to differentiate between pre- and post-increment. The support for operator overloading
essentially allows the programmer to type ++myObject instead of myObject.increment().
Another feature of C++ exposed in this file is the friend keyword. Any class or function defined
as a friend of a class has access to ALL the non-public members of the class. Since classes BST and
BSTNode are defined as friends of class BSTIterator, they have access to the private constructor and instance
variables. This sort of design allows the friend classes to create iterator objects, but no one else.
The bstnode.hpp file shall be responsible for holding the value to be stored in the tree along with a link to its parent and children nodes.
Note: Concepts already discussed in the other sections will not be mentioned again. If anything was not explained, it was probably covered in a previous section.
From lecture and the reading, it should be clear that a BST is a special type of tree that maintains a well-defined ordering property, allowing for fast searches. It is this ordering property that enables efficient support for the successor method -- which you will be implementing. A sound understanding of this ordering property is necessary to correctly implement the successor method.
Much of this class should be self-explanatory by now, however, one part needs a mention, which will be useful
in testing your program. Near the end of the file you will see the following template function:
std::ostream & operator<<(std::ostream& stm, const BSTNode<Data> &n). This is a helper
function designed to allow the details of a node to be printed using the stream extraction operator
<<. It's usage is as follows. Assume a BSTNode<int> object exists whose
identifier is myNode. To print the properties of this node to standard output, you would do the following:
std::cout << myNode.
The test_bst.cpp file provides a starting test suite for validating your binary search tree's correctness. It is by no means exhaustive and you should add additional functionality to this file to further test your program. Review the contents to see what tests are being performed and how they are implemented. This should help you identify what has not been tested and what functionality needs additional testing.
Note: Concepts already discussed in the other sections will not be mentioned again. If anything was not explained, it was probably covered in a previous section.
When writing your assignment, generally, it's best to first implement the general cases. For example, when implementing the insert operation for your BST, start with the assumption that a root node already exists and begin the insert logic. You can even have your constructor initially create a root node. Once you have this logic working, then consider the special logic that might be needed for the initial insertion of a node. Think about the possible situations under which insert can be called. For example, a new tree with zero elements, a tree with only one element, a tree with a root and left child only, and a tree with a root and right child only. Anything else is just another case of the above.
Probably the most tricky parts of this assignment will be implementing the destructor in the BST class and the successor function in the BSTNode class. As mentioned earlier, C++ does not manage resources for you. This mean you will have to delete each node that you created and attached to the tree in the destructor. It is suggested that you work this logic out on paper first. Think about how you can traverse a tree deleting nodes as you go. Once you solve this problem, implementing the destructor becomes easy. Work this out on paper with example trees. Think about the different tree shapes you can encounter and make sure your logic works regardless.
Equally complex is the successor method. Again, you should draw several trees on paper, thinking about where the successor node would exist given a certain position in the tree. As an example, draw a tree inserting the following nodes in this order { 100, 50, 75 }. Given you are currently looking at 75, who is the successor? How would you navigate to that node (100) in this case. Create more trees with differing shapes considering all the possible logic that is needed given the position of a node in the tree. Remember, you don't need to get too complicated. In most cases, a tree with 5-7 nodes will present all the different shapes. Trees with more nodes are really just more instances of the same problem.
Tip: Keep your code as simple as possible. Many a times the recursive algorithm is much easier to implement than the iterative one. Also, it's usually easier to read and debug.
While many of you may be inclined to perform a quick online search for a specific compiler error or the usage of a C++ feature, this will not be helpful in the long run. It might be faster to search stack overflow for an answer, but you should really learn how to utilize and read technical documentation. You will not truly learn how certain parts of the C++ standard template library are intended to be used any other way. In addition, reading this documentation will help YOU write better technical documentation and comments in your code.
For starters, you should always have a copy of the C++ operator precedence table available when you are programming. Not only does this help you understand how expressions are evaluated, but it will prevent you from cluttering your code with unnecessary parenthesis. See: C++ Operator Precedence. Also, a great resource for what is available in the standard template library and how to properly use these resources is available here: cppreferene.com.
Before searching online for your problem, take a moment to look at the error, review your code and logic, and be a visual debugger. You will learn more about compiler errors and what they mean by doing this. Another very useful tip is to intentionally do something in code incorrectly and then try to compile it. Study the compiler errors for something you know is wrong. This way you know how the compiler is informing you of the problem.
When you have completed the assignment, you must submit it. You will do this by pushing your changes to GitLab. Follow these steps, also go through the git instructions link provided in the Part 1 of this lab (above):
’git status’ to see what files have been
changed.
’git add <files>’ to stage certain files for a commit, use
’git add .’ to add all files in the working directory to the
commit (hopefully you will not be doing this at this late stage—all files
should already be in your repository!)
’git commit -m "FINAL SUBMISSION"’ to commit the changes to
your repository and indicate that you are done and this is your final
submission.
’git push origin
master’ Don’t forget this push! You must do this to get credit.
Some points to keep in mind:
There are 25 possible points on the assignment. If your solution files do not compile and link error-free, you will receive 0 points for this assignment. We will compile and test your program using the g++ compiler and runtime environment on ieng6. To get full credit, style and comments count.