BINARY SEARCH TREES Solution

Description

The Bag Class with a Binary Search Tree, adapted from Michael Main’s version

 

The Assignment:

Implement the BSTreeBag template class, using a binary search tree to store the items.

 

Purposes:

Ensure that you understand and can use binary search trees and recursive algorithms for processing them.

 

Before Starting:

Read this handout and the Trees chapter (pp. 507-535) in Carrano.

 

Due Dates:

Part 1:  Constructors, destructor, operator=, size required in lab due Saturday, Nov 16, 8 am.

Insert, count functions: 2% bonus if you finish and turn this in by Saturday, Nov 16, 8

am.

Part 2:  The rest of the work, including insert and count: due Saturday, Nov 23, 8 am. Files that you must write:

BSTTreeBag.h: Header file for this version of the BSTreeBag class. You don’t have to write much of this file unless you add helper functions. Just copy our version and add your name and other information at the top.

 

BSTreeBag.cxx: The implementation file for the new BSTreeBag class.  This time, you must write this from scratch—though your labs next week will help.

 

Other files that you may find helpful:

 

bintree.h and bintree.cxx. These define the binary tree node template class.  You don’t have to write anything for these.  NOTE: This version of the binary tree node template has the return values from the non-const versions of the left() and right() functions return a reference to the pointer in the node. This is indicated by the & symbol for them in bintree.h and bintree.cxx:

 

binary_tree_node*& left( )

 

The use of a “reference return type” (indicated by the ampersand) in the return value has two advantages that simplify the material. It now allows a direct assignment such as: p->left() = NULL. This is not a huge advantage, since the same thing can be accomplished by using the set_left function.

 

The expression p->left() can be passed as the argument to a function such as: tree_clear(p-

>left()); The parameter of tree_clear is a reference parameter, so that any changes that tree_clear makes to p->left() will now affect the actual left pointer in the binary_tree_node<ItemType>* p. In this example, the tree_clear function does set its

 

parameter to NULL, so that the total effect of tree_clear(p->left()) is to clear the left subtree of

p and to set p ‘s left pointer to NULL.

 

In the case of tree_clear, this is not a huge advantage because we could have just set p‘s left pointer to NULL ourselves. But, in this assignment, there are two functions, bst_remove and bst_remove_max, which are easier to write if we can use root_ptr->left() and root_ptr-

>right() as the parameters of recursive calls. See my implementations in BSTreeBag.h for details.

 

BSTreeBagTest.cxx: A simple interactive test program.

BSTreeBagExam.cxx: A non-interactive test program that will be used to grade the correctness of your bag class.

Makefile: for compiling the assignment.

 

The Bag Class Using a Binary Search Tree

Discussion of the Assignment

 

This assignment is another template class.  I am giving you the code for bintree.h and bintree.cxx, which define a template class for the binary_tree_node. Use these files, but do not change them. You’ll

see the specification for the whole basic bintree class in bintree.h: We begin by making a namespace for

your class (the test code has to say

 

using hw6;

 

to use binary_tree_nodes without having to say hw6::binary_tree_node all the time.)

 

namespace hw6

