Courses/CS 2124/Lab Manual/Templated Binary Search Tree

From A-State Computer Science Wiki
Jump to: navigation, search

A portion of this lab is to be done during the scheduled lab time. The take-home programming assignment is to be turned in before the next lab; see the lab website. The in-lab portion is worth 40% of the lab credit; the programming assignment is worth the other 60%. See the website for details on how the programming assignment will be graded. You are not responsible for user errors in input unless specified in the assignment. Feedback will be provided explaining your grade on each assignment.

It is important that you complete each step before going on to the next, as the exercises build upon one another. You will find it helpful to diagram the action of each method or function as you go along. If you have difficulty in some step, DO NOT proceed before resolving it; seek assistance from your lab proctor. You will not be able to fully appreciate the remaining content of the lab and you are likely to compound the problem.

Introduction

In this lab you will modify the BinarySearchTree class you created in a previous lab. You will make the tree a template, allowing it to work with any data type, and you will finish the tree's functionality by adding some methods.

Topics Covered in this Lab:

  • Templates applied to Binary Search Tree
  • Binary Search Tree Delete

Questions Answered in this Lab:

  • How can the Binary Search Tree be generalized to work with any type of contents?
  • How are values deleted from a Binary Search Tree?

Demonstrable Skills Acquired in this Lab:

  • Ability to implement a generic Binary Search Tree
  • Ability to implement the delete-by-copy algorithm in a Binary Search Tree.

Templated Binary Search Tree

In a previous lab, you created a binary search tree, based on nodes that were designed to contain an object of type Contact. In this lab, you will generalize your binary search tree so that it can contain any type of data, and you will finish out the functionality so that the tree will allow deletion.

The original Node was defined as follows:

class Node
{
   public:
               Node 
                  (const Contact& data);
      void     setLeft
                  (Node* newLeft);
      Node*    getLeft
                  (void) const;
      void     setRight
                  (Node* newRight);
      Node*    getRight
                  (void) const;
      void     write
                  (ostream& outfile) const;
   private:
      Contact  info;
      Node*    left;
      Node*    right;
};
      ostream& operator <<
                  (ostream& outfile, const Node& n);

And the class definition for the BinarySearchTree looked like:

class BinarySearchTree
{
   public:
               BinarySearchTree
                  (void);
      bool     addRecursively
                  (const Contact& newEntry);
      bool     addIteratively
                  (const Contact& newEntry);
      void     writeRecursively
                  (ostream& outfile) const;
      void     writeIteratively
                  (ostream& outfile) const;
   private:    // methods
      void     addRecursively    // called by public version
                  (Node* currentRoot, Node* newNode);
      void     writeRecursively  // called by public version
                  (ostream& outfile, Node* currentRoot) const;
   private:    // data
      Node*    root;
};

Begin by making your Node a template class, with the following definition:

template <class ValueType>
class Node
{
   public:
                        Node 
                           (const ValueType& data);
      void              setLeft
                           (Node<ValueType>* newLeft);
      Node<ValueType>*  getLeft
                           (void) const;
      void              setRight
                           (Node<ValueType>* newRight);
      Node<ValueType>*  getRight
                           (void) const;
      ValueType         getData
                           (void) const;
      void              write
                           (ostream& outfile) const;
   private:
      ValueType info;
      Node*     left;
      Node*     right;
};
      ostream& operator <<
                  (ostream& outfile, const Node& n);

This will require little modification of your original code, aside from replacing the Contact data type with the template parameter ValueType. You will need to implement a new method: getData() should return the data value held in the node.


Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate your templated Node class.


Now, modify your BinarySearchTree class definition so that it matches the following:

template <class ValueType>
class BinarySearchTree
{
   public:
                                    BinarySearchTree
                                       (void);
                                    BinarySearchTree
                                       (const BinarySearchTree<ValueType>& original);
                                    ~BinarySearchTree
                                       (void);
      BinarySearchTree<ValueType>&  operator=
                                       (const BinarySearchTree<ValueType>& rhs);
      bool                          insert
                                       (const ValueType& newEntry);
      void                          write
                                       (ostream& outfile, string sep=", ") const;
      bool                          contains
                                       (const ValueType& searchValue);
      bool                          remove
                                       (const ValueType& value);
      void                          clear();
      bool                          is_empty() const;
   protected:    // methods
      Node<ValueType>* search(const ValueType& searchValue) const;
      Node<ValueType>* search(const ValueType& searchValue, Node<ValueType>*& parent) const;
      void             remove(Node<ValueType>* victim, Node<ValueType>* parent);
   protected:    // data
      Node<ValueType>*    root;
};

