Computer Science 1xx Assignment #N
DUE DATE: mmddyyyy
Learning Objectives:
(This is a list of the major topics that you, as
students, will learn in this
assignment:)
Grading Rubric: This document is available for you use - you should use it to to help guide your work. The rubric is a document which explains how your work will be evaluated, and is located here.
You must
implement a Binary Search Tree, with the methods Add, Find, and PrintAllInOrder.
In order for your code to interface well with the provided framework, you must implement these methods using
the signature and return type that is specified below.
You specifically do NOT need to implement the Remove method.
You are required to implement the
'basic' methods that listed are here:
BST Methods |
||
Method Name |
Returns |
Parameters / Description: |
Add |
ErrorCode enum, to indicate success, or lack thereof |
Parameters:
If the given value is not a duplicate of any values already in the tree, and there are no out-of-memory related errors, this method should add the value to the tree in the proper place. This method does not need to balance the tree in any way, so adding values in a bad order will result in an unbalanced tree (for example, adding a, b, c, d will result in a BST that resembles a linked-list). |
Find |
Bool true if the character is already present in the tree, false if it isn't already present. |
Parameters:
|
GetAllInOrder |
char[] - an array containing all the values in the tree, with the lowest/smallest value in slot 0, and the largest/highest value in the last slot |
Parameters:
Retrieve all the values that are stored in the tree, in order, in the array that the method allocates, and then returns. So if you add m, b, t, a, d, p in to the tree, and then call this method, you should see the values a, b, d, m, p, t stored in the array that is returned to the caller, in that order. |
In addition,
you are required to implement the
'advanced' methods that listed are here:
BST Methods |
||
New
Method Name |
Returns |
Parameters / Description: |
Clone |
A BST object, which is a copy of the current Binary Search Tree |
Parameters:
The copy (the clone) must be a structurally identical duplicate of the original, but must consist of a new set of BSTNodes. This operation must run in O( N ) time. You are specifically forbidden from cloning the tree by simply calling the Add method (on a new tree) once for each value in the old tree. |
FindDepth |
An int - the depth/height of the tree. |
Parameters:
The depth of a tree (also known as a tree's height) is the largest number of levels in the tree. So a tree constructed by adding the values 10, 11, 12 has a height of 3. Adding the values 11, 10, 12 to an empty tree will result in a tree with height of just 2. Adding just 10 and 11 to an empty tree will also create a tree of height 2, and adding nothing to an empty tree will result in a tree of height 0. |
Balance |
Nothing |
Parameters:
This will balance the binary search tree.
You are free to allocate as much memory as you want, and to take
as much time as you want, in order to effect this change.
The tree does not need to maintain it's balance between
invocations of this method. To be clear, once this method is done executing, the resulting tree must be a valid BST Find, PrintAllInOrder (and Add) must all work correctly, and in O( log2(N) ) time. The normal implementations of these methods (for a normal BST) should be sufficient to accomplish this. While you are free to look up an implementation of an AVL (or Red-Black) tree in order to keep the tree ordered, we should be clear that implmementing such an algorithm is beyond the scope of the assignment you should be able to rebalance this yourself, only when this method is invoked. It is highly recommended that you think your solution to this problem through before you start coding. In particular, the instructor would be happy to double-check your solution before you begin coding it. |
You will be provided with a starter project that will provide you with most of the the implementation of most of the XNA-based game, including some logic needed to display the binary search tree on the screen (in the CBinarySearchTree, and CTreeNode classes).
You are not allowed to work in groups for this assignment. You should start, finish, and do all the work on your own. If you have questions, please contact the instructor.
Additionally, you should aggressively comment your code, paying particular attention to areas that are difficult to understand. If you found something to be tricky when you wrote it, make sure to comment it so that the next person (the instructor, who's grading you) understands what your code is doing. It is not necessary to comment every single line.
The purpose of new requirement is to both help you understand, and have you demonstrate, a thorough understanding of exactly how your program works.
Every file that you turn in should have:
·
At the top of each file that
you normally edit, you should put your name (first and last), the name of this
class (BIT 142), and the year and quarter, and the assignment number,
including the revision number, which starts at 0 (A2.0). If youre handing
this in again for a regrade, make sure to increase the minor version number by
one (from A2.0, to A2.1").
You normally edit the C# source code files (.CS files), and any Word documents
that you're handing in (if any).
You do not normally edit the .SLN or .CSPROJ files, and so you should not try to
put this identifying information in those files.
In general, you should make sure to do the following before handing in your project:
· All variables used should have meaningful names.
· The code should be formatted consistently, and in an easy to read format.
What to turn in:
· A single electronic folder (a directory). This folder should contain:
o
The source code for the
program all the .CS files in your project.
I would prefer that you include the project files stuff ending in .SLN and
.VCPROJ, so I can build your project more easily. If you can save these files
(the .SLN / . VCPROJ) into a file format that can be opened by VS.Net 2003, that
would be great.
o
You have to name the folder
with your last name, then first name, then the assignment number (both the major
version 2, and the minor (revision) number 0). Example: "Panitz, Mike,
A2.0"
· You should not include the Debug directory, or anything from it. I will dock you a couple points if you do. Also, you don't need to include your .NCB file, if it's present.
How to electronically submit your homework:
There's a link on the homework page to the document that guides you through handing in your work, using the SourceGear Vault program.