CSCE 3110 Data Structures
Assigment 4
Total: 120 points
Issued: 03/25/2007
Due: 04/09/2007
................................


1. (40 points) Consider a tree storing 1,000,000 items. What is the worst-case
height of T in the following cases:
       a. T is an AVL tree.
       b. T is a (2,4) tree.
       c. T is a binary search tree.
       d. T is a B-tree of order 100.
Justify your answers.

2. (60 points) Implement a binary search tree ADT what include functions for performing the following
operations:
-----------------------------------------------------------------------------------------------------
1. Delete a key
2. Perform a pre-order traversal of the tree
3. Perform a post-order traversal of the tree
4. Perform an Euler Tour Traversal of the tree
5. Count the number of nodes in the tree (without explicitly keeping track of the size of the tree with a variable) 
6. Caculate the height of the tree (again without explicityly keeping track of the size of the height with a variable)
7. Swap the left child and right child of every node of the binnary search tree.

What is the running time of your algorithm for each case? Save your program as BSTree.cpp?

Following is a sample program that implemented a skeleton of the ADT for a binary 
search tree. The ADT contain some of the basic operations on binary search trees. 

http://www.cse.unt.edu/~huangyan/3110/sampleProg/BSTree.cpp

Use or modify only if it helps you. If you do not use the codes provided, you will need to implement a similar
procedure for testing all the functionalities that you implemented.


3. (20 points) Show what the AVL tree looks like when the following numbers are inserted into initially empty AVL tree
(please show the tree after each insertion:
   45,23,89,12,11,5,23,10

Submission instructions:  
   - write a README file including the answers to problems 1 and 3, and a 
     detailed note about the functionality of each of the above programs, 
     and complete instructions on how to run them.
   - make sure you include your name in each program and in the README file.
   - make sure all your programs are fully commented, and compile and run 
     correctly on the CSP machines.
   - submit your assignment by the due date using the 'project' program.
     class code is '3110s001', and the project name is 'tree'.