Note that the above is a hard deadline, even if you have grace time remaining.
In this lab, you will implement the remove operation on a binary
search tree, along with an array-based heap implementation complete with
enqueue and dequeue.
After completing this lab, you should:
You may work with a partner for this lab. If you choose a partner, both members must contribute to the same work. That is, you cannot simply divide the lab in half, as everyone is responsible for all the content. Instead, you should use a pair programming style. In pair programming, one person acts as a driver, who takes control of the keyboard. The other person acts as a navigator, who reviews what the driver writes and offers advice. Oftentimes, the driver is occupied with details of the problem (e.g., variables, control flow, etc.), whereas the navigator is concerned with bigger-picture problems (e.g., functions, design, interactions). This works well for problems which are simply too large to fit into one person's head. If you're unfamiliar with the concept of pair programming, you may wish to watch this video on the topic.
With pair programming, oftentimes it works best if both participants are of approximately the same skill level. Generally, if the disparity in skill is large, the end result is frustrating for both parties - it really only works when both parties operate at approximately the same speed. With this in mind, you should select someone of approximately the same skill level.
remove-bash-4.2$ cd -bash-4.2$ pwd /cs/student/yourusername -bash-4.2$ cd cs24 -bash-4.2$ pwd /cs/student/yourusername/cs24 -bash-4.2$ mkdir lab9 -bash-4.2$ cd lab9 -bash-4.2$ pwd /cs/student/yourusername/cs24/lab9
Now copy over the files for this week.
They are kept in the directory: /cs/student/kyledewey/cs24/labs/9
-bash-4.2$ cp /cs/student/kyledewey/cs24/labs/9/* .
Note that there is a '.' at the end of that line. cp means copy.
/cs/student/kyledewey/cs24/labs/9/* means all of the files contained
in the directory /cs/student/kyledewey/cs24/labs/9. The '.' means to
copy from that location to the current location.
Now check to make sure the copy worked correctly:
-bash-4.2$ ls
You should see a set of files listed that will be used for this lab.
In addition, you'll need to copy over your binary search tree implementation from the previous lab:
-bash-4.2$ cp ../lab8/BST.cpp .
BST.h
This lab comes with its own version of BST.h, which contains a signature
for the remove method. You'll need to update this files with any additional
signatures you introduced when you implemented your binary search trees last time.
Consult BST.h in the lab8 directory and copy over the signatures
you need.
remove
Implement the remove method in BST.cpp, using any of the techniques discussed
during week 8, lecture 2.
I personally recommend using the latter approach discussed, which is described
in the textbook and on Wikipedia (scroll
down to “Deleting”).
Once you have implemented, you should be able to compile and test like so:
-bash-4.2$ clang++ BST.cpp Node.cpp main_bst.cpp -bash-4.2$ ./a.out
You are encouraged to add your own tests to main_bst.cpp.
Right now it does some fairly simplistic testing, which should serve as good
scaffolding from which to build your own tests up.
enqueue
From this point forward, you will be working with Heap.cpp.
This file implements an array-based version of a heap, briefly mentioned
during week 8, lecture 2.
In this representation, each node lies at a particular index of an array.
You can determine where parents and children for particular nodes are
in the array by using parentIndex (which gets the index of
the parent node given a particular node's index),
leftNodeIndex (which gets the index of the left child given
a particular node's index),
and rightNodeIndex (which gets the index of the right child
given a particular node's index).
For example, parentIndex(5) will return the index of the parent
node for the node at index 5 in the array.
bubbleUp
The bubbleUp operation is called whenever an element is enqueued,
and is used to restore the heap property recursively up to the parents.
(Recall that the heap property holds for empty nodes and for nodes whose
children are less than or equal to the value at the particular node, and the
children themselves have the heap property).
In order to get enqueue working, you'll need a functioning
version of bubbleUp.
Go ahead and implement bubbleUp now. bubbleUp
should proceed upwards until either:
enqueue
Once you have bubbleUp implemented, you should be in good
shape to implement enqueue. enqueue should
first insert the new element to the next available position in the array,
and then call bubbleUp on the index where the insertion occurred
in order to restore the (now possibly violated) heap property. Once
the heap property is restored, this should simply return true.
If there are no more available positions in the array, then enqueue
should instead return false and not modify the array in any way.
Note that, unlike with binary search trees, we do allow duplicate elements to
appear in heaps. This means that as long as the underlying array has room to
spare, enqueue should always succeed and return true.
Once you have enqueue implemented, you can compile your code like so:
-bash-4.2$ clang++ Heap.cpp main_heap.cpp
The main_heap.cpp file contains a small test suite, which currently tests
both enqueue and dequeue. To test enqueue
independently, you will need to comment-out the portions of main_heap.cpp
which make calls to dequeue.
dequeuebubbleDown
The bubbleDown operation is called whenever an element is dequeued,
and is necessary to restore the heap property recursively down to the children.
In order to get dequeue working, you'll first need a functioning
version of bubbleDown.
Go ahead and implement bubbleDown now. Note that this is more
complex than bubbleUp. You must now look at both child nodes,
and proceed forward only if one of the children is greater than the node you're
currently observing. Additionally, if both children are greater, then you
must proceed down the greater child. Each time bubbleDown
is called, it should be preceeded by a swap operation involving
the current node and the child node of interest.
Keep in mind that near the bottom of the tree, it's feasible that a node
might have only a left child, or perhaps even no child nodes at all.
The easiest way to check this is to determine where the indecies for
these child nodes lie (via leftNodeIndex and rightNodeIndex),
and then checking that these indecies are less than the current number
of elements in the array (i.e., length). If an index is greater
than length, then this merely shows where the child would be,
had the node under observation had a child.
dequeue
Once you have bubbleDown implemented, you're ready to implement
dequeue. dequeue should first check if the heap is
empty, returning -1 if it is and not modifying the array in any way.
If the heap is not empty, then dequeue should:
swap the last heap element in the array
(Note - this isn't necessarily the last element in the array)
with the root node
lengthbubbleDown on the root node's index to restore the heap property
Once you have enqueue implemented, you can compile your code like so:
-bash-4.2$ clang++ Heap.cpp main_heap.cpp
If you commented-out tests in main_heap.cpp before to test enqueue,
you should uncomment these now and run the suite. It is strongly recommended to add in your
own tests to the suite.
First, fill out the required fields in the provided README.txt file.
Once you have filled this in, you may submit everything with the following command:
-bash-4.2$ turnin lab9@cs24 BST.h BST.cpp Heap.h Node.h main_bst.cpp Heap.cpp Node.cpp README.txt main_heap.cpp