Computer Science 1xx – Assignment #N

DUE DATE: mmddyyyy  

Binary Search Trees

 

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.


 

What the program must accomplish:

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:

  1. The character to be added to the tree.  This should not be a duplicate of any values in the tree

 

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:

  1. The character to be located within the tree. 

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:

  1. None

 

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:

  1. None

 

            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:

  1. None

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:

  1. None

 

            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.
            This should take no more than O( N ) time, and no more than O( N ) space.  NOTE TO INSTRUCTORS: Yes, this does place restrictions on the solution, given that the prior paragraph said 'as much memory as you want'

            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.

 

Starter Project:

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).

 

Group Work, Commenting:

 

            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 you’re 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.

 


This document and the related materials are developed with support from Microsoft Research Computer Gaming Initiative under the Computer Gaming Curriculum in Computer Science RFP, Award Number 15871.