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

• Binary Search Tree - Basic Operations
In this assignment, you will implement a basic set of operations on a normal Binary Search Tree, such as Add, Find, and Print (all elements, in order)

• Binary Search Tree - Advanced Operations
You will also implement some additional / non-standard operations on a binary search tree, such as computing the height of a tree, cloning a tree, and balancing a tree using an (inefficient) supplementary array (which will require no more than O(N) space, and O( N ) time ).

• Recursion in the context of Binary Search Trees
You'll need to implement several of the methods using a recursive, 'divide-and-conquer' approach

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:

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: 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: 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: 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 all the XNA-specific code that you might need, including the InOrderDraw method, which is responsible for drawing a picture of the BST on the screen, as the game is being played.

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