CSCI 362: Binary Search Tree

Handout

Grab the handout tarfile from Autolab

Overview

Complete the SearchTree class, our implementation of a binary search tree data structure which could be used to implement ADTs like set and map. Since the class is templated, implement the methods DIRECTLY in the “hpp” file. I have added “TODO” comments where it may not be clear you have to write additional code.

You are permitted to add private helper methods, but you are NOT permitted to change the public interface.

Getting Started

Start by implementing the Node constructors and one line methods like size and empty. If any incomplete methods result in compiler errors, write stubs that do nothing or return a default value. Test the four methods above before continuing.

Next, implement a few more methods and test some more. Continue iterating in this fashion. Do NOT attempt to write all of the methods before testing or you will almost certainly be DELUGED with errors.

For this assignment, I will be using my own test driver (which is provided in the handout) to assign a grade.

• If your header fails to COMPILE with my test driver you will receive a ZERO for the assignment.
• If a test fails you will receive ZERO points for that test.

Your header file MUST allow my driver to complete execution for you to receive a grade. You are STRONGLY encouraged to write your own tests to verify your methods are correct. However, you will ONLY be submitting the header file to Autolab.

Required Functions

// Node

template <typename T>
struct Node {
  
  // [*    ]  (default) constructor
  Node (const T& = T());
  
  // [*    ]  constructor
  Node (const T&, Node*, Node*, Node*)
};

template <typename T>
struct TreeIterator {
  
  // [**   ]  Iterator dereference
  reference operator*() const;
  
  // [**   ]  Post-increment
  Self operator++ (int);
  
  // [**   ]  Post-decrement
  Self operator-- (int);
  
  // [**   ]  in-order successor
  static ConstNodePtr increment (ConstNodePtr n);
  
  // [**   ]  in-order predecessor
  static ConstNodePtr decrement (ConstNodePtr n);
};

template <typename T>
class SearchTree {
  
  // [***  ]  copy constructor
  SearchTree (const SearchTree&);
  
  // [*    ]  empty accessor
  bool empty() const;
  
  // [*    ]  size accessor
  size_t size() const;
  
  // [**   ]  begin accessor (return iter to smallest element)
  iterator begin();
  const_iterator begin() const;
  
  // [**   ]  end accessor (return iter to header node)
  iterator end();
  const_iterator end() const;
  
  // [***  ]  delete all nodes and set header's pointers to nullptr -- use recursive clear
  void clear();
  
  // ========== HELPERS ==========
  
  // [**   ] returns minimum rooted at param
  NodePtr      minimum (NodePtr)       const;
  
  // [**   ] returns maximum rooted at param
  NodePtr      maximum (NodePtr)       const;
  
  // [***  ] returns node with value==v (or nullptr)
  ConstNodePtr findHelper (const T& v) const;
  
  // [***  ] inserts v into the tree rooted at r
  NodePtr      insert (const T& v, NodePtr& r, NodePtr parent);
  
  // [**** ] erase v from the tree rooted at r -- return true IFF erase succeeded
  bool         erase (const T& v, NodePtr& r);
  
  // [***  ] deletes all nodes in the tree rooted at r
  void         clear (NodePtr r);
  
  // [*****] does a level-order print for a SearchTree
  void         printLevelOrder (ostream& out, NodePtr r) const;
};

NOTE: Stars are representative of difficulty and/or order that you should implement functionality.

Logistics

You may work with ONE partner on this assignment. To create a group on autolab, perform the following steps:

1. Visit the Assessment page on Autolab
2. Expand the “Options” pane on the left
3. Click the “Group Options” link
4. Establish some (appropriate) group name
5. Enter the Millersville email address of your partner
   • Your partner will receive a confirmation email which they will need to click in order to establish the group.
6. When either of you submit, Autolab will record a submission for you.

Running the Test Driver

• Invoke make from the assessment handout directory
  • This will take some time – the test program is over 1000 lines
  • Ultimately, an executable called TreeTest should be generated
  • If TreeTest cannot be generated, your assignment cannot be graded
• Invoke ./TreeTest to run the autograder
  • a list of failed tests will be reported (if any)
  • your weighted score (out of 90 points) will be listed at the end

DO NOT SUBMIT TO AUTOLAB CONTINUOUSLY

The autograder is provided as part of the handout and runs on the linux lab machines.

Grading

This lab is graded out of 100 points total.

• 90 points are autograded
• 10 points are reserved for style, formatting, and good programming conventions.