Data structure HW

HONOR CODE

COMP-3040

Data Structures

Assignment-3

Due on 10/05/2016

I pledge my honor that I have neither given nor received aid on this work. Do not sign until after you have completed your assignment.
Name:	Signature:

1. Refer to program p3-1-BinarySearchTree.cs

a. Write code to build a Binary Search Tree with the following nodes: 55, 29, 80, 22, 41, 72, 35, 78, 44, 90, 18, 88, 25, 60. Print screen shot of the run.

b. Add one operation in your program that finds the height of BST. Find the height of the BST you build in a) by calling this method in the Main method

c. Draw the tree (on paper, preferably using MS-Word).

d. Draw the tree after deleting node 90

e. Draw the tree after deleting node 80 (from the original tree, not from after d))

f. Draw the tree after deleting node 55 (from the original tree, not from after d) and e))

g. Draw the tree after inserting a node whose key is 43 to the original BST.

2. In a BST with n nodes, how many comparisons are needed for searching, insertion, and deletion in worst case, respectively? How many comparisons are needed for these operation in average case, respectively?

3. Write a class of BST of Employee records (Employee empID is used as key). The class must contain the following operations:

· Search a node (given an employee’s empID ), and print the record when it is found.

· Insert a node (given a new employee record)

· Delete a node (given an employee’s empID )

· Print out of all employee records in the BST in in-order traversal.

Write the Main method to test your program as follows:

· Create an empty BST.

· Insert 10 Employee records into the BST in the following order:

empID	Name	Salary
1055	name1	Random 40k-90k
1029	name2	Random 40k-90k
1080	name3	Random 40k-90k
1022	name4	Random 40k-90k
1041	name5	Random 40k-90k
1072	name6	Random 40k-90k
1035	name7	Random 40k-90k
1078	name8	Random 40k-90k
1044	name9	Random 40k-90k
1090	name10	Random 40k-90k

and print the BST in in-order to confirm 10 records are inserted correctly.

· Search an employee record (given an employee’s empID ), and print the employee record if the empID is found.

· Delete an employee record (given an employee’s empID ), and print the BST in in-order to confirm that the record is deleted.

The Employee class is given as follow:

class Employee

{

public string name;

public int empID;

public double salary;

public void Input()

{

Console.Write("Name: ");

name = Console.ReadLine();

Console.Write("ID: ");

empID = int.Parse(Console.ReadLine());

Console.Write("Salary: ");

salary = double.Parse(Console.ReadLine());

}

public Output()

{

Console.WriteLine("[{0}|{1}|{2:C}]", name, empID, salary);

}

public override string ToString()

{

return string.Format("({0}|{1}|{2:C})", name, empID, salary);

}

}