Note: You will need to convert either your addIteratively() or addRecursively() method into the new insert() method. You will also need only one of the write...() methods. It would be preferable to use the iterative versions for efficiency, but correctness will be more important here than efficiency. If you use the recursive versions, modify the private helper method as necessary. The code shown above does not reflect this — it reflects the choice of the iterative insert() and write() methods.

Modifications

  • Change the private sections to protected.
BinarySearchTree() 
Create a copy constructor that will create a new BinarySearchTree that is a deep-copy of an existing tree. This could be implemented using the overloaded assignment operator that you will be adding below.
~BinarySearchTree() 
If your class does not already contain a destructor, create one now. The destructor could just make a call to the clear() method...
clear() 
Remove all elements from the binary search tree, freeing all dynamically allocated memory. The tree should be left in an empty state, ready for new values to be inserted.
is_empty() 
Returns true if the tree contains no elements, or false otherwise.
operator=() 
Create an overloaded assignment operator for the tree. A pre-order traversal will be necessary for this (create each node's children first, before moving down the tree).
insert() 
Modify your insert() method (if needed) so that duplicate values will not be inserted into the tree. The insert() method should only return true when a new value was inserted. It should return false if the tree already contained the value being inserted.
write() 
Modify your write() method so that the caller can provide an optional second paramter consisting of a string that should be used to separate data values. The separator should default to "comma-space", and should not be displayed preceding the first data value or following the last data value.
contains() 
Should return true if the searchValue is in the tree, or false otherwise. Internally, you should make use of the protected search() method for this to avoid duplicating code.
search() 
Should return a pointer to the node containing searchValue if it is found in the tree, or null if the value is not in the tree. The method should be overloaded so that a second argument may be included (by reference). If provided, this parameter will be set to point to the parent of the node where searchValue was found, or to null if the value isn't found in the tree, or if the value was found at the root of the tree. The one-parameter version of the search function should simply call the two-parameter version (ignoring the resulting value for parent).
remove() 
Should safely remove a value from the tree, and properly free memory allocated to the node. If the value was found in the tree, remove() should return true, or false otherwise. This version of remove() should simply locate the node that is to be deleted, then call the second version of remove() to actually perform the deletion.
remove() 
(protected helper version) Given a pointer to a node that should be deleted (victim) and its parent node (parent), remove the victim node from the tree. Note that if the victim is the current root of the tree, then the parent pointer will be null. One algorithm for deleting from a binary tree is outlined below.


Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate each of your added methods as soon as they are completed.


Delete

Deleting from a binary search tree involves handling three possible cases:

  • deleting a leaf node
  • deleting a node with one child
  • deleting a node with two children

Two of these cases are trivial:

  • To delete a leaf node, simply set the link from the parent to the node to null, then free the memory used by the node.
  • To delete a node with one child, set the link from the parent so that it points to the node's child subtree, then free the memory used by the node.

Deleting a node with two children is more difficult, since the node has one incoming link (from the parent), but two outgoing links. Thus, the node itself cannot simply be removed without damaging the structure of the tree.

One way to delete a value from an interior node with two child subtrees without damaging the tree's structure is called delete by copy. It proceeds as follows:

  • While maintaining a pointer to the node that should be deleted (call it victim), locate either the largest value in the left subtree, or the smallest value in the right subtree. The algorithm for finding the largest value in the left subtree follows:
    • Start with a pointer to the left child (call it current), and a second pointer that will "follow" current down the tree, always pointing to the parent of the current node (call it parent). Now iteratively move current down the right subtree as far as possible (with parent following). The largest value in the subtree will be located at the right-most branch. Be careful not to move your current pointer off the bottom of the tree...
    • The algorithm for locating the smallest value in the right subtree is symmetrical to this.
  • Copy the data value from the current node into the victim node
  • Delete the current node. This will be a trivial delete involving either a leaf or a node with only one child — see above. You can perform this operation with a recursive call to the delete helper function. Draw a few trees to help you visualize this.

Test your code thoroughly before submitting. You will be using this tree as a base class in the homework assignment. It will need to be error free



Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate your working tree and the test code you have developed before leaving the lab.


Create a .zip or .tar.gz (or similar) archive of all the source files in your project (NOT any binary files!) and submit to the [CSCADE] website.


Labsubmitsinglefile.pngUpload your solution in a file named binary_search_tree.zip.