Programming Assignment #5: Basics of binary search trees

Due: Wednesday, March 14

Purpose: Incorporate operator overloading and the capacity console input/output into the DateType class, and revise the Tree class for handing date information in binary search trees. 

*********************************************************

First, download and unzip this code framework  to get the Visual Stidio.NET project, which includes the following source code files:

 

·        DateType.h specifies the enhanced interface of the revised DateType class for storing date information.

·        DateType.cpp provides partial implementation of of the revised DateType class.

·        Tree.h specifies the interface of the revised Tree class for storing date information.

·        Tree.cpp implements the details of the member functions of the revised Tree class.

·        main.cpp contains the main function in it to use the Tree class and the DateType class and to test the functionality of both classes.

 

Steps:

 

  1. Carefully examine the enhanced interfaces of the revised DateType class and the revised Tree class.

 

  1. Add code into DateType.cpp to fully implement the SetRandomDate method (you need to call the rand( ) function in  the standard C++ library for random number generation), all the new overloaded relational operators in the DateType class, and  the global operators >> and << for  input and output involving DateType objects. If you prefer using your own implementation of the DateType class, you can retain your own DateType.cpp as the basis of enhancement instead of the one given in the sample framework.

 

  1. Use main.cpp to add code to carefully test to make sure your implementation of the DateType class works fine.

 

  1. Totally rewrite the main function to declare a Tree object myTree and use a loop to display a menu allowing the user to repeated do any of the following tasks until the user wants to quit the program:
    1. display the current contents of myTree
    2. insert a new date into myTree
    3. remove a date from myTree
    4. search to determine whether a date given by the user is currently in myTree
    5. randomly generate and insert n random dates into myTree (n is given by the user) and then randomly generate and delete n random dates from myTree,
    6. quit the program

 

Submit your work to the TA:

submit all your source code files (.cpp and .h files) and a brief description of how much you have accomplished and what bugs you know to the TA by the due date.

 

 

**************************************************************************

**************************************************************************

 

Experiment#1 (Email your findings to Dr. Lin)

 

                                 i.            After finishing Programming Assignment #5 above, use the option of random insertion and deletion of n dates with n up to 10000 into the binary search tree, and manually estimate how much time it takes for the program to complete the task.

                               ii.            Go back to your Programming Assignment #4: project and replace the old DateType.h and the old  DateType.cpp files there with the new enhanced versions you have here.

                            iii.            Modify the main function in DateTest.cpp to add the one more option into the user menu there: generate and insert n random dates into the linked list (n is given by the user) and then generate and delete n random dates from the linked list. See the foot note [1] for more details.

                             iv.            After finishing the revision of Programming Assignment #4 above, Use the option of random insertion and deletion of n dates with n up to 10000 into the linked list, and manually estimate how much time it takes for the program to complete the task.

                               v.            Compare the results of (i) and (iv) above and email your findings to Dr. Lin by the due date.

 

**************************************************************************

**************************************************************************

 

 

 

 

 

 


[1] The purpose of Experiment 1 is to stretch the data structure (either a binary tree or a linked list) by first inserting a batch of n random dates into the data structure, and then deleting another batch of n random dates from the data structure to see how much time it takes.

 

The dates in the second batch are not related to these in the first batch. In other words, for the deletion phase random dates generated may not be in the data structure at all.

 

You do not need to seperate the insertion phase and the deletion phase into two separate menu options. See the following sample code segment. (If you do seperate them into two seperate menus, it is fine. But in your experiment you should do insertion of n random dates first and then do deletion of n random date, Otherwise, it would be trivial for trying to delete random dates from an empty data structures.)

...

 

//For stretching the binary search tree, can use similar construct to stretch a linked list

Tree myTree;

DateType myDateTypeObject;

 

               cout   << "Two batches of random dates to insert and delete\n:";

            cout << "How many random dates should we generate in each batch?\n:";

            cin >> num;

            //build up a random binary search tree of num nodes by doing num insertions

            for(int i = 0; i < num; i++)

            {

                myDateTypeObject.SetRandomDate();

                myTree.Insert(myDateTypeObject);

            }

            //stress the data structure by doing num deletions

            for(int i = 0; i < num; i++)

            {

                myDateTypeObject.SetRandomDate();

                myTree.DeleteItem(myDateTypeObject);

            }

 ...