{

 

template <class ItemType>    // bag holds any ItemType class binary_tree_node       // class name

{

public:

 

// TYPEDEF

typedef ItemType value_type; // comparable ItemTypes typedef unsigned int size_type;

 

// CONSTRUCTOR         // if data was not supplied,

// it gets initialized here.

binary_tree_node(

const ItemType& init_data = ItemType( ),

binary_tree_node* init_left = NULL, binary_tree_node* init_right = NULL

)

{

data_field = init_data;

left_field = init_left;

right_field = init_right;

}

 

// MODIFICATION MEMBER FUNCTIONS ItemType& data( ) { return data_field; }

 

binary_tree_node*& left( ) { return left_field; }

binary_tree_node*& right( ) { return right_field; }

 

// CONST MEMBER FUNCTIONS

const ItemType& data( ) const { return data_field; }

const binary_tree_node* left( ) const

{ return left_field; }

const binary_tree_node* right( ) const

{ return right_field; }

bool is_leaf( ) const

{ return (left_field == NULL) &&

(right_field == NULL); }

 

Next come your private member variables for your state as a node in a binary tree:

 

private:

ItemType data_field;

binary_tree_node *left_field;

binary_tree_node *right_field;

};

 

Last come the nonmember functions for making trees from these binary tree nodes.

 

The first 3 do tree traversals (remember there are 3 orderings) and pass in a Process as a function to be done on every element on the tree (now we are passing functions like they’re data, mind you).  I didn’t actually use these functions for this homework, but they’re here if you want them.

 

// NON-MEMBER FUNCTIONS for the binary_tree_node<ItemType>:

template <class Process, class BTNode>

void inorder(Process f, BTNode* node_ptr);

 

template <class Process, class BTNode>

void preorder(Process f, BTNode* node_ptr);

 

template <class Process, class BTNode>

void postorder(Process f, BTNode* node_ptr);

 

The next one, print, is very useful for displaying your tree:

 

template <class ItemType, class SizeType>

void print(binary_tree_node<ItemType>* node_ptr, SizeType depth);

 

We have a tree_clear function to destroy a tree (which has to happen recursively without losing the links):

 

template <class ItemType>

void tree_clear(binary_tree_node<ItemType>*& root_ptr);

 

We have a tree_copy function to make a deep copy of a full tree (also recursive):

 

template <class ItemType>

binary_tree_node<ItemType>* tree_copy(const binary_tree_node<ItemType>*

root_ptr);

 

 

Finally, the code has a recursive method to count up all the nodes in the tree and return that number:

 

template <class ItemType>

typename binary_tree_node<ItemType>::size_type tree_size(const

binary_tree_node<ItemType>* node_ptr);

 

We’ll discuss the bintree functions in class, but they should take care of a lot of the binary search tree functions, as long as you can call them properly.  I used print for debugging a lot. (Start print’s depth at

0, and depth will count up in recursions and terminate properly.)

 

Your bintree.cxx and bintree.h files give you the basic functions of a binary tree, but you are writing a class that extends this binary tree into a binary search tree. In the textbook, Carrano’s binary search tree has the rule that a binary search tree node has data that is greater than all the data in its left subtree, and its data is also less than all the data in its right subtree. But this doesn’t let us add duplicates to a tree, which is overly restrictive. We’ll relax this rule to say that the data in a binary search tree node is >= the data in its left subtree, and < the data in its right subtree. Now we can put duplicate entries in and not lose them.

 

In BSTreeBag.h, you will see the functions you need to create in the BSTreeBag.cxx file. These are template functions, like the bintree.cxx and bintree.h ones. You can use the functions in bintree to get this done; it will help you keep your code short and safe.

 

#ifndef BAG6_H

#define BAG6_H

#include <cstdlib>    // Provides NULL and size_t

#include “bintree.h”  // Provides binary_tree_node and related

functions

 

namespace hw6

{

template <class ItemType>

class BSTreeBag

{

public:

 

// TYPEDEFS

typedef unsigned int size_type;

typedef ItemType value_type;

// CONSTRUCTORS and DESTRUCTOR BSTreeBag( );

BSTreeBag(const BSTreeBag& source);

~BSTreeBag( );

 

// MODIFICATION functions

size_type erase(const ItemType& target);

bool erase_one(const ItemType& target);

void insert(const ItemType& entry);

void operator +=(const BSTreeBag& addend);

void operator =(const BSTreeBag& source);

// CONSTANT functions size_type size( ) const;

size_type count(const ItemType& target) const;

 

 

private:

 

 

 

 

 

addroot_ptr);

};

// Root pointer of binary search tree binary_tree_node<ItemType> *root_ptr;

void insert_all(binary_tree_node<ItemType>*

 

 

// NONMEMBER functions for the BSTreeBag<ItemType> template class template <class ItemType>

BSTreeBag<ItemType> operator +(const BSTreeBag<ItemType>& b1, const BSTreeBag<ItemType>& b2);

}

 

#include “BSTreeBag.cxx” // Include the implementation.

#endif

 

1. 1. BASIC BINARY SEARCH TREE FUNCTIONS (start here)

 

Begin (as we always must) by considering a constructor. Don’t forget the template line for each of these

functions. Like this:

 

template <class ItemType> BSTreeBag<ItemType>::BSTreeBag()

{

// ??

}

 

Your Bag should set its root_ptr to NULL here. Since no numbers have yet been added, we aren’t storing any nodes yet.  For us, an empty tree means the root_ptr is NULL, always.  That’s all this constructor needs to do. Here’s a beautiful sketch of the memory right now for this newly made bag:

 

 

Your copy constructor, next, would benefit by looking at the tree_copy function in bintree.h and getting that to work.

 

Your destructor, likewise, would probably use tree_clear.

 

Your assignment operator should (among other things) make a call to tree_clear if needed, and it should also use tree_copy.

 

Along these same lines, write size. The header for this needs a typename that’s got the class namespace and the unsigned integer type we defined there.  (It’s a hassle; I’ll go over it more, but this is needed to stop the compiler from kicking and screaming and punching.)

 

 

const

typename BSTreeBag<ItemType>::size_type BSTreeBag<ItemType>::size( )

 

 

All of these functions should go pretty quickly once you figure out what’s already been written. And if you do that, your memory managing functions are mostly done except for the insert and erase methods. Be sure you have this done early on and working by Friday at the latest, so you can finish the rest.

Upload what you have for the lab this week.

 

2. 2.  INSERTING AN ITEM INTO A BINARY SEARCH TREE

 

The next steps are to insert an entry, so you have a tree to play with. Remember that you always

know the tree’s root_ptr in this code, since that is a member of the class.

 

void BSTreeBag<ItemType>::insert(const ItemType& entry)

 

This involves handling one special case, where you’re inserting into an empty tree like the one that your default constructor made. You can tell if that’s true, provided that you set root_ptr correctly in that constructor. If so, say

 

root_ptr = new binary_tree_node<ItemType>(entry);

 

to make a new node on the heap (with left and right child pointers == NULL, and data containing the entry). The address of this node will now be stored in your root_ptr. In that case, your insert is done.   In the example below, we’ve inserted 76 into an empty binary search tree of integers.

 

 

If the tree already has data in it, though, the code has to put the new entry in the right place. This works a lot like the method for searching for an item in a tree (as discussed quite ably in the trees chapter of Carrano’s book).  In the example below, we have added 23 and 97 to the tree above:

 

 

Later, if we add more numbers (59, 103, 8), we’ll see:

 

 

One way to find the right place to insert a new entry is is to define a boolean variable called done, which starts as false (we have done nothing yet!) and a node pointer (binary_tree_node<ItemType>* cursor), which starts as root_ptr. Then, while done remains false,

 

If the data at the cursor is greater than or equal to the entry,

 

 

there.

If the cursor has no left child (its left()pointer is NULL), you can add the new entry

 

 

In this case, add the new binary_tree_node with this entry as the left child

 

cursor->left() = new binary_tree_node<ItemType>(entry);

 

and note that you are now done. else, keep looking in the left subtree

cursor = cursor->left();

 

Else, similar logic applies to the right subtree.

 

Notice that cursor->left() is now returning a binary_tree_node<ItemType>*&, and the reference return type allows us to assign to it. This change sticks around after the code finishes, so you have really added it.  Slick.

 

3. 3. ERASING AN ITEM FROM A BINARY SEARCH TREE

 

To erase an item from a binary search tree is harder. We usually have to replace the erased item with something else to keep the tree an honest binary search tree.  Erasing is complicated enough that we need 3 helper functions for all of the cases. One is bst_remove. This corresponds to erase_one; your public function erase_one will call your helper function bst_remove to do its whole job.

 

3a.        bst_remove

 

The code I used has a second helper function called bst_remove_max that bst_remove might need to use.  But first, let’s talk about bst_remove. bst_remove removes a single copy of a target from a tree, and updates the root_ptr (and the others) as needed. It returns true if it found the target to remove, and false if it did not.

 

bool bst_remove(binary_tree_node<ItemType>*& root_ptr, const ItemType&

target)

 

The first case for bst_remove to handle is when the root_ptr == NULL. In this case, we can return false right away; there is no search tree left to remove an item from.  That’s a base case for the recursion.

 

Else, if the root_ptr’s data is greater than the target, we must look in the left subtree for the item to remove. Make a recursive call using the left child of the root_ptr:

 

return bst_remove(root_ptr->left(), target);

 

Else if the root_ptr’s data is less than the target, look in the right subtree; do something like the line above;

 

Else, you’ve found the target at this root_ptr. Congratulations. Things now get complicated:

 

If the root_ptr has no left child, then you can delete root_ptr, but you want to replace it with its right child (even though that might be NULL, it’s ok).

 

binary_tree_node<ItemType>* old_root_ptr = root_ptr;

root_ptr = root_ptr->right();      // replace with right child

delete old_root_ptr;               // no leaks

 

Consider our tree again.

 

 

To reinforce this example, suppose we wish to delete the 97. Here is what should happen:

 

 

Else, you are removing a target in the middle of the tree with children, which is harder. You’ll probably have to replace this removed target with another entry in the tree to keep it a valid binary search tree. In this case, the best thing to do is to replace the target we’re deleting with the largest item in our left subtree. Suppose we want to delete the 76 from our tree and illustrate this example. Here is what should happen:

 

 

This function’s handled by the bst_remove_max function. Done correctly, this lets us replace our own data with the item we find there:

 

bst_remove_max(root_ptr->left(), root_ptr->data());

 

Now all your bst_remove cases should be done.

 

3b.        bst_remove_max

 

Back to bst_remove_max, which removes the largest item from a tree and writes this item back by reference to removed using a reference input parameter):

 

