Exercise 6

Creating a Binary Search Tree (BST)

Due Date - November 6, 2012 @ 6:00pm

Introduction

Previously, we used a recursive binary search algorithm to search for certain values within a set of sorted values.  What if the values need to be sorted before performing this search? We would need a way to store the set that allows for both efficient sorting and efficient searching.  In programming, a common way to do this is with binary search trees.  A BST is a binary tree data structure with the the following characteristics (From Wikipedia):

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.
• There must be no duplicate nodes.

When dealing with BST's, they are optimal whem the BST is balanced.  A BST with n nodes is balanced when its height h, the number of levels below the root, is equal to log ₂ n rounded down to the closest integer.    An example of the difference between an unbalanced and a balanced BST is shown in the iamge below.

Assignment

      Write a C program that recursively creates a balanced BST from an ordered set of values.

Specification

1. Your program should exit and print an error message by using the code given in PrintError() under the following circumstances:

• If the user does not give enough arguments.
• If the program can’t open the file.
• If the dynamic memory is not allocated properly.
• If the numbers in the file are not sorted in increasing order.

2. The  name of the file are given as a command-line arguments. (e.g. ./ex6  <filename>)
3. Your binary search algorithm must be implemented as a RECURSIVE function.
4. You will need to dynamically allocate memory to store the ordered numbers.
5. You will need to dynamically allocate memory to store the BST.
6. You can assume the values in the file are distinct.

7. You cannot use anything like the following:

       int size = 0;
       ... /* find the number of elements */
       int array[size]; 
   

   You have to use malloc and free. Failure to do so wil result in loss of points.

8. The numbers in the file can be stored in a 4-byte integer ("int" in C). You don't need to test extreme cases whether the numbers in the file may need more than 4 bytes.

9. Your output needs to show how many numbers in the file. 

10. You should check memory leak. Failure in the valgrind check wil result in loss of 50% points for each testcase.

Skeleton

You can download the skeleton for ex6 here.  It contains the following files

• ex6.c - Contains the main function for this assignment
• bst.c - Contains the auxillary functions for this assignment
• utility.h - Contains all function headers and constants
• tree.h - Contains the defintion of a BST node and the function header for the PostOrderWalk function used to evaluate the shape of your tree. You must use this definition for a BST node for this assignment.  You should not write your own version of PostOrderWalk for this assignment.
• tree.o - Contains the object file  for the PostOrderWalk function.  This file weas generated on a machine in EE 206/207.  It will not work if used on other operating systems.  Please use  the machines in EE 206/207 when testing your code by visiting or using a secure shell client.
• Makefile - Contains sections that will compile, run some of the provided testcases, and compare your solution with the expected solution.  To run the part that will run your code with the provided testcases and do the comparison, type make test.
• A suite of testcases and their solutions.

Do not modify the main function (do not modify the arguments and do not modify the function body). Do not modify the PrintError function. Do not add new files and remove files. Do not modify the names, return types, and arguments of the functions in the skeleton.

You can add new functions inside bst.c.

For this exercise, you should change only bst.c and utility.h.

Example

Numbers in the file:

196 204 426 1280 5142 25719 154328 1080307 8642466

Output:

There are 9 numbers in the file.
Left
Left
Left
Back
Right
Back
Value: 196
Back
Right
Left
Back
Right
Left
Back
Right
Back
Value: 1280
Back
Value: 426
Back
Value: 204
Back
Right
Left
Left
Back
Right
Back
Value: 25719
Back
Right
Left
Back
Right
Left
Back
Right
Back
Value: 8642466
Back
Value: 1080307
Back
Value: 154328
Back
Value: 5142
 

Grading

2 points total.

Points will be take off if the program doesn't meet the specifcations.

You should consider possible testcases on your own. Passing all the testcases we gave you doesn't guarantee receiving  full percentage of the score.

Valgrind Check

Valgrind is used to check if your program has a memeroy leak (By Wikipedia).

In the Makefile, we have turn on valgrind check by the command:

 valgrind --leak-check=yes --verbose

In this case,-- verbose is one of the option telling valgrind to give extra information on various aspects of your program, such as: the shared objects loaded, the suppressions used, the progress of the instrumentation and execution engines, and warnings about unusual behaviour.

You can refer to more options about valgrind here (Provided by Valgrind™ Developers).

While your program ends with  all the heap memeory freed, you should see the following sentences at the end of its report,

==6104== HEAP SUMMARY:
==6104==     in use at exit: 0 bytes in 0 blocks
==6104==   total heap usage: 2 allocs, 2 frees, 968 bytes allocated
==6104==
==6104== All heap blocks were freed -- no leaks are possible
==6104==
==6104== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 6)

The most important part of the valgrind output is the statement All heap blocks were freed -- no leaks are possible. 

If you see that statement, valgrind passed.  If not, then there is memory leak.

Submission Procedure

   Create a zip file that contains the folowing files

• ex6.c
• bst.c
• utilith.h
• Makefile - The makefile should produce an executable "ex6".

To create a zip file in the Linux terminal, type

zip ex6.zip ex6.c bst.c utility.h tree.h Makefile

and the submit the zip file (i.e. ex6.zip) to Blackboard

You can also submit this .zip file to the course testing website for additional testcases.

References

.h Files

• All constants you will need.  Constants can be defined using the #define command.  An example would be  "#define MAXLEN 102".
• All function headers  for the function in your program. 
• Any macros you have created

Your .h file should be included in your .c file. 

Links about recursion:

Introduction to recursion with examples.
The code is in C++. However the only difference in this code respect to C is how the print to console. "cout<<"hello"" is used instead of printf("hello").

Demonstration of a step to step recursion algorithm

Recursion vs Iteration