CS35: Data Structures and Algorithms

Lab 6: Binary Search Trees

Due on Wednesday, April 3 at 11:59 PM. This is a team lab. You and your assigned lab partner(s) will complete this lab together. Make sure that you are familiar with the Partner Etiquette guidelines. You may discuss the concepts of this lab with other classmates, but you may not share your code with anyone other than course staff and your lab partner(s). Do not look at solutions written by students other than your team. If your team needs help, please post on the Piazza forum or contact the instructor or ninjas. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.

We will be using Teammaker to form teams. You can log in to that site to indicate your preferred partner. Once you and your partner have specified each other, a GitHub repository will be created for your team. If you have any trouble using Teammaker, contact your instructor.

Overview

For this lab, you will implement the binary search tree (BST) data structure. You will then write a series of unit tests to confirm that your data structure works correctly. (You may additionally use the provided word-counting program to evaluate your BST.)

Starting Code

Your starting code can be found in the appropriate repository for your team. The following is a description of the repository’s initial contents; bolded files are those which you must change in completing the lab.

Part I: Implementing Binary Search Trees

Example BST

Most of the work of this lab is implementing the binary search tree. Your implementation is spread across two files: linkedBST-inl.h (which contains the implementation of the LinkedBST class’s methods) and linkedBSTNode-private-inl.h (which contains private helper functions for those methods to use). The LinkedBST class is a template class with two templated type names: K (the type of the keys in the BST) and V (the type of the values). The LinkedBST class itself tracks only two pieces of data:

A single node stores information about its key, its value, and its left and right children. If a node does not have a child, then the corresponding pointer variable will be set to nullptr.

Many of the methods in the binary search tree are natural to implement recursively. For this reason, you will write a collection of recursive helper functions for your LinkedBST methods to call. For instance, the height of a node is equal to one more than the largest of the heights of its two children. Many of the public methods of LinkedBST will be single-line calls to the private recursive functions to begin the operation at the BST’s root node.

The vector STL Class

The vector<T> class, found in the vector library, is the C++ STL implementation of an array list. It is used somewhat differently from our List<T> interface. Here’s a handy translation guide:

Operation List code vector code
Insert at front myList.insertFirst(value) no simple equivalent
Insert at back myList.insertLast(value) myVector.push_back(value)
Determine size myList.getSize() myVector.size()
Get element by index myList.get(index) myVector[index]
Set element by index no equivalent myVector[index] = value
Remove from back myList.removeLast() myVector.pop_back()

One other difference is that the pop_back method is void; you must retrieve the last element yourself if you want to see that element before it is removed.

The primary reason that we introduce vector for this lab is because vectors can also be copied just like pairs. Consider the following code:

List<int>* listPointer1 = new STLList<int>(); // create a pointer to a new List
List<int>* listPointer2 = listPointer1;  // copy the pointer
listPointer1->insertLast(4);           // add an element
cout << listPointer2->getSize() << endl; // prints 1; they point to the same List
List<int> list1;                         // create a statically-allocated list
List<int> list2 = list1;                 // illegal! Lists doesn't know how to copy themselves!

vector<int> vector1;                     // create a statically-allocated
vector1.push_back(4);
vector1.push_back(6);
vector<int> vector2 = vector1;           // vectors do know how to copy themselves
cout << vector2.size() << endl;          // prints 2 (since both elements were copied)
vector1[0] = 2;                          // assigns 2 to the first position of vector 1
cout << vector2[0] << endl;              // prints 4; vector 2 is a different vector

Some methods of the BST ADT interface use vector to prevent you from having to worry about memory management (e.g. delete) for the values they return.

Testing the Binary Search Tree

In addition to implementing the LinkedBST class and the helper methods, you must also write unit tests. To get you started, some of the tests in tests.cpp have been completed for you. You should write many more tests. At a minimum, you should write a test for each “TODO” comment that has been provided. You must write one test for each of these comments that tests the appropriate method or function in a non-trivial way. For the recursive functions, you must provide at least one test that utilizes recursion; for BST methods, you must provide a test that operates on a tree of height greater than one. For example, consider the following test:

TEST(negativeHeight) {
    LinkedBST<int,string>* tree = new LinkedBST<int,string>();
    CHECK_EQUAL(-1, tree->getHeight());
}

If you were required to write a test for getHeight, this test, alone, would not suffice; it does not trigger recursion within the getHeightInSubtree helper function. That is, you will probably need to write multiple test cases for each method you are testing. You are encouraged to include the above test (and other tests like it) in your lab submission. Make sure that each of the functions and methods has at least one non-trivial test.

Please remember that these tests are a development tool as well as a lab requirement. You should write these tests as soon as possible and use them to help you find bugs and verify the correctness of your code. You should even consider writing the tests before you write your implementation just so you can make certain that you know what you expect your code to do. Also note that we have provided you with an implemented checkInvariants method. Use this throughout your tests to verify that the BST is the proper size and satisfies the BST property (i.e., don’t just test it once; use it to help test the other methods).

Remember to test the corner cases like empty trees, trees with only left-children, operations on the root node and on leaf nodes, etc. A good development approach is to write some code in manualTests to figure out what’s happening in your BST, and then later copying that code into a new test in tests.cpp once you figure out what you output you want to get from it.

Implementation Strategy

Blueprints
Source: OpenClipArt.org

This lab involves writing more code than previous labs, so it is useful to plan an approach to your work. Below is a strategy which should organize your efforts; you are not required to proceed in this order, but it might help.

  1. In linkedBST-inl.h, implement the non-recursive methods: the constructor, getSize, and isEmpty. Compile and test your code. You should now pass the emptyTree test in the tests.cpp file.

  2. Next work on implementing the recursive methods. Note that most methods within linkedBST-inl.h will be quite brief, making a call to a recursive helper method within linkendBST-private-inl.h to do most of the work. Start with insert, which should call insertInSubtree. Once you have implemented these two methods successfully, you will pass more of the initial tests provided in the tests.cpp file.

  3. Now you should be able to get into a nice rhythm:
    • In tests.cpp, go to the next TODO and add some tests for that method.
    • In linkedBST-inl.h, implement the public method.
    • In linkedBST-private-inl.h, implement the private helper method associated with the public one.
    • Compile, test, and debug until you’ve successfully passed those tests.
    • Rinse and repeat!
  4. Debug any memory leaks as described below.

Once you are finished, you should be able to compile and run the word counting program:

make wordcount
./wordcount testFile

For your convenience, a few text documents have been provided in the test_data directory.

Memory

For this lab, your program is required to run without memory errors or leaks. You should use valgrind as you proceed in your testing to track memory errors. When you have a complete first draft of your implementation:

Coding Style Requirements

You are required to observe good coding practices. You have seen these requirements many times, and should know them by now. If you’re unsure, check previous labs where the style requirements were stated explicitly.

Summary of Requirements

When you are finished, you should have

When you are finished with your lab, please fill out the post-lab survey. You should do this independently of your partner.