void bst_remove_max(binary_tree_node<ItemType>*& root_ptr, ItemType&

removed)

 

This means that when you find the binary_tree_node<ItemType>* with the maximum value (call that node frodo here), you say

 

 

removed = frodo->data();     // function remembers removed item bst_remove_max must consider 2 recursive cases.

The first is that it has been given a root_ptr with no right child. In this case, the data in root_ptr is

what needs to be removed, as above. We want to delete this root_ptr node, too, but carefully.

 

binary_tree_node<ItemType>* old_root_ptr = root_ptr;

 

If root_ptr’s right child is missing, we can replace the node we are deleting with its left child without breaking the rules of a binary search tree:

 

root_ptr = root_ptr->left(); // copy left child to root’s address

 

Now we can delete the old_root_ptr.

 

The second case is when the root_ptr has a right child, and we should look there for even bigger items.  The code below will update the right child (lvalue!) and the data (lvalue!) automatically.

 

bst_remove_max(root_ptr->right(), root_ptr->data());

 

3c.         bst_remove_all

 

Erasing all the items in a tree requires you to write bst_remove_all. This works like bst_remove, but if bst_remove_all finds and removes the target, it must still keep looking in case more copies of the target exist.  When you write this, have erase call bst_remove_all and you are done.

 

4. 4. COUNTING UP THE COPIES OF AN ITEM IN A BINARY SEARCH TREE

 

