Project for class...must be kept simplistic. An example of my programming style is included, along with the libraries as follows:
I have modified the genBST library by adding the functions necessary to implement the DSW balancing algorithm. The files genBST.h and genQueue.h are provided on Courseweb.
By including the above files, you should easily be able to create a program to build a binary tree by inserting a randomly generated sequence of integers, then balance convert it to a perfectly balanced tree by first invoking createBackbone, then invoking createPerfectTree. The createBackbone function places the number of nodes in its reference parameter. This value is the required parameter to createPerfectTree.
In keeping with our focus on evaluating the efficiencies of algorithms, your task is to determine, on average, what number of anticipated accesses to the tree are needed to justify the cost of balancing. To do this, you will have to modify the code provided to measure the work required, then analyze the results and write a logical and well-documented analysis.
A primary key to a valid analysis will be to determine the average number of nodes that are accessed in a random search of the tree. This will require determination of the level of each node in the tree before balancing and after balancing. It will also require that your code be modified to count the number of fundamental operations performed in the process of balancing the tree. For purposes of this analysis we will make the following assumptions:
· Fundamental data operations include data comparisons and pointer assignments.
· All fundamental operations are considered to have equal cost (a pointer assignment is equivalent in effort to a data comparison)
· All searches will be for items that are in the tree (no failed searches.)
In order to provide for both the data collection and verification of the code, your program must be designed to take its input from a simple text file, name to be input by the user. The user should also be prompted for the number of values to be inserted. (Note: Due to the recursive nature of some of the traversals, you should limit the number of actual data values used to 50 or fewer to avoid memory problems.)
**1) Complete and fully-functional working program(s) in executable form as well as *.cpp source code of all work done. Well-documented code required.
2) Deliverables must be in ready-to-run condition.
3) All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement).
WinXP C++ Visual Studio