CSC 210 Lab 6

COMPUTING SCIENCE 210
Algorithm Analysis and Data Structures

Lab 6 -- Binary Search Trees

Due Date: Friday, December 4 (at the start of the lab session)

Note: There is no lab 5. The weightings of labs and programming assignments will be adjusted to account for the missing 4%.

Objectives

To understand the characteristics of binary search trees, including how the shape of a BST affects the efficiency of the search operation.
To understand the relationship between the order in which data arrives for insertion into a BST and the shape of the resulting tree.
To gain experience with recursive programming.

Assignment

Part 1 -- Order of Insertion and BST Shape

Copy the file

\\Bach\Sys\Public\CSC210\Labs\9\Treesrch.cpp

to your own subdirectory and compile it. (You may wish to copy the header files from the same directory as well. Use a project file to compile the program. Select the compiler option "Precompiled headers -- Use but do not generate.")

Use the program in interactive load mode to enter data (small integers, no duplicates) such that you produce three trees of the following shapes:

A worst-case tree: a single line extending downward to the right from the root node. (Seven or eight nodes will suffice.)
An almost-worst-case tree: two lines descending from the root in an inverted-V formation. (Seven or nine nodes will suffice.)
A best-case tree: a full BST with four levels, each level having the maximal number of nodes (counting the root node as a level). [You get to figure out how many nodes will be needed.]

In a written statement, discuss the relationship between the order in which data items arrive for insertion into a tree and the shape of the resulting tree. Specifically, identify orders that lead to a worst-case tree (from the perspective of searching for data) and a best-case tree. Explain why these orders result in the best and worst cases respectively.

Part 2 -- Generating a Best-Case BST

Extend the loadTree function to allow a fourth option: "Load a Best-Case Tree". Write a new function loadBestCaseTree() which is called when the user selects this new option. The new function should inquire how many items the user wants in the tree (N) and then generate calls to the add method that result in a completely full binary search tree containing the values 1, 2, ... N. Confirm that your function works by printing a tree that results from calling it.

Lab Report

Submit a lab report which includes your answers to the questions posed in Part 1 and the printout of the tree specified in Part 2, along with the changed portion of the source code.

E-mail a copy of your revised Treesrch.cpp to mohrj@augustana.ab.ca.

COMPUTING SCIENCE 210 Algorithm Analysis and Data Structures