Counting the copies of a target item in the tree uses that size_type again (compiler no kick, no scream).

 

typename BSTreeBag<ItemType>::size_type

BSTreeBag<ItemType>::count(const ItemType& target) const

 

This requires us to walk a binary_tree_node<ItemType>* cursor from the root_ptr down through the tree, looking for more copies of target and counting our answer up with each one we find.  Initialize your answer to 0. Start cursor out as root_ptr.

 

While the cursor is not NULL, if the data at cursor is equal to the target, increment the answer to

1.

 

If the data at the cursor is greater than or equal to the target, return answer + the count in the left child.  Else, if the data is less than the target, return the count in the right child.

 

5. 5. ADDING ITEMS TO A BINARY SEACH TREE WITH +: operator+=, operator+, and insert_all

 

To implement operator+=, we add the helper function insert_all:

 

void BSTreeBag<ItemType>::insert_all(binary_tree_node<ItemType>*

addroot_ptr)

 

Here, if the addroot_ptr is not NULL, we insert its data into ourselves, and call

 

insert_all(addroot_ptr->left());

// and one other thing you can deduce from the line above.

 

Now, operator+= can check for self assignment (very important). If the assignment’s NOT something like  b += b, calling insert_all directly will work to do the job. If it is like b += b, though, we need to double b. For this, make a copy of the addroot_ptr, use that as the root to  insert_all, and then clear out the copy. Else, what bad thing can happen? Ponder that.

 

When you have operator+= working, use it to make operator+.

 

6. 6. SOME HINTS:

 

Work piece by piece. Comment out the tests you can’t pass in the functions.

 

Since this is a template class, debugging can be more difficult (some debuggers don’t permit breakpoints in a template function.) To help in debugging, you can call print(root_ptr, 0) in a program to print the binary search tree for the bag you’re changing. But clean those out before you submit the code.

 

If you use our Makefile, you might notice that the BSTreeBag and bintree templates in the .cxx files are never compiled on their own, but in order to create BSTreeBagTest and BSTreeBagExam, all the template files must be present in the current directory.

 

Most of your grade will be based on the correctness of your implementation. However, the TAs will also look at your work and assign some points for clarity and programming style. Make sure that your name is on all your work.